[Math] A problem on Expected value using the survival function

markov chainsprobability

Let $X$ be a random variable denoting the number of times needed to roll ( including the last roll) a fair six-sided die until we obtain 4 consecutive six's. I would like help in computing $\mathbb{E}(X).$

I think I have to use the formula $$ \mathbb{E}(X) = \sum_{n=1}^\infty \mathbb{P}(X\geqslant n) $$ but I'm not sure how to compute $\mathbb{P}(X\geqslant n),$ so I'd like a little help.

Best Answer

The system can be described by a 5 states Markov chain, with the state described by a number of consecutive six's accumulated so far. The transition matrix is: $$ P = \begin{bmatrix} 1-p & p & 0 & 0 & 0 \\ 1-p & 0 & p & 0 & 0 \\ 1-p & 0 & 0 & p & 0 \\ 1-p & 0 & 0 & 0 & p \\ 0 & 0 & 0 & 0 & 1 \end{bmatrix} $$ where for the case at hand $p=\frac{1}{6}$ is the probability to get a six at the next rolling of the die.

The classic way to solve this is to consider the expected number of rolls $k_i$ given an initial state $i$. We are interested in computing $k_0 = \mathbb{E}(X)$.

Conditioning on a first move, the following recurrence equation holds true: $$ k_i = 1 + p k_{i+1} + (1-p) k_0 \qquad \text{for} \qquad i=0,1,2,3 $$ with boundary condition $k_4 = 0$. Solving this linear system yields: $$ k_0 = \frac{p^3+p^2+p+1}{p^4} \quad k_1 = \frac{p^2+p+1}{p^4} \quad k_2 = \frac{p+1}{p^4} \quad k_3 = \frac{1}{p^4} \quad k_4 = 0 $$

In[24]:= Solve[{k0 == 1 + k1 p + (1 - p) k0, 
   k1 == 1 + k2 p + (1 - p) k0, k2 == 1 + p k3 + (1 - p) k0, 
   k3 == 1 + p k4 + (1 - p) k0, k4 == 0}, {k1, k2, k3, k0, 
   k4}] // Simplify

Out[24]= {{k1 -> (1 + p + p^2)/p^4, k2 -> (1 + p)/p^4, k3 -> 1/p^4, 
  k0 -> (1 + p + p^2 + p^3)/p^4, k4 -> 0}}

Substituting $p=\frac{1}{6}$ gives $k_0 = \mathbb{E}(X) = 1554$.


Added A good reference on the subject is a book by J.R. Norris, "Markov chain" (Amazon). The chapter on discrete Markov chains is available on-line for free from the author. Section 1.3 discusses finding mean hitting times $k_i$.