Random number generators

Linear Congruential Generator (LCG) is one of the conventional random number generation schemes. These random numbers are not true random numbers, but are "pseudo-random numbers". Check the meaning of "pseudo" from a trusted dictionary. In that, our generator is meant to generate a known (deterministic) sequence of numbers which are only "mixed enough". So, after generating a long sequence of numbers, once we begin from a certain element of sequence, advancing one number at a time will provide us with a perception of randomness. We can use them in our statistical experiments and simulations with quite some reliability.

An LCG is defined by the recurrence relation \(X_{n+1}=\left(a X_n+c\right) \bmod m\), where \(m\) is the modulus, \(a\) is the multiplier, \(c\) is the increment, and \(X_0\) is the seed. Each generated value \(X_n\) must be one of the integers \(0,1,2, \ldots, m-1\). Therefore, there are only \(m\) possible states. Since the rule is deterministic, once the same value appears again, all later values will repeat in exactly the same order. Thus every LCG sequence is eventually periodic. In the best case, the period can be as large as \(m\), but it can never exceed \(m\).