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*_{0})
gives reasonable pseudo-random numbers.
The *n*th random number *R*_{n} is a function of the (*n*-1)st random number:

To complete this analogy, the previous random number

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! |

2001-06-04