Expected flips to get three heads in a row

Question

You flip a fair coin repeatedly. What is the expected number of flips until you first see three heads in a row (HHH)?

Accepted Answer

Track progress with states S0, S1, S2 (current run of 0, 1, or 2 trailing heads). Let E0, E1, E2 be the expected remaining flips. A tail always drops you back to S0. E0 = 1 + 	frac12 E1 + 	frac12 E0, E1 = 1 + 	frac12 E2 + 	frac12 E0, E2 = 1 + 	frac12 \cdot 0 + 	frac12 E0. From the first, E0 = 2 + E1. Substitute E2 = 1 + 	frac12 E0 into the second: E1 = 1 + 	frac12\left(1 + 	frac12 E0ight) + 	frac12 E0 = 1.5 + 0.75 E0. Then E0 = 2 + 1.5 + 0.75 E0, so 0.25 E0 = 3.5 and E0 = 14. Why the jump from 6 to 14. HHH self-overlaps at lengths 1 and 2 (its prefix H equals its suffix H, and HH …

Expected flips to get three heads in a row

Your answer

More Probability questions