How many coin flips does it take, on average, to see two consecutive heads (HH)? Most people guess 4. The correct answer is 6. How many to see HTH? Most people guess 6 or 8. The correct answer is 10. The difference between these two results reveals something fundamental about how overlapping patterns affect expected stopping times.
Expected Flips for HH (Markov Chain)
Define states: Start (S), one H seen (H), absorbing state HH. Let E_S and E_H be the expected flips to absorption from each state.
From S: E_S = 1 + (1/2)E_H + (1/2)E_S
From H: E_H = 1 + (1/2)(0) + (1/2)E_S
Solving: E_H = 1 + E_S/2
E_S = 1 + (1/2)(1 + E_S/2) + E_S/2
E_S = 1 + 1/2 + E_S/4 + E_S/2
E_S/4 = 3/2 → E_S = 6
Expected Flips for HTH
States: S, H (seen H), HT (seen HT), absorbing HTH. The critical difference: if we are in state HT and flip H to reach HTH — we are done. But if we flip H while in state H (trying to extend H to HT), we stay in state H (the new H starts a fresh potential HT sequence). This overlap structure inflates the expected time.
E_S = 1 + (1/2)E_H + (1/2)E_S E_H = 1 + (1/2)E_H + (1/2)E_HT E_HT = 1 + (1/2)E_HTH + (1/2)E_S = 1 + 0 + (1/2)E_S Solving the system: E_S = 10
HTH takes 10 flips on average versus 6 for HH. The reason: HH "reuses" its prefix — if you see H while waiting for the second H, you have not wasted that flip. HTH cannot reuse its prefix in the same way; a misfire often sends you back to the start.
Python Simulation
import random
def flips_to_pattern(pattern):
seen = []
target = list(pattern)
flips = 0
while seen[-len(target):] != target:
seen.append(random.choice(['H', 'T']))
flips += 1
return flips
n = 100_000
hh_avg = sum(flips_to_pattern('HH') for _ in range(n)) / n
hth_avg = sum(flips_to_pattern('HTH') for _ in range(n)) / n
print(f"E[HH]: {hh_avg:.2f} (exact: 6)")
print(f"E[HTH]: {hth_avg:.2f} (exact: 10)")
Read the full article with complete state-transition matrix derivation →
Top comments (0)