Heads in a Row

You flip a fair coin until you see $n$ heads in a row. What is the expected number of flips?

Reveal solutionHide solution

#Build the streak one rung at a time

Let $E_n$ be the expected number of flips to reach a run of $n$ heads. To get there, first reach a run of $n-1$ , which takes $E_{n-1}$ flips, then flip once more. With probability $\tfrac{1}{2}$ it is heads and the run is complete; with probability $\tfrac{1}{2}$ it is tails, which wipes the streak back to zero and leaves you needing a fresh $E_n$ flips. So

E_n = E_{n-1} + 1 + \tfrac{1}{2}\cdot 0 + \tfrac{1}{2}\,E_n. \tag{1}

#Solve the recursion

Rearranging gives $\tfrac{1}{2}E_n = E_{n-1} + 1$ , that is $E_n = 2E_{n-1} + 2$ . Starting from $E_0 = 0$ this unrolls to

E_n = 2^{\,n+1} - 2. \tag{2}

The state is the current run of heads. A head climbs one rung, a tail drops all the way back to 0, and the run is complete at n. Because every tail erases the whole streak, the expected wait doubles at each new rung.

#Read it off

Each extra head roughly doubles the wait, because one tail at the wrong moment costs the entire run and sends you back to the start. For three heads in a row, $E_3 = 2^4 - 2 = 14$ flips, and for ten in a row it is already $2046$ .