1. Random Number Generators #

Random Number Generators (RNGs) are a means of drawing numbers following a distribution. A RNG is valued by

1. the degree of randomness (ability to pass statistical tests);
2. reproducability (deterministic vs. true random);
3. efficiency.

Computer-based RNGs are almost always deterministic, rather than truly random. For that reason they are usually called pseudo-random RNGs (PRNGs). Many PRNGs produce sequences of numbers using a recursion \[ x_{i+1} = f(x_i). \tag{1.1}\] with \(i \in \mathbb{N}^0\) . The first number of the sequence, $x_0$, is a chosen constant, and is called the seed of the RNG.

A recommended read is the short writing by Random Number Generators: Good Ones Are Hard To Find by Park and Miller.

1.1 The Linear Congruential RNG #

A Linear Congruential RNG (LCRNG) is a PRNG that generates numbers in \(M := \{ 0, 1, 2, \dots, m - 1\}\) with the recursion \[ x_{i+1} = (ax_i + c)\, \text{mod} \, m, \tag{1.2}\] where \(a \in M, c \in M, m \in \mathbb{N}^+\) are parameters. $c$ is called the carry of the LCRNG. An LCRNG is called multiplicative if the carry is zero, and mixed otherwise.

An LCRNG will start repeating itself after a number of iterations. That is to say, it runs into a repeating cycle of length $n$, when \(x_{i+n} = x_i\) . An LCRNG may have multiple of such cycles, and the choice of $x_0$, the seed, determines in which cycle the RNG will end. The length of the shortest (most pessimistic) cycle that the LCRNG can land into is called the period. More precisely, it is the minimum over all $x_0$ and all $i$ of $x_{i+n} = {x_i}$. In the best case, an LCRNG has a full period, which means $n=m$ for mixed generators, or $n=m-1$ for multiplicative generators.

LCRNGs are easily distinguishable from true random RNGs. LCRNGs will always visit numbers of a cycle in consecutive order, and each number is visited precisely once per cycle. A true random number generator, on the other hand, may repeat certain numbers and skip others.

Let $\Omega$ indicate the uniform distribution on $[0, 1]$. To have numbers distributed in $[0, 1]$, which is more useful than numbers from $M$, the output of the LCRNG may be scaled using \[ \omega_i := \frac{x_i}{m - 1}. \tag{1.3}\]

1.2 Example LCRNGs #

The table below contains a few LCRNGs.

Some entries of parameters are suggested in the literature. The Park-Miller generator is viewed as a “minimal standard” generator: the generator has full period.