First-Step Analysis: Conditioning on What Happens Next

You flip a fair coin repeatedly. What's the expected number of flips until you see heads? Everyone knows the answer is 2 — but why, in a way that generalises to harder versions where the intuition runs out? What's the expected number of flips until you see two heads in a row? That one stops most people cold if they try to reason about it directly.

Try the two-heads-in-a-row version yourself before reading on — count out a few sequences by hand if it helps.

The trap: trying to enumerate every possible sequence

The direct approach — list every sequence of flips that ends in the target pattern, weight each by its probability and length, and sum — is exactly what a computer would do and exactly what a human shouldn't. The sequences form an infinite, awkwardly-structured set (HH, THH, TTHH, HTHH, …) and summing an infinite series by hand under interview pressure is a losing game.

The fix is to stop thinking about the whole future and instead ask: what happens on just the first step, and where does that leave me?

Worked example: expected flips to first heads, the simple case

Let $E$ be the expected number of flips until the first heads. On the very first flip, two things can happen: heads, with probability 1/2, in which case you're done after exactly 1 flip; or tails, with probability 1/2, in which case you've used 1 flip and are now — because the coin has no memory — in exactly the same situation you started in, needing $E$ more flips on average.

$$E = \frac12(1) + \frac12(1+E).$$

In words: half the time you finish in one flip; half the time you spend one flip and then face the identical problem again. Solving: $E = \frac12 + \frac12 + \frac12 E \Rightarrow \frac12 E = 1 \Rightarrow E = 2$. No infinite sum, just one equation with one unknown, because the recursive structure of the problem let $E$ appear on both sides.

Worked example: expected flips until two heads in a row

Now the harder version. The key realisation is that a single state isn't enough — you need to track how close you are, so define two unknowns: $E_0$, the expected number of additional flips needed when your current streak of consecutive heads is 0 (including the very start, or right after a tails), and $E_1$, the expected number of additional flips needed when you currently have exactly one head in a row.

From state 0: flip once. Heads (prob 1/2) moves you to state 1, having used 1 flip. Tails (prob 1/2) keeps you in state 0, having used 1 flip.

$$E_0 = 1 + \frac12 E_1 + \frac12 E_0.$$

From state 1: flip once. Heads (prob 1/2) means you've hit two in a row — done. Tails (prob 1/2) breaks the streak, sending you back to state 0.

$$E_1 = 1 + \frac12(0) + \frac12 E_0.$$

In words: each equation says "spend one flip, then land in whichever state the coin sends you to, weighted by its chance." Substitute the second into the first: $E_0 = 1 + \frac12\left(1+\frac12 E_0\right) + \frac12 E_0 = 1 + \frac12 + \frac14 E_0 + \frac12 E_0$, so $E_0 - \frac34 E_0 = \frac32$, giving $\frac14 E_0 = \frac32$, so $E_0 = 6$. It takes 6 flips on average to see HH — noticeably more than double the 2 flips for a single head, because a broken streak forces you all the way back to state 0, not partway.

The transferable technique

First-step analysis turns "sum an infinite or awkward set of futures" into "write one equation per state, using the fact that the unknown reappears on the right-hand side." The steps are always the same: define enough states to capture everything relevant to the future (often "how much progress have I made"), write one equation per state by conditioning on the very next step, and solve the resulting linear system. This is the exact machinery behind gambler's-ruin durations, random-walk return probabilities, and every "expected time until pattern X" question — recognise the shape and the algebra does the rest.