39: Random Number Generation
“The generation of random numbers is too important to be left to chance.” - Robert R. Coveyou.
"Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin" - Von Neumann.
Lecture outline: how to generate and validate pseudo random numbers using computers?
1) What is randomness?
The counterintuitive nature of randomness.
2) Generating random numbers and variates.
Tabulated 'random' numbers.
True random number generators (TRNGs).
Pseudorandom number generation
Arithmetic random number generation.
Properties of good PRNGs.
Middle-square method.
Linear Congruential Generator (LCG).
Multiplicate LCG.
Commonly used RNGs: Lehmer's LCG; IBM RANDU; LCG 16807; Mersenne Twister; Multiply with Carry (MWC).
Seed Selection.
Random variate generation:
Inverse transformed variates.
3) Testing random numbers.
Inverse transformed variates.
Good RNG are hard to find.
Frequency test: Chi-square test.
Spectral test (test of k-tuples).
Primary reference for this lecture:
“The Art of Computer Systems Performance Analysis: Techniques for Experimental Design, Measurement, Simulation, and Modeling” by Raj Jain; Chapter 29: “Commonly Used Distributions”.
Secondary references for this lecture:
1. "Probability, Markov Chains, Queues, and Simulation: The Mathematical Basis of Performance Modeling", William Stewart, Chapter 17.
2. “Simulation” by Sheldon Ross.