Computing Applications Last byte

Puzzled: Solutions and Sources

Last month (November 2013) we posted three tricky puzzles concerning coin flipping. Here, we offer solutions to all three. How did you do?
  1. 1. No head start
  2. 2. Decline the privilege
  3. 3. A good bet
  4. Author
  5. Footnotes
flipping coin

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.

Back to Top

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?

Back to Top

3. A good bet

You had to decide whether to risk $1 to win $19 by flipping exactly 50 heads in 100 flips. How likely is flipping 50 heads on the nose? A good estimate for flipping precisely n heads in 2n flips is 1/√(πn/2). Sheesh. What does π have to do with it? Anyway, with our modest numbers, a computer does the exact calculation easily; the number of ways to flip exactly 50 heads is "100 choose 50," or 100!/(50!)2, so the total number of outcomes for 100 flips is 2100. Dividing the first by the second yields approximately 8%, which exceeds 1/20, so it is indeed a good bet—assuming it was not made with your bottom dollar.

Back to Top

Back to Top

Join the Discussion (0)

Become a Member or Sign In to Post a Comment

The Latest from CACM

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved

Communications of the ACM (CACM) is now a fully Open Access publication.

By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.

Learn More