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 …
—————————
Solution I'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 after T coin flips (where T, obviously if you think about it, is an even number)?
To cut right to the chase, the proportion of games ending after exactly T tosses 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 29. 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 ended before that, 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 for T up to 40. T is the number of tosses, E is the number of games that ended after exactly T tosses, 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 / 106 | P × 2T – 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) C0 / 2; the second is (close to) C1 / 23; the third is (close to) C2 / 25; the fourth is (close to) C3 / 27; … and so on. Add 'em up and you get:
½ × (C0 + C1 / 4 + C2 / 16 + C3 / 64 + C4 / 256 + … )
The coefficients of the Cs 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 substitute x = ¼, this works out to 2. Half of 2 is 1, and the result is confirmed.
—————————
So far, so good; but why is 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 the T-th flip, defined as above, i.e. actually the (T–1)-th flip followed by the T-th.
First, how many possible configurations could be produced by the T-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 them all out, 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 configurations could be 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 2T−2, that "survive" after the (T−2)-th flip, and will be passed on as input to the T-th, is f(T). Flip T — i.e. the (T−1)-th followed by the T-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 of f, is just f(T+2). So I have a recurrence relation:
f(T+2) / f(T) = 4 × (T−1) / T
The solution of this recurrence relation is f(T) = 2 × (T−3) × CT/2 − 2. [This follows from the standard recurrence relation for Catalan numbers: Ck / Ck−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.)