skip to content

What is the expected number of fair coin flips until the first HH, by first-step conditioning?

level: middleimportance: must knowfreq 50%

answer

  1. condition on the very next flip
  2. states track surviving progress
  3. some failures cost more than others
  4. define a state for trailing head
  5. two linear equations, two unknowns

basics

~20 s

Six flips on average. Condition on the next flip using two states — no progress, or a trailing head. Solving E0 = 1 + 0.5E1 + 0.5E0 and E1 = 1 + 0.5*E0 gives E1 = 4 and E0 = 6.

solid answer

~50 s

The answer is 6. Set up states by how much progress survives: state 0 means the last flip was a tail or nothing has been flipped, state 1 means the last flip was a head. Let `E0` and `E1` be the expected additional flips from each. First-step conditioning gives `E0 = 1 + 0.5*E1 + 0.5*E0` (a head advances you, a tail keeps you where you are) and `E1 = 1 + 0.5*0 + 0.5*E0` (a head finishes, a tail throws away the progress). Solving: `E0 = 2 + E1` and `E1 = 1 + 0.5*E0`, so `E0 = 6` and `E1 = 4`. The contrast is the real point: waiting for HT takes only 4 flips, because a head following a head still leaves you one flip from HT, while a tail following a head destroys HH progress completely.

code

python · 15 lines
python
import random

def flips_until(pattern):
    seen = ""
    count = 0
    while not seen.endswith(pattern):
        seen += random.choice("HT")
        count += 1
    return count

random.seed(0)
trials = 200000
for pattern in ("HH", "HT"):
    total = sum(flips_until(pattern) for _ in range(trials))
    print(pattern, round(total / trials, 3))

go deeper

for a junior

Know that the answer is a small number found by setting up equations rather than by inverting a probability, and be able to follow the two-state argument when it is walked through with you.

for a middle

Set up and solve the system yourself without prompting, naming the states by how much progress survives a bad flip, and remember the +1 for the flip you spend on each transition.

for a senior

Explain the HH-versus-HT asymmetry in terms of self-overlap and recovery cost, and generalise cleanly to a biased coin or a longer run without re-deriving from scratch.

for a principal

Recognise the pattern as a template: any expected-time question with a small memoryless state space collapses to a linear system, and be able to say when the state space stops being small enough for that to work.

