| | Ivars Peterson's MathLand |
April 22, 1996
Marsaglia has spent most of his career dealing with random numbers -- both producing and testing them. He published his first paper on the topic more than 40 years ago. Since then, Marsaglia and his collaborators have identified a variety of flaws in computer-based random number generators, invented more robust versions of these generators, and developed a suite of rigorous tests to check for randomness.
Loosely speaking, any number that belongs to a sequence of random numbers is a member of that string by chance. Ideally, it has no connection with any other number in the sequence, and each number has a specified probability of falling in any given range. If the probability distribution is uniform, one would expect that each of the 10 digits from 0 to 9 occurs about one-tenth of the time.
Researchers use random numbers for tackling a wide range of problems, from modeling molecular behavior and sampling opinion to solving certain equations and testing the efficiency of algorithms. Such numbers also play crucial roles in a wide variety of games, including electronic versions of slot machines, lotteries, and other forms of gambling. Indeed, the world of gambling inspired use of the term "Monte Carlo method" to describe any algorithm that employs random numbers.
A century ago, people who needed random numbers in their scientific work tossed coins, rolled dice, dealt cards, picked numbers out of well-stirred urns, or browsed census records and other lists of digits. In 1927, L.H.C. Tippett published a table of 41,600 random numbers, obtained by taking the middle digits of the area of parishes in England. He did it as a service to others who needed a convenient source of such numbers.
Nearly 30 years later, experts at the RAND Corporation used a special machine for electronically generating random bits, which were then converted into a table of a million random decimal digits. To remove slight biases discovered in the course of intensive testing, the one million digits were further randomized by adding all pairs and retaining only the last digit.
Shortly after the introduction of computers in the late 1940s, researchers also began to search for efficient ways of obtaining random numbers to use in computer programs. They developed random-number generators that scramble the bits of a given number in such a way that the result appears independent of previously generated numbers.
But the numbers in the resulting sequences typically don't meet all the criteria that establish randomness. Patterns often still remain. After all, the computer simply follows a set procedure to generate the numbers, and restarting the process produces the same sequence. Moreover, these sequences eventually begin repeating themselves. It's all quite deterministic.
During the last few years, in a project funded by the National Science Foundation, Marsaglia has been packing his hard-won expertise onto a CD-ROM to create a catalog of random bits for the information age.
Marsaglia's primary purpose is to provide a source of unassailable random numbers for serious Monte Carlo studies and simulations, where millions of such numbers are often required. In smaller doses, these completely patternless strings of bits can be used to provide reliable and verifiable random choices in designing experiments and clinical trials, for running sample surveys and choosing jury panels, and in other applications.
The Marsaglia Random Number CD-ROM contains some 5 billion random bits, divided into sixty 10-megabyte files, which can be read 1, 8, 16, or some other number of bits at a time, depending on the application. The disk also contains Marsaglia's "Diehard" battery of randomness tests, along with text files explaining the theory underlying the tests and the random number generators used to create the random bits.
The random bits were made by combining three sources of electronic white noise with the output from the best of the latest crop of deterministic random number generators, based on Marsaglia's "mulitply-with-carry" method. "They seem to pass all tests I have put to them -- and I have some very stringent tests," Marsaglia says.
A truly random stream of bits remains random when it's combined with any other stream of bits, no matter how patterned. Marsaglia mixed digital tracks from rap and classical music selections and even a few digital pictures into some of the 10-megabyte files on the CD-ROM. Both the untouched and mixed files seem to pass his randomness tests, he reports.
Marsaglia's CD-ROM was finally ready in March, just as he was about to retire and become an emeritus professor at Florida State. His NSF grant allowed him to make 1,000 copies, and most of these have already been snapped up by researchers bent on working with the best they can get in random digits.
Marsgalia doesn't have the funds to produce more copies of the CD-ROM. But with such strong interest in random bits, perhaps someone else will take over production and distribution of this unique resource.
As mathematician Robert R. Coveyou at the Oak Ridge National Laboratory once put it, "The generation of random numbers is too important to be left to chance."
Knuth, Donald E. 1969. The Art of Computer Programming. Reading, Mass.: Addison-Wesley.
Marsaglia, George. 1968. Random Numbers Fall Mainly in the Planes. Proceedings of the National Academy of Science (USA) 61 (September): 25-28.
Marsaglia, George, and Arif Zaman. 1994. Some portable ver-long-period random number generators. Computers in Physics 8 (January/February): 117-121.
______. 1991. A new class of random number generators. Annals of Applied Probability 1 (3): 462-480.
Peterson, Ivars. 1991. Numbers at Random. Science News 140 (Nov. 9): 300-301.
______. 1990. Islands of Truth: A Mathematical Mystery Cruise. New York: W. H. Freeman.
Pickover, Clifford A. 1195. Random number generators: Pretty good ones are easy to find. The Visual Computer 11:369-377.
RAND Corporation. 1955. A Million Random Digits with 100,000 Normal Deviates. New York: Free Press.
You can reach George Marsaglia at geo@stat.fsu.edu. If you are a researcher interested in obtaining a copy of his random number CD-ROM for scientific use, please include your mailing address in the text of your message, following this format: name\\address line\\address line\\...\\address line\\, where "\\" signals a new line.
Comments are welcome. Please send messages to Ivars Peterson at ip@scisvc.org.
Ivars Peterson is the mathematics and physics writer at Science News. He is the author of The Mathematical Tourist, Islands of Truth, Newton's Clock, and Fatal Defect: Chasing Killer Computer Bugs. He is now working on Adventures in Mathland: The Jungles of Randomness (to be published in 1997 by Wiley).