Learn / Library / Probability

Waiting for a long run

ProbabilityHard

A fair coin is tossed repeatedly with independent tosses. What is the expected number of tosses until $3$ heads in a row appear for the first time?

Checking an answer needs JavaScript. The hint and the solution open without it.

Hint

Define states by the current length of the heads streak and write linear equations for the expected remaining tosses.

Solution

Let $E 0$ , $E 1$ , $E 2$ be the expected additional tosses when the current streak of heads has length $0$ , $1$ , $2$ .
Conditioning on the next toss gives $E 2 = 1 + E 0 \div 2$ , $E 1 = 1 + E 2 \div 2 + E 0 \div 2$ and $E 0 = 1 + E 1 \div 2 + E 0 \div 2$ .
The last equation simplifies to $E 0 = 2 + E 1$ .
Substituting the first equation into the second gives $E 1 = \frac{3}{2} + 3 \times E 0 \div 4$ , and with $E 0 = 2 + E 1$ this yields $E 1 = 12$ .
Therefore $E 0 = 14$ .

Answer: $14$