Flips until the pattern tails-heads-tails-heads appears

Question

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

Accepted Answer

Track how many leading characters of THTH your recent flips match: S0, S1 (T), S2 (TH), S3 (THT), done (S4). Let ei be expected remaining flips, e4 = 0. The key overlaps come from the pattern repeating "TH": - From S1 (T): H to S2; T gives "TT", last char T, stays S1. - From S2 (TH): T to S3; H gives "THH", ending matches nothing, back to S0. - From S3 (THT): H completes THTH (done); T gives "THTT", last char T, so to S1. - From S0: T to S1, H stays S0. e0 = 1 + 	frac12 e1 + 	frac12 e0, \quad e1 = 1 + 	frac12 e2 + 	frac12 e1, \quad e2 = 1 + 	frac12 e3 + 	frac12 e0, \quad e3 = 1 + 	frac…

Flips until the pattern tails-heads-tails-heads appears

Your answer

Discussion

Learn the concepts

Related questions