I am faced with the following question (which might be quite classical):
Suppose that we have a fair coin and we toss it until we have two consecutive heads (H) or tails (T). What is the expected number of tosses until the game stops?
Let $X$ denote the required random variable and let $AB$ denote events $A$ followed by $B$, where $A, B \in \{ H, T\}$. Then by the standard technique of conditional expectation,
\begin{eqnarray}
\mathbb{E} [X] & = & \mathbb{E} [X| TT] \mathbb{P}(TT) + \mathbb{E} [X| HH] \mathbb{P}(HH) \\
&& + \mathbb{E} [X| TH] \mathbb{P}(TH) + \mathbb{E} [X| HT] \mathbb{P}(HT) \\
& = & 2 \big( \frac{1}{4} \big) + 2 \big( \frac{1}{4} \big) + \big( 2+ \mathbb{E} [X] \big) \big( \frac{1}{4} \big) + \big( 2+ \mathbb{E} [X] \big) \big( \frac{1}{4} \big) \\
& = & 2+ \frac{1}{2} \mathbb{E} [X],
\end{eqnarray}
which gives
$$ \mathbb{E} [X] = 4.$$
However, the answer should be $3$. Is there a problem with this approach?
Best Answer
The computation for $E[X|TH]$ and $E[X|HT]$ is wrong. It should be: $$\ E[X|TH]=2+1(P(H))+(E[X|HT]-1)P(T)\\ E[X|HT]=2+1(P(T))+(E[X|TH]-1)P(H)\\ \implies E[X|TH] = E[X|HT]=4 $$ Basically, the game gets over if you get THH or HTT. You need not wait till THHH or THTT.
Hint: To get $E[X|TH]$ condition it on the third toss and use $E[X|THT]=1+E[X|HT]$