Expected Flips for Consecutive Heads
You have a fair coin. Let $X_i$ be the number of flips required to see $i$ consecutive heads for the first time.
Compute $\mathbb{E}[X_1]$, $\mathbb{E}[X_2]$, and $\mathbb{E}[X_3]$.
For each, set up a recursive equation and solve it. Can you spot the pattern and conjecture a formula for general $\mathbb{E}[X_k]$?
Hints
- Think about what happens to your "streak" of consecutive heads when you flip a tails -- you lose all progress and must start over from scratch.
- Set up a recursive equation by conditioning on the next flip. The key states are the number of consecutive heads you have accumulated so far.
- Use the shortcut: $E_k = E_{k-1} + 1 + \frac{1}{2}E_k$, which says "first reach $k-1$ consecutive heads, then flip once more -- if tails, restart entirely."
Worked Solution
How to Think About It: This is a classic first-passage-time problem with a Markov chain flavor. At any point, you are in some state representing "how many consecutive heads you have built up so far." A single tail resets you to zero. The key structural insight is that getting to $k$ consecutive heads means first getting to $k-1$ consecutive heads, then flipping one more head -- but if that extra flip is tails, you have burned all your progress and must restart from scratch. This nesting creates a clean recursive structure.
Quick Estimate: For $\mathbb{E}[X_1]$, you just need one head -- that is a geometric with $p = 1/2$, so $\mathbb{E}[X_1] = 2$. For $\mathbb{E}[X_2]$, once you have your first head (cost: 2 flips on average), you flip again. Half the time you get a second head and you are done. Half the time you get tails and restart. So the answer should be a bit more than $2 \times 2 = 4$, but each restart costs the full $\mathbb{E}[X_2]$ again, so it will be higher. Guessing around 6. For $\mathbb{E}[X_3]$, by similar logic, somewhere around 14. Let's verify.
Approach: Define states by the current streak of consecutive heads. Set up recursive equations using the law of total expectation, conditioning on the next flip.
Formal Solution:
*Computing $\mathbb{E}[X_1]$:*
Let $E_1 = \mathbb{E}[X_1]$. On any flip, with probability $1/2$ we get heads (done in 1 flip), and with probability $1/2$ we get tails (wasted 1 flip, restart):
$$E_1 = \frac{1}{2}(1) + \frac{1}{2}(1 + E_1)$$
$$E_1 = 1 + \frac{1}{2}E_1 \implies \frac{1}{2}E_1 = 1 \implies E_1 = 2$$
*Computing $\mathbb{E}[X_2]$:*
Let $E_2 = \mathbb{E}[X_2]$. Condition on the first flip:
- Tails (prob $1/2$): wasted 1 flip, restart. Contributes $1 + E_2$.
- Heads (prob $1/2$): we have 1 consecutive head. Now flip again:
- Heads (prob $1/2$): done in 2 flips total.
- Tails (prob $1/2$): wasted 2 flips, restart. Contributes $2 + E_2$.
$$E_2 = \frac{1}{2}(1 + E_2) + \frac{1}{2}\left[\frac{1}{2}(2) + \frac{1}{2}(2 + E_2)\right]$$
$$E_2 = \frac{1}{2} + \frac{1}{2}E_2 + \frac{1}{2} + \frac{1}{4}E_2 = 1 + \frac{3}{4}E_2$$
Solving: $\frac{1}{4}E_2 = 1$, so
$$\boxed{E_2 = 6}$$
Alternatively, think of it this way: to get 2 consecutive heads, first get 1 consecutive head (expected cost $E_1 = 2$ flips), then flip once more. With probability $1/2$ you get heads and you are done. With probability $1/2$ you get tails and must restart entirely. So:
$$E_2 = E_1 + 1 + \frac{1}{2}(0) + \frac{1}{2}(E_2) = E_1 + 1 + \frac{1}{2}E_2$$
$$E_2 = 2(E_1 + 1) = 2(2 + 1) = 6 \checkmark$$
*Computing $\mathbb{E}[X_3]$:*
Using the same recursive shortcut: to get 3 consecutive heads, first get 2 consecutive heads (expected cost $E_2 = 6$), then flip once more. With probability $1/2$ you get heads (done). With probability $1/2$ you get tails (restart from scratch):
$$E_3 = E_2 + 1 + \frac{1}{2}E_3$$
$$\frac{1}{2}E_3 = E_2 + 1 = 7 \implies E_3 = 14$$
$$\boxed{E_3 = 14}$$
*General formula:*
The recurrence $E_k = 2(E_{k-1} + 1)$ with $E_0 = 0$ solves to:
$$E_k = 2^{k+1} - 2$$
You can verify: $E_1 = 4 - 2 = 2$, $E_2 = 8 - 2 = 6$, $E_3 = 16 - 2 = 14$, $E_4 = 32 - 2 = 30$.
Answer: $\mathbb{E}[X_1] = 2$, $\mathbb{E}[X_2] = 6$, $\mathbb{E}[X_3] = 14$. The general formula is $\mathbb{E}[X_k] = 2^{k+1} - 2$.
Intuition
This problem illustrates a fundamental pattern in first-passage-time problems with "catastrophic resets." The streak of consecutive heads is fragile -- a single tails destroys all accumulated progress and sends you back to zero. This asymmetry between building (one head at a time) and losing (everything at once) is why the expected time grows exponentially: each additional consecutive head doubles the expected wait, plus a constant. The recurrence $E_k = 2(E_{k-1} + 1)$ captures this perfectly.
This structure shows up constantly in quant interviews and in practice. Any process where you need a sustained run of favorable outcomes -- a trading strategy that requires $k$ consecutive winning days before triggering a signal, a system that must pass $k$ sequential checks -- will exhibit this exponential blowup. The practical lesson: requiring long unbroken streaks is extremely expensive in expectation, and robust designs should avoid conditioning on them whenever possible.