A fair coin is flipped until two heads appear in a row. Set up the recurrence over the state of the last flip, solve it, and give the expected number of flips.

A fair coin is flipped until two heads appear in a row. Set up the recurrence over the state of the last flip, solve it, and give the expected number of flips.

Approach: Define the expected remaining flips from each of the states no-progress and one-head, write one linear equation for each by conditioning on the next flip, then solve the two by two system.

6. Let E_0 be the expected number of remaining flips with no current run and E_1 with exactly one trailing head. Conditioning on the first step gives E_0 = 1 + 0.5 E_1 + 0.5 E_0 and E_1 = 1 + 0.5 * 0 + 0.5 E_0, where the zero is the absorbing state reached by a second head. The first recurrence relation simplifies to 0.5 E_0 = 1 + 0.5 E_1, so E_0 = 2 + E_1. Substituting into the second gives E_1 = 1 + 0.5(2 + E_1), so 0.5 E_1 = 2 and E_1 = 4, hence E_0 = 6. The general answer for k heads in a row is 2^{k+1} - 2, which this matches at k = 2. The contrast with the pattern HT, whose expected value is 4, comes from the overlap structure: a failed attempt at HH after a head still leaves no progress, while HT never wastes a head.

Follow-up: What is the expected wait for the pattern HTH, and why do two patterns of equal length differ in expected wait?

Key concepts: recurrence relation, conditioning on the first step, expected value, absorbing state.