Generating Random Numbers

Finding a reliable source of random numbers is essential to making any Monte Carlo simulation work. A good random number generator produces sequences of bits which are indistinguishable from random coin flips. This is much easier said than done. Generating random numbers is one of the most subtle and interesting problems in computer science, because seemingly reasonable solutions can have disastrous consequences.  

Bad random number generators can easily cause Monte Carlo simulations to give meaningless results. For example, suppose we tried a random number generator which simply alternated heads and tails each time it is asked for another coin flip. This generator produces a sequence of coin flips which has some of the properties of a truly random sequence. For example, the expected number of heads after n random coin flips is n/2, and that is exactly how many will be produced by our simple generator.  

But compare the following sequence of fifty real random flips (I used real pennies) with this ``phony-random'' sequence:

real random	HTHHH	TTHHH	TTTHT	THHHT	HTTHH
	HTHHT	THHTH	THHTT	HTHHT	TTTHT
phony random	HTHTH	THTHT	HTHTH	THTHT	HTHTH
	THTHT	HTHTH	THTHT	HTHTH	THTHT

There are significant differences between the two sequences. First, the real random sequence had an unbalanced number of heads and and tails (27 heads vs. 23 tails). This is not surprising. In fact, 50 coin flips should end up as exactly 25 heads and 25 tails only 11.2% of the time. Likewise, in the real random sequence there is a run of 4 consecutive tails. A sufficiently long sequence of flips should have substantial runs of consecutive heads or tails, if it is truly random. Such counterintuitive behavior helps explain why people are lousy at designing truly random-looking sequences. Many embezzlers, ballot stuffers, and quack scientists have been caught because their data or audit trails were too ``random'' to hold up to careful scrutiny.

Let's think through the consequences of using the phony-random generator with our simulation, instead of a truly random generator. No matter how many games we simulated, there would only be two different trifecta outcomes ever produced! Suppose that whenever the first coin was heads, we assigned player 1 to be the winner of the first point (against player 2). Whenever player 1 wins the first point, this means that the next ``random'' coin flip will always yield a tails, and so the winner of the second point will always be predestined. In either case, the outcome of the first coin flip always decides the winner of the match, and so the results of our simulation are completely meaningless!

So how do we generate truly random numbers on a computer? The short answer is that we can't. Computers are deterministic machines that always do exactly what that they are programmed to do. In general, this is a good thing, for explains why we trust computers to balance our checkbook correctly. But it eliminates the possibility of looking to computers as a source of true randomness.

The best we can hope for are pseudo-random numbers, a stream of numbers that appear as if they were generated randomly. This is a dicey situation. John von Neumann, the brilliant mathematician who is credited with designing the first modern computer, said it best: ``Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin.''  

 

The pseudo-random number generation algorithm of choice generates random numbers using the same principle that roulette wheels do. In a roulette wheel, we start by rolling a ball around and around and around the outer edge of the wheel. After several seconds of motion, the ball loses enough energy that it drops into the bottom part of the wheel, and then comes to rest in one of the 38 equal-sized labeled compartments at the bottom of the wheel.  

Why do casinos and their patrons trust that roulette wheels generate random numbers? Why can't the fellow in charge of rolling the ball learn to throw it so it always lands in the double zero slot? The reason is that the ball always travels a very long path around the edge of the wheel before falling, but the final slot depends upon the exact length of the entire path. Even a very slight difference in initial ball speed means the ball will land in a completely different slot.

So how can we exploit this idea to generate pseudo-random numbers? A big number (corresponding to the circumference of the wheel) times a big number (the number of trips made around the wheel before the ball comes to rest) yields a very big number (the total distance that the ball travels). Adding this distance to the starting point (the release point of the ball) determines exactly where the ball will end up. Taking the remainder of this total with respect to the wheel circumference determines the final position of the ball, by subtracting off all the loops made around the wheel by the ball.

This is the idea behind the linear congruential generator. It is fast, simple, and (if set with the right constants a, c, m, and R₀) gives reasonable pseudo-random numbers. The nth random number R_n is a function of the (n-1)st random number:

$$R_n = (a R_{n-1} + c) ~\mbox{mod}~ m$$

To complete this analogy, the previous random number R_n-1 corresponds to the starting point of the ball, while a and c dictate how hard the ball will be thrown. Finally, m stands for the circumference of the wheel. The mod function is just a fancy term for the remainder.   Lurking within my simulation is a linear congruential generator with carefully chosen constants, which have been shown to produce reasonable-looking pseudo-random numbers.^4.1, The high correlation between the distribution of observed trifectas and our simulation results gives us faith in both our model and our random number generator.

I hope you have enjoyed this excerpt from Calculated Bets: Computers, Gambling, and Mathematical Modeling to Win!, by Steven Skiena, copublished by Cambridge University Press and the Mathematical Association of America. This is a book about a gambling system that works. It tells the story of how the author used computer simulation and mathematical modeling techniques to predict the outcome of jai-alai matches and bet on them successfully -- increasing his initial stake by over 500% in one year! His method can work for anyone: at the end of the book he tells the best way to watch jai-alai, and how to bet on it. With humor and enthusiasm, Skiena details a life-long fascination with the computer prediction of sporting events. Along the way, he discusses other gambling systems, both successful and unsuccessful, for such games as lotto, roulette, blackjack, and the stock market. Indeed, he shows how his jai-alai system functions just like a miniature stock trading system. Do you want to learn about program trading systems, the future of Internet gambling, and the real reason brokerage houses don't offer mutual funds that invest at racetracks and frontons? How mathematical models are used in political polling? The difference between correlation and causation? If you are curious about gambling and mathematics, odds are this is the book for you! This book is available in both hardcover and paperback.