Summary of the Notes:

Generating random numbers is not as easy a job as it looks like. Sequences generated by randomly chosen methods typically fail to have satisfactory randomness properties. Superisingly, one kind of good generator, Linear Congruential Generator,turns out to be of very simple form X_n+1 =(aX_n + c) mod m, n ≥0.

We considered two factors to help to make the linear congruential sequence look random: period and potency, and discussed the choices of a, c, m, X₀ that give or fail to give the sequence long period or high potency.

Then we introduced ways of testing the generators: first test the output sequence with some empirical test, then use chi-square test to evaluate the infomation collected from impirical test.

History:

For people who are interested in the history of the subject: The article "Random Number Generators" by T.E.Hull and A.R.Dobell, SIAM Review 4 (1962), 230-254, contains an excellent bibliography of the pre-1962 literature on the subject.

Present Use:

The linear congruential generator now is widely used but also has limitation, which makes it not suitable for high resolution Monte Carlo Simulation.

New development:

In 1997, Makoto Matsumoto and Takuji Nishimura found a new random number generator, which they named the Mersenne Twister, with the phenomenally large period 2¹⁹⁹³⁷ - 1. Though it is not safe to use in cryptographical applications, it generates random numbers very efficiently and is now in wide use.

Spectral test:

There is one kind of very important test which is left out in the notes because of its complexity. It's the spectral test formulated in 1965 by R.R.Coveyou and R.D.MacPherson. For a detailed explanation, refer to section 3.3.4 of [1]. For a intuitive description, refer to [2].

References:

[1] Donald E.Knuth, The Art of Computer Programming, Volume 2, Third Edition,Addison-Wesley,Boston.1997

[2] Feature Column from the AMS: http://www.ams.org/featurecolumn/archive/random.html

[3] Ireland,Kenneth, and Michael Rosen, A Classical Introduction to Modern Number Theory, Springer-Verlag, New York 1991

[4] James E. Gentle, Random Number Generation and Monte Carlo Methods, Second Edition,Springer-Verlag New York,Inc.1998