Friday, March 14, 2014

Day $\pi$ wish I happy everybody!

By what factor can you guarantee to increase your bankroll at a roulette table, if somehow you get the information that in the next $2n$ rounds, each of the colors red and black will occur exactly $n$ times?

Clearly you can double your bankroll by watching and waiting until the last of those $2n$ rounds, and betting what you have on the color that has come up only $n-1$ times. But you can do better. If $n=2$, you can increase your bankroll by a factor $8/3$: You don't bet anything in the first round. In the second round, you cleverly bet one third of your bankroll on the color that didn't come up in the first round. If you win, you now have $4/3$ of your initial bankroll, and after passing in the third round, you double up in the fourth. If on the other hand you lose in the second round, you still have $2/3$ of your initial bankroll, and since you now know the color of the next two numbers, you can double your remaining money twice, again ending up with $8/3$ times your initial bankroll.

If $n=3$, you can gain a factor $16/5$, and in general the answer is
\[ \frac21\cdot \frac43\cdot \frac65 \cdots \frac{2n}{2n-1}.\]
The factor you gain is actually the reciprocal of the a priori probability that $2n$ rounds of a roulette wheel without zeros would give $n$ red and $n$ black numbers. For an explanation and a description of the strategy, I recommend the lovely paper Games People Don't Play by Peter Winkler.

The reason I bring this up today, March 14, is that for large $n$, the factor you gain is asymptotically \[\sqrt{\pi\cdot n}.\]
The explanation has to do with the Wallis product formula for $\pi$, discovered around 1655 by John Wallis, and it is a fundamental way in which the number $\pi$ enters probability theory and combinatorics.

Wallis formula is usually written
\[\frac21\cdot \frac23\cdot\frac43\cdot\frac45\cdot\frac65\cdot\frac67\cdots = \frac{\pi}2.\]
If we truncate the product on the left just after the factor $\frac{2n}{2n-1}$, the even numbers $2,4,\dots,2n-2$ will occur twice in the numerator, and $2n$ will occur once, while the odd numbers $3,5,\dots,2n-1$ occur twice in the denominator. Taking square roots, we get
\[\frac{2\cdot 4 \cdot 6\cdots \sqrt{2n}}{3\cdot5\cdot 7 \cdots (2n-1)} \approx \sqrt{\frac{\pi}2},\]
and multiplying both sides by $\sqrt{2n}$, we obtain the asymptotical gain at the roulette table:
\[ \frac21\cdot \frac43\cdot \frac65 \cdots \frac{2n}{2n-1} \approx \sqrt{\pi \cdot n}.\]

It has been said that the Wallis product is a lousy way of computing $\pi$, but this is getting things backward. Yes, Ludolph van Ceulen had already calculated 35 decimals of $\pi$ using the method of Archimedes, and Wallis' formula added nothing in terms of such computations. But you don't use the Wallis product to approximate $\pi$, you use $\pi$ to approximate the Wallis product. And Wallis' product doesn't just occur in roulette games. It describes the asymptotics of the central binomial coefficient, which in turn determines the famous factor $\sqrt{2\pi}$ in the formula for the normal distribution and in Stirling's approximation of $n!$. Not to mention the Gamma function and the volume of the $n$-dimensional sphere.

Ten years ago, in 2004, while trying to come up with a good problem for the Swedish mathematical "olympiad", I happened to discover a proof of Wallis' product formula involving no calculus, just plain algebra and geometry. I thought I must have rediscovered something that was known since long ago, but after failing to find it in the literature, I wrote it down and submitted it to the American Mathematical Monthly. A few years later I was happy to hear from Donald Knuth who was preparing a lecture about my proof. And here is a video of his talk. Happy pi-day everyone!