DOI: 10.1145/2534706.2534727 Peter Winkler
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.no head start. 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?
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.
All readers are encouraged to submit prospective
puzzles for future columns to email@example.com.
Peter Winkler ( firstname.lastname@example.org) is william morrill
Professor of mathematics and Computer science,
at dartmouth College, hanover, nh.
© 2013 aCm 0001-0782/13/12 $15.00