Coin Flips: HH vs HT: Puzzle and Step-by-Step Solution
Probability
Medium
Reported at Jane Street, SIG, Citadel, Optiver
The puzzle
You flip a fair coin until you see two heads in a row (HH). How many flips do you expect to need? How does that compare with flipping until you see a head followed by a tail (HT)?
Short answer: HT takes 4 flips on average; HH takes 6.
Step 1: HT: two waits for a single outcome
To see HT you first need a head. The number of flips until the first head is geometric with success probability 1/2, so it takes 2 flips on average.
Once you have a head, you are waiting for a tail. Any further heads do not hurt, because you are still sitting on a head. So the wait for the tail is again geometric with mean 2. Total: 2 + 2 = 4 flips.
Step 2: HH: a failure sends you back to the start
Use first-step analysis. Let E be the expected number of flips to see HH from scratch. The first flip is T with probability 1/2: you have used 1 flip and are back to the start, so this branch costs 1 + E.
The first two flips are HT with probability 1/4: you have used 2 flips and are back to the start, cost 2 + E. The first two are HH with probability 1/4: you are done in 2 flips. So E = 1/2 (1 + E) + 1/4 (2 + E) + 1/4 × 2.
Expand: E = 1/2 + E/2 + 1/2 + E/4 + 1/2 = 3/2 + 3E/4. So E/4 = 3/2 and E = 6.
Step 3: Why the two answers differ
In any long sequence of flips, HH and HT each appear in a given position with probability 1/4, so they are equally frequent. But HH overlaps itself: occurrences of HH cluster together (HHH contains two), so the gaps between clusters are longer. HT cannot overlap itself, so its occurrences are spread evenly. Same frequency, different waiting time.
A general shortcut, from the theory of pattern matching, adds 2^k for every k at which the pattern's prefix of length k equals its suffix of length k. For HH: k = 1 and k = 2 both match, giving 2 + 4 = 6. For HT only k = 2 matches, giving 4.
Step 4: The race follow-up
If you race HH against TH, which appears first? HH only wins if the first two flips are HH, probability 1/4. Any T before the first HH means a TH must come before it, because the first H after that T completes TH. So TH wins with probability 3/4, even though the two patterns are equally frequent.
Why interviewers ask it
Set up first-step analysis cleanly and explain the overlap intuition. Firms often chain this into the race question to see whether you reason or just recall.
Knowing the proof is half of it. Work Coin Flips: HH vs HT interactively, then take it under a clock with the rest of the Outcry simulators.