A curious puzzle by Dartmouth mathematician Peter Winkler: You’ve just joined the Coin Flippers of America, and fittingly the amount of your dues will be decided by chance. You’ll name a head-tail sequence of length 5, and then a coin will be flipped until that sequence appears in five consecutive flips. Your dues will be the total number of flips in U.S. dollars; for instance, if you choose HHHHH and it takes 36 flips to produce a run of five heads, then your annual dues will be $36. What sequence should you pick?

At first it seems that it shouldn’t matter — any fixed sequence should have the probability (1/2)⁵, or 1/32. But “Not so fast,” Winkler writes. “Overlapping causes problems.” It is true that in an infinite sequence of random flips, the average distance between one occurrence and the next of any fixed sequence is 1/32. But if you choose HHHHH (for example), one occurrence of this outcome gives a huge head start to the next — if the next flip is a tail, then you’re starting over cleanly, but if it’s a head then you’ve already produced the next occurrence.

“If X is the average time needed to get HHHHH starting fresh, the average of 1 + X and 1 is 32,” Winkler writes. “Solving for X yields a startlingly high 62 flips.” To get your expected dues down to $32, you need to pick a sequence where this “head start” effect doesn’t obtain. There are 10 such sequences; one is HHHTT.

(Peter Winkler, “Coin Flipping,” Communications of the ACM 56:11 [November 2013], 120.)