Flips until the pattern heads-tails-heads appears

Question

You flip a fair coin and watch the running sequence of outcomes. You stop the first time the last three flips spell out H, T, H in that order.

On average, how many flips does it take for the pattern HTH to first appear?

Accepted Answer

Track how much of the target HTH your recent flips already match. The states are: S0 (no useful progress), S1 (last flip matches "H"), S2 (last two match "HT"), and done (S3 = HTH). Let ei be the expected remaining flips from state Si, with e3 = 0. The subtle part is what a "wrong" flip does, because a failed attempt can still leave a partial match: - From S0: H goes to S1, T stays at S0. - From S1 (have H): T advances to S2; H keeps you at S1 (the new H is a fresh start of "H"). - From S2 (have HT): H completes HTH (done); T gives "HTT", whose ending matches nothing, so back to S0. Each flip…

Flips until the pattern heads-tails-heads appears

Your answer

More Probability questions