Random number; problems in generating pseudo-random

Random number

A random number is a number drawn from a given distribution so that its value cannot be predicted. In simulation it usually means a number R uniformly distributed on [0, 1) and independent of the other numbers. These are the base from which random variates of any distribution (exponential, normal, etc.) are produced.

True random numbers (from radioactive decay, electronic noise) are slow and cannot be repeated. So computers use pseudo-random numbers, produced by a deterministic recurrence such as the linear congruential method Xn+1 = (aXn + c) mod m, Rn = Xn/m. They only imitate randomness.

Problems in generating pseudo-random numbers

1. Not truly random. The sequence is fully determined by the seed and the formula, so it only appears random.
2. Finite period / cycling. The sequence must repeat after at most m values. A poor choice of a, c, m gives a short cycle, so the same numbers are reused.
3. Departure from uniformity. The generated numbers may not be evenly spread over [0, 1), giving too many or too few numbers in some regions.
4. Dependence (correlation). Successive numbers may be correlated, or fall on a few lines or planes when plotted in 2 or 3 dimensions (lattice structure).
5. Poor seed or parameter choice. Some seeds lead to degeneration, e.g. the sequence sticks at zero, or a short loop. The choice of a, c, m must follow the full-period conditions.
6. Discrete values only. Only m distinct values are possible, so the density is not truly continuous. Small m gives large gaps.
7. Computational issues. Overflow in the product aX, slow speed, or different results on different machines (non-portability).
8. Need for statistical testing. Every generator must be tested for uniformity (chi-square, K-S) and independence (runs, autocorrelation, gap, poker) before use. Passing the tests is not a guarantee, because only finite tests are made.

Remedies: use a large modulus (e.g. 2³¹ − 1), proven multipliers, combined generators, and always test the output. Reproducibility is an advantage, since the same stream can be replayed for debugging.