## The technique: condition on the first step The general move is to write the expected value you want in terms of expected values from the states you can reach after one step. If `T` is the total number of flips and `F` is the outcome of the next flip, the law of total expectation says ``` E[T] = E[T | F = H] * P(H) + E[T | F = T] * P(T) ``` Because the coin has no memory, everything after that flip depends only on **how much of the target pattern is still intact**. That turns an infinite-horizon problem into a small system of linear equations. ## States for the pattern HH Only the tail end of the sequence matters, and only up to one character: - **State 0** — nothing flipped yet, or the last flip was a tail. No usable progress. - **State 1** — the last flip was a head. One more head finishes. - **Done** — HH has appeared. Let `E0` be the expected number of *further* flips from state 0 and `E1` from state 1. From state 0 you always spend one flip. With probability 1/2 it is a head and you move to state 1; with probability 1/2 it is a tail and you are back in state 0: ``` E0 = 1 + 0.5 * E1 + 0.5 * E0 ``` From state 1 you again spend one flip. With probability 1/2 it is a head and you are finished (zero further flips); with probability 1/2 it is a tail and you fall all the way back to state 0: ``` E1 = 1 + 0.5 * 0 + 0.5 * E0 ``` ## Solving The first equation gives `0.5 * E0 = 1 + 0.5 * E1`, i.e. `E0 = 2 + E1`. Substituting the second, `E0 = 2 + 1 + 0.5 * E0`, so `0.5 * E0 = 3` and `E0 = 6`. Back-substituting, `E1 = 1 + 3 = 4`. The answer to the question — starting from scratch — is `E0 = 6`. ## The HT contrast, and why it is the interesting half Run the same construction for the pattern HT. State 1 again means "the last flip was a head", but now a *head* is the harmless failure: ``` E1 = 1 + 0.5 * 0 + 0.5 * E1 (a tail finishes; another head keeps you in state 1) E0 = 1 + 0.5 * E1 + 0.5 * E0 ``` The first gives `E1 = 2`, and the second gives `E0 = 2 + E1 = 4`. So HT arrives after 4 flips on average and HH after 6, even though **in any fixed pair of consecutive flips both patterns have probability 1/4**. The asymmetry is about **overlap and recovery**, not about how likely the pattern is in a single window. HH can overlap itself: the second character of a successful HH is also a valid start for the next one. That self-overlap is what makes a failure expensive — when you are one head short and get a tail, the head you were holding is worthless and you restart from nothing. HT does not overlap itself, so a failure (another head) leaves you exactly as well-placed as you were. A related warning: do not compute the answer as the reciprocal of the per-pair probability. The consecutive two-flip windows in a sequence overlap, so they are not separate independent attempts, and reasoning as if they were gives 4 for HH — which is wrong. ## Biased coins and longer patterns With `P(head) = p` and `q = 1 - p`, the same two equations become `E0 = 1 + p*E1 + q*E0` and `E1 = 1 + q*E0`. Solving gives ``` E[flips until HH] = 1/p + 1/p^2 ``` which returns `2 + 4 = 6` at `p = 0.5`, a good check. Note it blows up quadratically as the coin becomes tail-heavy. For a run of `n` heads on a fair coin, one state per prefix length gives ``` E = 2 + 4 + 8 + ... + 2^n = 2^(n+1) - 2 ``` so HHH takes 14 flips on average and HHHH takes 30. Each extra required head roughly doubles the wait, because every near-miss discards the entire run. ## How to present it in an interview 1. Say up front that you will condition on the next flip. 2. Name the states in terms of *surviving progress*, not raw flip counts — that is the insight the interviewer is testing. 3. Write the equations, solve them, and state the answer. 4. Volunteer the HT comparison and the overlap explanation. Candidates who stop at 6 answer the question; candidates who explain why HH is slower than HT answer the reason it was asked. ## Sanity checks - Every expected value must exceed 2 (you cannot finish in fewer than two flips). - Making the coin more head-heavy must lower the HH answer. - A simulation converges to 6 and 4 quickly; a few hundred thousand runs separates them unambiguously.

  • What is the expected wait for HT, and why is it shorter?
    Four flips. With a trailing head, a tail finishes HT and another head leaves you exactly where you were, so `E1 = 1 + 0.5*E1` gives `E1 = 2` and `E0 = 4`. For HH the failure flip is a tail, which erases the head you were holding and sends you back to the start. Same per-pair probability, very different recovery cost.
  • How does the answer change for a biased coin with P(head) = p?
    The equations become `E0 = 1 + p*E1 + (1-p)*E0` and `E1 = 1 + (1-p)*E0`, which solve to `E[flips until HH] = 1/p + 1/p^2`. At `p = 0.5` that is 2 + 4 = 6, matching the fair case, and it grows quadratically as `p` shrinks because near-misses become both more frequent and more costly.
  • Does the same recursion extend to a three-head run, HHH?
    Yes — add one state per prefix length: no progress, one trailing head, two trailing heads. On a fair coin the expected wait is `2 + 4 + 8 = 14`, and for a run of n heads it is `2^(n+1) - 2`. Each additional required head roughly doubles the wait, since any tail discards the whole run.
  • Why is it wrong to answer 4 by inverting the probability of HH in one pair of flips?
    That treats the sequence as a series of separate two-flip attempts, but consecutive windows overlap and share a flip, so they are not independent trials. The overlap structure is exactly what distinguishes HH from HT, and any argument that ignores it must give both patterns the same answer — which is demonstrably false.

It is like climbing a ladder where one rung is greased. For HH, slipping drops you to the floor; for HT, slipping leaves you standing on the same rung.

saying these in an interview costs you the question

  • Says HH and HT take equally long because each pair has probability 1/4
  • Answers 4 by inverting the probability of HH in a single pair
  • Forgets that a tail after a head erases all HH progress
  • Treats overlapping two-flip windows as independent attempts
  • Defines states by flip count instead of surviving progress
  • Omits the +1 for the flip spent in each transition

context

resolving links…