Flips until the pattern heads-heads-heads appears

Question

You flip a fair coin until the last three flips are H, H, H. On average, how many flips does it take for HHH to first appear?

Accepted Answer

Track your progress toward HHH by how many trailing heads you have: S0, S1, S2, and done (S3). Let ei be the expected remaining flips, e3 = 0. Here a miss is brutal: any tail contains no useful prefix of HHH, so it always sends you back to S0. - From S0: H to S1, T stays S0. - From S1: H to S2, T to S0. - From S2: H completes HHH (done), T to S0. e0 = 1 + 	frac12 e1 + 	frac12 e0, \quad e1 = 1 + 	frac12 e2 + 	frac12 e0, \quad e2 = 1 + 	frac12 \cdot 0 + 	frac12 e0. From the first, e0 = 2 + e1. Substitute e2 = 1 + 	frac12 e0 into e1 = 1 + 	frac12 e2 + 	frac12 e0 = 1 + 	frac12(1 + 	fra…

Flips until the pattern heads-heads-heads appears

Your answer

More Probability questions