How do computers, which are completely deterministic devices, generate random numbers?

INTRODUCTION

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!

email David Deley: deleyd@ieee.org