Pseudorandom number generator

A pseudorandom number generator is a deterministic state-update algorithm producing numbers intended to imitate an independent sequence from a prescribed probability distribution. For Monte Carlo integration, desirable features include good one-dimensional and multidimensional uniformity, a period far longer than the calculation, negligible detectable dependence, reproducible seeds, sufficient numerical precision and fast generation. Uniform marginal distributions alone do not provide independent draws.

A pseudorandom number is an output of a deterministic algorithm chosen to imitate samples from a specified probability law. For example, a linear congruential generator returns fractions $S_i/M$ on a finite grid in $[0,1)$. Their intended uniform distribution is an approximation, and their serial dependence must be assessed separately from the generator's period.

Choose integers $M>1$, $a$, $c$ and a seed $S_0$. Iterate $S_{n+1}=(a{S}_n+c)\mathrm{mod}M$ and return $U_n=S_n/M$. This gives a deterministic finite-state pseudorandom number generator with output in $[0,1)$. A nonzero increment gives a mixed generator; $c=0$ gives a multiplicative generator. Its period is at most $M$, but even a full period does not guarantee good multidimensional uniformity or statistical independence.

A linear congruential generator has period $M$ for every seed if and only if $\gcd (c,M)=1$, every prime dividing $M$ divides $a-1$, and $4\mid M$ implies $4\mid a-1$. The coprimality of $c$ prevents the orbit from being trapped in a residue class; the multiplier conditions permit full-period lifting through each prime power. Combining the prime-power periods by the Chinese remainder theorem gives period $M$. For $M=12^k=2^{2k}{3}^k$, the multiplier criterion reduces to $a\equiv 1(\mathrm{mod}12)$, together with $\gcd (c,6)=1$. A positive increment alone is insufficient.