Not so Random Coin Toss: Mersenne Twister

“The generation of random numbers is too important to be left to chance.” — Robert R. Coveyou

Often when confronted with difficult decisions, I resort to a simple coin toss to "get objective". But, flipping a coin may not be the fairest way to settle disputes. About 13 years ago, statistician Persi Diaconis started to wonder if the outcome of a coin flip really is just a matter of chance. He had Harvard University engineers build him a mechanical coin flipper. Diaconis, now at Stanford University, found that if a coin is launched exactly the same way, it lands exactly the same way.

The randomness in a coin toss, it appears, is introduced by us sloppy humans. Each human-generated flip has a different height and speed, and is caught at a different angle, giving different outcomes.

But using high speed cameras and equations, Diaconis and colleagues have now found that even though humans are largely unpredictable coin flippers, there's still a bias built in: If a coin starts out heads, it ends up heads when caught more often than it does tails.

PseudoRandom number generators have a much better probability distribution:

Marsaglia and Mersenne are at 0.5000 -- in other words, a perfect random distribution of heads vs tails.

The Mersenne twister is a pseudorandom number generator developed in 1997 by Makoto Matsumoto and Takuji Nishimura that is based on a matrix linear recurrence over a finite binary field F₂. It provides for fast generation of very high quality pseudorandom numbers, having been designed specifically to rectify many of the flaws found in older algorithms.

Its name derives from the fact that period length is chosen to be a Mersenne prime. There are at least two common variants of the algorithm, differing only in the size of the Mersenne primes used. The newer and more commonly used one is the Mersenne Twister MT19937, with 32-bit word length. There is also a variant with 64-bit word length, MT19937-64, which generates a different sequence.

Being a big proponent of "not reinventing the wheel" I set out to see if I could find somebody's C# implementation. It didn't take long to find Dave Loeser's article at codeproject.com, with a feature-complete implementation of the latest algorithm. A little monkeying with the initialization and seeding, and I had my coin flipper all done.

My test implementation has a web page with a button that will run the "flip" through 1 Million iterations, and choose the last one as the outcome value. This is then used to show either heads or tails on a nice image of an old Indian Head Penny. It also shows you the statistics for each set of 1 million "coin tosses". You can view the live sample page here, and you can download the sample code and play with it if you like! This algorithm is fast -- it will do the 1 million iterations in about 135 milliseconds -- the page displays the elapsed time using the stopwatch class.