More fun with coin flipping

January 30, 2014

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

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

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.