by

David W. Deley

## INTRODUCTION

Many computer programming languages today include a function for generating random numbers. For example, the C programming language includes a function named rand() as a standard part of its language. Supposedly once you get the generator going by giving it a "seed" value then all you have to do is call it repeatedly and it will give you a "random" number every time. But how is it that computers, which are completely deterministic machines, can generate "random" numbers?

This paper presents some background theory in basic probability theory and inferential statistics. We then present a number of empirical tests for analyzing a computer generated sequence of random numbers, and we apply these tests to several popular random number generators.

CONTENTS:

 INTRODUCTION 1.0 PROBABILITY THEORY 1.1 ROLLING DIE 1.2 THE LANGUAGE OF PROBABILITY 2.0 INFERENTIAL STATISTICS 2.1 THE PROBABILITY OF ERROR 2.2 GENERAL TEST PROCEDURE 2.3 THE CHI-SQUARE TEST 2.4 2.4 THE KOLMOGOROV-SMIRNOV TEST 3.0 ANALYSIS OF A SEQUENCE OF RANDOM NUMBERS 3.1 ONE-DIMENSIONAL TESTS 3.2 TWO-DIMENSIONAL TESTS 3.3 THREE-DIMENSIONAL TESTS 3.4 HIGHER DIMENSIONAL TESTS 4.0 LINEAR CONGRUENTIAL RANDOM NUMBER GENERATORS 4.1 GENERATORS TESTED FOR THIS REPORT AND THEIR DEFINITION 4.2 GENERAL FORMAT OF LINEAR CONGRUENTIAL RANDOM NUMBER GENERATORS 4.3 THE MTH\$RANDOM ALGORITHM 4.4 THE RANDU ALGORITHM 4.5 STARTING THE MTH\$RANDOM GENERATOR 4.6 STARTING THE RANDU GENERATOR 4.7 STARTING THE ANSI C GENERATOR 5.0 RATINGS FOR VARIOUS GENERATORS 5.1 REVIEW OF TESTS PERFORMED 5.1.4 THE 1-D TEST 5.1.4 THE 2-D TEST 5.1.4 THE 3-D TEST 5.1.4 THE 4-D TEST 5.2 TEST RESULTS 5.2.1 MTH\$RANDOM 5.2.2 RANDU 5.2.3 C and ANSI C 5.2.4 Microsoft C 5.2.5 Turbo Pascal 5.3 Why did they all fail after 1-10 million iterations? 6.0 THE SPECTRAL TEST 7.0 SHUFFLING 8.0 DES AS A RANDOM NUMBER GENERATOR 9.0 HOW GOOD A RANDOM GENERATOR DO YOU NEED? 10.0 WHAT IS A RANDOM NUMBER GENERATOR? 11.0 THE RANDOM SEUQUENCE {1, 1, 1, 1,... 1} (added September 2003) CONCLUSION SAMPLE PARADOXES OF PROBABILITY The Monty Hall 3 Door Problem Simpson's Paradox The Three-Card Game The Child Paradox Which is safer? Flying vs. Automobile? How to Make 44 a Majority of 140 ANSWERS Further analysis of Child Paradox question 3 (added October 2006) Further analysis of Child Paradox question 4 (added October 2006) GENERATING RANDOM INTEGERS WITHIN A DESIRED RANGE Using the C OR C++ rand() function Additive Random Number Generators (Updated December 2007) The Structure of Language SOURCE CODE FOR PROGRAMMERS who wish to test the randomness of a random number generator SOURCE CODE AND DISCUSSION OF NEWER & BETTER RANDOM NUMBER GENERATORS (added May 2005) LINKS FOR FURTHER RESEARCH REFERENCES Begin the adventure! 