7.3.1 Uniform distribution

Many computer systems are supplied with random number generators in their standard libraries. These are usually linear congruential pseudo-random number generators [41], which generate a sequence of integers $I_1, I_2, I_3, \ldots$, each between 0 and $m-1$ by the recurrence relation

$$I_{j+1} = a I_j + c \quad (\mathrm{mod~} m) \quad.$$

The multiplier $a$ and the increment $c$ are positive integers and the modulus $m$ is a large number. If these three parameters are properly chosen, the sequence will be of maximal length, that is of length $m$. In that case, all integers between 0 and $m-1$ appear, before the sequence is repeated. Thus, any initial seed $I_0$ is as good as any other. In order to have a uniform distribution in the interval $[0, 1[$, generally $I_{j+1}/m$ is returned. It is clear from the recursive form, that $I_{j+1}=m$ cannot occur and therefore $I_{j+1}/m$ is strictly less than 1.

The quality of this random number generator depends only on the parameters in the recurrence relation, and it is satisfactory for many applications, but far from perfect. For example, successive numbers differ by a multiple, which is orders of magnitude smaller than the modulus. These low-order correlations are removed by shuffling the output. A random deviate derived from the $j$th value in the sequence, $I_j$, is output not on the $j$th call, but rather on a randomized later call.

If even longer random sequences are needed, two different sequences can be combined to obtain a new sequence, whose period is the least common multiple of the two periods. When implementing a random number generator, special care must be taken of the machine's maximum value for an integer number and the size of the mantissa in the floating-point representation.

Thus, the quality of a random number generator should only be limited by its period.