## August 2008

—————————

*The Math Corner in this month's diary included the following brainteaser.*

You can flip coins until the number of heads and tails are equal. The payoff is the number of flips. So, half of all games end after two flips and pay two dollars …

—————————

SolutionI'm not sure how you structure a genuine betting game out of this, but let's just take the problem to be: How many games would you expect to end afterTcoin flips (whereT, obviously if you think about it, is an even number)?

To cut right to the chase, theproportionof games ending after exactlyTtosses is the ((T/ 2) – 1)-th Catalan number divided by the (T– 1)-th power of 2.

The zero-th, first, second, third, fourth, … Catalan numbers are 1, 1, 2, 5, 14, 42, 132, 429, …, so the proportion of games ending after exactly 10 tosses, for example, would be the fourth Catalan number divided by 2^{9}. That would be 14 divided by 512, which is around 0.02734375.

Thus roughly 2.7 percent of your games end after exactly ten tosses. (Of course, quite a lot — nearly 73 percent — will have endedbeforethat, after 2, or 4, or 6, or 8 tosses.) After 2, 4, 6, 8, 10, 12 tosses, the percentages ending are 50, 12.5, 6.25, 3.9, 2.7, 2.1.

A simulation confirms this. I — actually, of course, my PC — played a million games to see how many ended after 2, 4, 6, … tosses. Here are the results forTup to 40.Tis the number of tosses,Eis the number of games that ended after exactlyTtosses, the rightmost column just shows the zero-th, 1st, 2nd, 3rd, … Catalan numbers. The numbers in the fourth column have been rounded to the nearest integer.

T |
E |
P = E / 10^{6} |
P × 2^{T – 1} |
Catalans |
---|---|---|---|---|

2 | 500,031 | 0.500031 | 1 | 1 |

4 | 125,220 | 0.12522 | 1 | 1 |

6 | 62,218 | 0.062218 | 2 | 2 |

8 | 38,584 | 0.038584 | 5 | 5 |

10 | 28,105 | 0.028105 | 14 | 14 |

12 | 20,157 | 0.020157 | 41 | 42 |

14 | 16,246 | 0.016246 | 133 | 132 |

16 | 12,794 | 0.012794 | 419 | 429 |

18 | 10,036 | 0.010036 | 1,315 | 1,430 |

20 | 9,040 | 0.00904 | 4,740 | 4,862 |

22 | 7,663 | 0.007663 | 16,070 | 16,796 |

24 | 6,738 | 0.006738 | 56,522 | 58,786 |

26 | 6,009 | 0.006009 | 201,629 | 208,012 |

28 | 5,595 | 0.005595 | 750,948 | 742,900 |

30 | 4,981 | 0.004981 | 2,674,154 | 2,674,440 |

32 | 4,816 | 0.004816 | 10,342,281 | 9,694,845 |

34 | 3,690 | 0.00369 | 31,696,858 | 35,357,670 |

36 | 3,873 | 0.003873 | 133,075,264 | 129,644,790 |

38 | 3,267 | 0.003267 | 449,013,056 | 477,638,700 |

40 | 2,961 | 0.002961 | 1,627,826,944 | 1,767,263,190 |

If you were to add up all the numbers in the third column, you should of course get 1. Is this the case?

Well, the first number is (close to)C_{0}/ 2; the second is (close to)C_{1}/ 2^{3}; the third is (close to)C_{2}/ 2^{5}; the fourth is (close to)C_{3}/ 2^{7}; … and so on. Add 'em up and you get:

½ × (C_{0}+C_{1}/ 4 +C_{2}/ 16 +C_{3}/ 64 +C_{4}/ 256 + … )

The coefficients of theCs in the infinite series there are just the 0th, 1st, 2nd, 3rd, … powers of ¼. Now the generating function for the Catalan numbers is [1 – (1 – 4x)^{½}] / 2x. If you substitutex= ¼, this works out to 2. Half of 2 is 1, and the result is confirmed.

—————————

So far, so good; butwhyis this the solution?

I confess I don't have a complete answer, but here is as far as I've got.

Since no game ends on an odd-numbered coin flip, it's best to think of a consecutive pair of flips as a single event. We do two flips and scrutinize the result. We do two more (total four) and scrutinize the result … and so on. I'm going to speak like this: When I say "the sixth flip," I shall mean the fifth and the sixth, taken as a single event, acting on the result of the fourth flip, which of course is defined the same way.

With that in mind, let's look at the result of theT-th flip, defined as above, i.e. actually the (T–1)-th flip followed by theT-th.

First, how manypossibleconfigurations could be produced by theT-th flip? By "configuration," I mean a sequence of heads and tails. Here is a possible configuration from the sixth flip: TTTTTH. The previous five flips were all tails; the sixth a head (reverting for a moment there to the commonsense meaning of "sixth flip").

Well, there are of course 64 possible configurations from six coin flips: HHHHHH, HHHHHT, HHHHTH, …, TTTTTT. (You didn't think I was going to write themallout, did you?) However, some of those configurations are "dead." I mean, they won't be participating in the 6th flip because they ended a previous game. The configuration HTHHHH, for example, would have ended the game at coin flip number 2; the configuration HHTTHT, at coin flip number 4.

So how many possible configurationscouldbe produced by the sixth flip? Of which, how many will "survive" (i.e. not end at the sixth game) to be fodder for the eighth flip? The actual answers there are 24 and 20; but of course we are seeking a general solution.

Let's algebraize. Suppose the number of configurations, out of all the possible 2^{T−2}, that "survive" after the (T−2)-th flip, and will be passed on as input to theT-th, isf(T). FlipT— i.e. the (T−1)-th followed by theT-th — multiplies this by four. Of those 4×f(T), what proportion are game-enders?

The answer is 1/T.

The remainder, to be passed on as input to the (T+2)-th flip, is of course (1−1/T) times 4×f(T); or, to put it slightly differently, 4×[(T−1)/T]×f(T).

But that, by my definition off, is justf(T+2). So I have a recurrence relation:

f(T+2) /f(T) = 4 × (T−1) /T

The solution of this recurrence relation isf(T) = 2 × (T−3) × C_{T/2 − 2}. [This follows from the standard recurrence relation for Catalan numbers: C_{k}/ C_{k−1}= 2 × (2k−1) / (k+1).]

That just gets you to the Catalan numbers. A wee bit more logic then gets you to the result I quoted way up above.

The missing link — the thing I haven't figured out yet — is that statement in green. Why is it true? A statement as simple as that ought to be easy to figure out, but I'm stuck on it.

(And my guess is that this is a "von Neumann solution" anyway — i.e. that the result follows much more directly and neatly from one of the many properties of the Catalan numbers, which I'm not sufficiently familiar with.)