10 Consecutive Heads

Build the run one head at a time. Let $T_k$ be the expected number of flips until you first have $k$ heads in a row. How is $T_{k+1}$ related to $T_k$?

To get $k + 1$ in a row, you must first get $k$ in a row, then flip once more. Heads: done. Tails: you are back at the start and still need $T_{k+1}$ flips on average.

Let $T_k$ be the expected number of flips until you first see $k$ heads in a row, with $T_0 = 0$.

Step 1: From $k$ heads in a row to $k + 1$. To get $k + 1$ heads in a row, you first need $k$ in a row, which takes $T_k$ flips on average. Then you flip once more:

• Tails (probability $\tfrac12$): the run is broken. You have used $T_k + 1$ flips and are back at the start, so you still need $T_{k+1}$ more flips on average. Total: $T_k + 1 + T_{k+1}$.
• Heads (probability $\tfrac12$): you now have $k + 1$ in a row and you are done. Total: $T_k + 1$.

Averaging the two cases:

Step 2: Simplify. The right side is $T_k + 1 + \tfrac12 T_{k+1}$. Subtract $\tfrac12 T_{k+1}$ from both sides and multiply by $2$:

Step 3: Solve. Start from $T_0 = 0$ and apply the rule ten times:

Each value is $2$ less than a power of $2$: $T_k = 2^{k+1} - 2$. (Adding $2$ to both sides of the rule gives $T_{k+1} + 2 = 2(T_k + 2)$, so $T_k + 2$ doubles every step.)

Check: $T_1 = 2$ is the familiar expected wait for a single head.

Answer: