Expected Flips for Two Consecutive Heads
You flip a fair coin repeatedly until you see two heads in a row. What is the expected number of flips?
As a follow-up, think about why the sequence $HH$ takes longer on average than $HT$.
Hints
- Think about what "states" you can be in based on your progress toward $HH$. How many distinct states are there before you finish?
- Set up a Markov chain with states for zero progress and one $H$ observed. Write the expected-value equations by conditioning on the next flip from each state.
- From the state with one $H$, you get $e_H = \frac{1}{2}e_0 + 1$. Substitute this into the equation for $e_0$ and solve the resulting linear equation.
Worked Solution
How to Think About It: This is a first-passage-time problem on a small Markov chain. Before writing any equations, think about the states you can be in: you either have zero progress toward $HH$, or your last flip was $H$ and you need one more. Every time you flip tails, you lose all your progress. That "restart" penalty is what makes this take longer than you might guess. A naive thought is "two heads, each takes 2 flips on average, so maybe 4" -- but that ignores restarts. The answer will be higher.
Quick Estimate: On any given pair of consecutive flips, $P(HH) = 1/4$. If the trials were independent (they are not, but as a rough bound), you would need about $1/(1/4) = 4$ "trials" -- but each trial overlaps by one flip, so that suggests something in the range of 4-8 flips. The geometric-style heuristic gives a rough guess around 6. Let's confirm.
Approach: Set up a system of linear equations by conditioning on the current state of the Markov chain.
Formal Solution:
Define two states based on progress toward $HH$:
- State 0: no progress (either we just started, or the last flip was $T$).
- State $H$: the last flip was $H$; one more $H$ finishes the game.
Let $e_0$ = expected flips to reach $HH$ from State 0, and $e_H$ = expected flips to reach $HH$ from State $H$.
From State 0, we flip once:
$$e_0 = \frac{1}{2}(1 + e_0) + \frac{1}{2}(1 + e_H)$$
- Tails ($1/2$): we stay in State 0, having used 1 flip.
- Heads ($1/2$): we move to State $H$, having used 1 flip.
From State $H$, we flip once:
$$e_H = \frac{1}{2}(1 + e_0) + \frac{1}{2}(1)$$
- Tails ($1/2$): we crash back to State 0, having used 1 flip.
- Heads ($1/2$): we are done -- it took 1 flip.
Simplify the second equation:
$$e_H = \frac{1}{2}e_0 + 1$$
Substitute into the first equation:
$$e_0 = 1 + \frac{1}{2}e_0 + \frac{1}{2}e_H = 1 + \frac{1}{2}e_0 + \frac{1}{2}\left(\frac{1}{2}e_0 + 1\right)$$
$$e_0 = 1 + \frac{1}{2}e_0 + \frac{1}{4}e_0 + \frac{1}{2} = \frac{3}{2} + \frac{3}{4}e_0$$
$$\frac{1}{4}e_0 = \frac{3}{2} \implies e_0 = 6$$
Follow-up -- why $HH$ takes longer than $HT$:
The expected time to first see $HT$ is only 4 flips (you can verify with a similar Markov chain). The key difference: when you are in State $H$ and trying to complete $HT$, a tails *finishes* the pattern. But when you are in State $H$ and trying to complete $HH$, a tails *restarts* you. Meanwhile, when trying for $HT$ and you see another $H$, you have not lost progress -- you are still in State $H$. The $HH$ pattern has no such "free retry."
Answer: The expected number of flips is $\boxed{6}$.
Intuition
This is one of the cleanest examples of first-passage times on a Markov chain, and it shows up constantly in quant interviews because it tests whether you can set up states and condition properly. The core technique -- define states based on progress, write one equation per state by conditioning on the next step, solve the system -- generalizes to any pattern-matching problem (consecutive runs, specific sequences, etc.). It is the same machinery behind gambler's ruin, coupon collector variants, and many market microstructure models.
The deeper lesson is the comparison between $HH$ and $HT$. Patterns that can "reuse" partial progress when they fail (like $HT$ -- if you see $HH$ while hunting for $HT$, you still have your $H$) arrive faster than patterns where failure means a full restart (like $HH$ -- a single tails wipes out everything). This asymmetry is the basis for Penney's game and has analogs in trading: a strategy that can partially recycle losing positions into the next setup has a shorter expected time-to-profit than one where every loss is a clean reset.