Communications of the ACM

Last byte

Puzzled: Solutions and Sources

A coin is flipped repeatedly. How long must you wait, on average, before you see a particular head-tail sequence of length five? Any fixed sequence has probability 1/25 = 1/32 of being observed in a given five flips, so the answer is 32, right? Not so fast. Overlapping causes problems. What is true is that in an infinite sequence of random flips, the average distance between one occurrence and the next of any fixed sequence is 32. But suppose the sequence is HHHHH. Such an occurrence would provide a huge "head start" (sorry) to the next occurrence. If the next flip is a tail, you must start over, but if a head, a new occurrence has already taken place. If X is the average time needed to get HHHHH starting fresh, the average of 1+X and 1 is 32. Solving for X yields a startlingly high 62 flips. To reduce your expected dues to \$32, you must pick a sequence whose occurrence gives no head start to the next occurrence. HHHTT is one of 10 sequences with this property.

2. Decline the privilege

You and your opponent choose different length-five head-tail sequences, with the first to occur determining the winner. If possible, decline the "privilege" of picking first; whatever the first chooser chooses, the second can do much better. Worst case: you pick HHHHH, your opponent picks THHHH, and you are dead meat unless the flips begin with five heads. In general, if you pick VWXYZ your opponent crushes you by picking UVWXY, with the right choice of U. If my calculations are correct, you can do no better than, say, HHTHT (one of the good choices in Puzzle 1). Even then, your opponent counters with HHHTH, winning two times out of three. Does it bother you that your opponent has a big advantage, even though the average waiting time for your sequence is less?

Godmar Back

There are actually 12, not 10 sequences of length 5 with the property that the expected number of coin flips is 32 before the sequence appears first.

Joseph Skudlarek

Actually, one can do better than a 0.33333 (1 in 3) chance of winning if they have to go first, with the winning sequence being the first one to occur. A best first choice is HTTHH; then, the best your adversary can do is choose THTTH, for a probability of success for you of 0.34615, so you win more often than 1 out of 3.

Create a Web Account

If you are already an ACM member, Communications subscriber, or Digital Library subscriber, please set up a web account to access premium content on this site.

Join the ACM

Become a member to take full advantage of ACM's outstanding computing information resources, networking opportunities, and other benefits.

Subscribe to Communications of the ACM Magazine

Get full access to 50+ years of CACM content and receive the print version of the magazine monthly.