Suppose you’re flipping a fair coin and you stop the moment you see two heads in a row. Let $N$ be the number of flips that takes. On average, how big is $N$? In other words, what is $E[N]$?
In a previous post, we computed the mean hitting time of a state in a Markov chain by conditioning on the first transition $X_1$, a trick we’ll call one-step recursion. In this post, we’ll apply the same trick to compute $E[N]$. We’ll work with a general probability $p$ of heads, and only at the end plug in $p = 1/2$ for the fair-coin case.
There’s one big difference in style between this post and the previous one. In the previous post, we were careful to justify each step rigorously, naming the law of total expectation, the Markov property, time-homogeneity, and so on. This post leans much more heavily on intuition.
We won’t write the chain $\mathcal{X} = \lbrace X_0, X_1, \dots\rbrace$ out explicitly, and we won’t invoke the law of total expectation or the Markov property by name. Instead, we’ll just reason directly about what conditional expectations like $E[N \mid HT]$ “should” equal, leaning on the simple observation that observing a tail wipes out any in-progress streak.
Once we have the answer, we’ll go back and look at the problem through the rigorous Markov chain lens. We’ll see that the intuitive manipulations were really the same mean hitting time recursion from the previous post in disguise.
Why bother working intuitively first? Terry Tao has a wonderful short essay, There’s more to mathematics than rigour and proofs, where he describes mathematical maturity as a three-stage progression.
First comes a “pre-rigorous” stage, where you work by intuition and informal manipulation. Then a “rigorous” stage, where you learn to be careful and precise. And finally a “post-rigorous” stage, where intuition comes back, but now you trust it because you know any informal step could be made rigorous if you had to.
Both intuition and rigour matter, and neither replaces the other. Intuition is what lets you guess the right identity, pick a productive way to condition, or notice that two problems are really the same problem in disguise. Rigour is what lets you trust the answer once you have it. The previous post was an exercise in rigour; this one is an exercise in intuition.
Setup and notation
Let $p \in (0, 1)$ be the probability of heads on a single flip. We want $E[N]$, the expected number of flips until we see two heads in a row.
To set up the one-step recursion, we’ll introduce a few conditional expectations, each one indexed by the prefix of flips we’ve already observed:
- $E[N \mid H]$: the expected number of flips until we see two heads in a row given that the first flip has already happened and was heads.
- $E[N \mid T]$: same idea, but the first flip was tails. Because the flips are independent, then the random process of flipping the coin is memoryless, such that $E[N \mid T] = E[N]$.
- $E[N \mid HH]$: the expected number of flips until we see two heads in a row given that the first two flips have already happened and were both heads. Because we’ve already seen two heads, $E[N \mid HH] = 0$.
- $E[N \mid HT]$: the expected number of flips until we see two heads in a row given that the first flip was heads and the second was tails. Again, because the coin flips are indepndent, when we see a tails on the second flip, the streak resets, such that $E[N \mid HT] = E[N]$.
One-step recursion
Now we condition on the first flip. With probability $p$ it’s heads, and with probability $1-p$ it’s tails:
The leading $1$ counts the first flip itself, and the rest counts the expected number of additional flips after that first flip.
From the previous section, $E[N \mid T] = E[N]$, and we can expand $E[N \mid H]$ in $\eqref{EN}$:
From the previous section, $E[N \mid HH] = 0$ and $E[N \mid HT] = E[N]$. So,
Plugging $\eqref{ENH2}$ into $\eqref{EN}$,
That’s one linear equation in one unknown, $E[N]$. Solving for $E[N]$ yields $E[N] = \frac{1 + p}{p^2}$. For a fair coin with $p = 1/2$, $E[N] = 6$. That is, on average, we need to flip the fair coin 6 times to see two heads in a row.
Markov chain interpretation
Equations $\eqref{EN}$ and $\eqref{ENH1}$ are mean hitting time recursions on a 3-state Markov chain. The states are:
- $S_0$: “no head pending”; either we haven’t flipped yet, or the most recent flip was a tail.
- $S_1$: “one head pending”; the most recent flip was a head, but we haven’t seen two in a row yet.
- $S_2$: “two heads in a row”; absorbing.
The transitions are:
- From $S_0$: go to $S_1$ with probability $p$, stay at $S_0$ with probability $1-p$.
- From $S_1$: go to $S_2$ with probability $p$, go back to $S_0$ with probability $1-p$.
- From $S_2$: stay at $S_2$ with probability $1$.
Using the $\tau_{ij}$ notation from the previous post, the mean hitting times of $S_2$ from $S_0$ and $S_1$ are
and equations $\eqref{EN}$ and $\eqref{ENH1}$ are exactly the mean hitting time recursion $\tau_{iS_2} = 1 + \sum_k p_{ik} \cdot \tau_{kS_2}$ (with $\tau_{S_2 S_2} = 0$) instantiated at $i = S_0$ and $i = S_1$. The “memoryless restart” identities $E[N \mid T] = E[N]$ and $E[N \mid HT] = E[N]$ are just the chain’s transitions back into $S_0$.
Conclusion
The same one-step recursion that handled the random walk on a square in the previous post handles this coin-flipping problem too. The only thing that changes is the underlying Markov chain. A 4-state walk on a square gets replaced by a 3-state absorbing chain that tracks the current head streak.
The closed form $E[N] = (1 + p)/p^2$ also generalizes nicely. If you want $k$ heads in a row instead of $2$, you get a $(k+1)$-state absorbing chain, and the same one-step recursion gives you a closed-form mean hitting time of the absorbing state.