More fun with coin flipping

In my last post I attempted to solve three coin flipping puzzles using Monte Carlo simulation. The solutions to the puzzles are published, so I’ll compare my results to the correct analytic solutions.

Problem 1

The first problem is:

You have just joined the Coin Flippers of America, and, naturally, the amount of your annual dues will be determined by chance. First you must select a head-tail sequence of length five. A coin is then flipped (by a certified CFA official) until that sequence is achieved with five consecutive flips. Your dues is the total number of flips, in U.S. dollars; for example, if you choose HHHHH as your sequence, and it happens to take 36 flips before you get a run of five heads, your annual CFA dues will be $36. What sequence should you pick? HHHHH? HTHTH? HHHTT? Does it even matter?

Although I expected the dues for any sequence to be about $32 dollars, I found that a few sequences (HHHHH and TTTTT) were much more expensive. Both of these choices lead to dues of around $62 dollars. Peter Winkler describes why this occurs in his answer:

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.

So my Monte Carlo simulation correctly predicted this result.

Problem 2

The second problem is:

Now you have entered your first CFA tournament, facing your first opponent. Each of you will pick a different head-tail sequence of length five, and a coin will be flipped repeatedly. Whoever’s sequence arises first is the winner. You have the option of choosing first. What sequence should you pick?

My simulation indicated that both HHHHH and TTTTT are poor choices winning least often because they occur least often. My simulation also indicated, rather surprisingly, that HTTTT is the best option. As it turns out, I missed a key part of the problem. Your opponent can know your chosen sequence, and choose his or her sequence accordingly. My simulation assumed your opponent had no knowledge of your choice. Winkler uses this part of the problem to propose the solution.

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.

I added another simulation to the utility which tests this strategy. For each possible combination you can choose, here are the results if your opponent chooses the first four flips from your sequence with a leading ‘H’ (using 10,000 iterations):

Sequence	Percent of games you win	Sequence	Percent of games you win
HHHHT	50.53%	HHTHT	33.55%
THTHT	49.74%	HHHTT	33.39%
THTHH	42.56%	HHTTT	33.29%
HTHHT	41.37%	HHTTH	33.23%
HTHHH	41.36%	HTTTT	32.96%
THHTH	40.57%	HHHTH	32.96%
TTTHT	38.76%	HHTHH	32.8%
TTHTH	38.22%	HTTTH	32.42%
TTHTT	38.22%	HTTHT	30.99%
TTHHT	37.86%	THTTH	29.7%
THHHH	37.48%	THTTT	29.15%
THHHT	37.04%	HTHTT	26.37%
TTTHH	36.98%	HTHTH	22.73%
HTTHH	36.64%	TTTTH	6.28%
TTHHH	36.38%	TTTTT	3.13%
THHTT	34.19%

Here are the results if your opponent chooses the first four flips from your sequence with a leading ‘T’:

Sequence	Percent of games you win	Sequence	Percent of games you win
TTTTH	50.18%	TTTHT	34.44%
HTHTH	49.85%	THHHH	34.08%
THTTH	42.09%	TTHHH	33.49%
THTTT	42.0%	TTHHT	33.3%
HTHTT	41.55%	TTHTH	32.98%
HTTHT	40.25%	TTHTT	32.88%
HHTTT	38.1%	TTTHH	32.73%
HHHTT	38.04%	THHHT	32.36%
HHTHH	37.66%	THHTH	31.32%
HHTHT	37.34%	HTHHT	29.2%
HTTTT	37.04%	HTHHH	28.77%
HTTTH	36.79%	THTHH	26.88%
HHHTH	36.73%	THTHT	22.83%
HHTTH	36.4%	HHHHT	6.05%
THHTT	36.21%	HHHHH	2.91%
HTTHH	35.06%

Clearly, if you opponent is blindly following one or the other strategy, your best option is to choose either HHHHT or TTTTH. I suspect that your opponent will be smart enough to choose the appropriate leading flip to give you almost no chance to win in these two cases. As Winkler mentions, your best option is to choose one of the sequences in the middle, which gives the best results for both cases. He suggests HHTHT, which wins about 1 of 3 times.

Problem 3

The third problem is:

Following the tournament (which you win), you are offered a side bet. You pay $1 and flip a coin 100 times; if you get exactly 50 heads, you win $20 (minus your dollar). If you lose, you are out only the $1. Even so, should you take the bet?

Winkler mentioned that a good estimate for flipping \(n\) heads in \(2n\) flips is

\[\frac{1}{\sqrt{\pi n/2}}\]

With \(n=50\) this expression yields about 11%. He indicates that we instead can compute the value exactly, since the number of ways to flips exactly 50 heads in 100 flips is 100 choose 50, and the total number of outcomes for 100 flips is \(2^{100}\), then the chance to getting exactly 50 heads in 100 flips is

\[\frac{100!/(50!)^2}{2^{100}} = 0.08\]

Since 8% is greater than 1/20 (5%), Winkler indicates that this is a good bet.

My results, on the other hand, found that this bet wins only 2% of the time, meaning it is not a good bet. My utility inspects only 1000 possible \(2^{100}\)combinations of flips, so I suspect that my sample size is consistently too small. Based on the time the utility takes to run with 1000 samples, I suspect that using any reasonable number of the \(2^{100}\) samples will not be feasible. Winkler’s analytic solution is clearly correct.