Chapter 9

Random Numbers

This chapter describes algorithms for the generation of pseudorandom numbers with both uniform and normal distributions.

9.1

Pseudorandom Numbers
0.814723686393179

Here is an interesting number:

This is the first number produced by the Matlab random number generator with its default settings. Start up a fresh Matlab, set format long, type rand, and it’s the number you get. If all Matlab users, all around the world, all on different computers, keep getting this same number, is it really “random”? No, it isn’t. Computers are (in principle) deterministic machines and should not exhibit random behavior. If your computer doesn’t access some external device, like a gamma ray counter or a clock, then it must really be computing pseudorandom numbers. Our favorite definition was given in 1951 by Berkeley professor D. H. Lehmer, a pioneer in computing and, especially, computational number theory: A random sequence is a vague notion . . . in which each term is unpredictable to the uninitiated and whose digits pass a certain number of tests traditional with statisticians . . .

9.2

Uniform Distribution

Lehmer also invented the multiplicative congruential algorithm, which is the basis for many of the random number generators in use today. Lehmer’s generators involve three integer parameters, a, c, and m, and an initial value, x0 , called the seed. A
September 16, 2013

1

2 sequence of integers is defined by xk+1 = axk + c mod m.

Chapter 9. Random Numbers

The operation “mod m” means take the remainder after division by m. For example, with a = 13, c = 0, m = 31, and x0 = 1, the sequence begins with 1, 13, 14, 27, 10, 6, 16, 22, 7, 29, 5, 3, . . . . What’s the next value? Well, it looks pretty unpredictable, but you’ve been initiated. So you can compute (13 · 3) mod 31, which is 8. The first 30 terms in the sequence are a permutation of the integers