I first encountered this problem in the final of my probability class. Later, similar questions appeared here and there so I decided to write this solution. The method involved is known as “first-step analysis”, which is very useful in stochastic processes.

A and B play a game of fair dice. A keeps throwing the fair die until he obtains the sequence “11” in two successive throws. B throws the die until he obtains the sequence “12” in two successive throws. Are their expected waiting times the same? Compute their expected waiting times.

Solution (CLICK ME):

Let $E_0=[\text{ expectation to get '11' if last roll is not 1 }]$ and $E_1=[\text{ expectation to get '11' if last roll is 1 }]$. Then we have the following recursive relationship: \begin{align*} \begin{cases} E_0 = \frac{1}{6}(E_1+1)+\frac{5}{6}(E_0+1) \\ E_1 = \frac{5}{6}(E_0+1)+\frac{1}{6}, \end{cases} \end{align*} which gives \begin{align*} \begin{cases} E_0 =42\\ E_1 =36. \end{cases} \end{align*} Here $E_0 = 42$ is the average waiting time to obtain the sequence '11'. Similarly, let $E'_0=[\text{ expectation to get '12' if last roll is not 1 }]$ and $E'_1=[\text{ expectation to get '12' if last roll is 1 }]$. Then we have the following recursive relationship: \begin{align*} \begin{cases} E'_0 = \frac{1}{6}E'_1+\frac{5}{6}E'_0+1\\ E'_1 = \frac{1}{6}E'_1 + \frac{4}{6}E'_0+1 \end{cases} \end{align*} which gives \begin{align*} \begin{cases} E'_0 =36\\ E'_1 =30, \end{cases} \end{align*} Here $E'_0 = 36$ is the average waiting time to obtain the sequence '12'. We see that, in average, we should expect to see the sequence '12' sooner compared to '11'.


A similar but simpler problem: find the expected number of coin tosses until first two consecutive heads, i.e., ‘HH’. You can try to solve it by the method above.