Expected flips until the pattern HTH

Question

You flip a fair coin repeatedly. What is the expected number of flips until the pattern HTH appears? Compare it with HTT.

Accepted Answer

Track the longest suffix of your flips that is a prefix of the target. For HTH the states are "" (nothing), "H", and "HT"; reaching "HTH" finishes. E{\varnothing} = 1 + 	frac12 EH + 	frac12 E{\varnothing}, \quad EH = 1 + 	frac12 EH + 	frac12 E{HT}, \quad E{HT} = 1 + 	frac12\cdot 0 + 	frac12 E{\varnothing}. The transitions to watch: from "H", a tail advances to "HT" and a head keeps you at "H". From "HT", a head finishes, but a tail gives "...HTT", whose longest useful suffix is empty, so you fall all the way back to "". Solve. The first equation gives E{\varnothing} = 2 + EH. The third …

Expected flips until the pattern HTH

Your answer

More Probability questions