Pseudorandom number generator

A pseudorandom number generator (PRNG) is an algorithm which when run generates a sequence of numbers, the elements of which are approximately independent. Most such algorithms attempt to produce samples that are uniformly distributed. Common variants are Linear Congruential Generators, Lagged Fibonacci Generators, Linear Shift Feedback Registers and Generalised Shift Feedback Registers.

"see also" Blum Blum Shub, Mersenne Twister.

Because a PRNG is a deterministic algorithm, its output has certain properties that a true random sequence would not exhibit. One of these is guaranteed periodicity - it is certain that given a sufficient number of iterations, the generator will revisit its initial state. In addition, a PRNG can be started from an arbitrary starting point, or seed state, and will always produce an identical sequence from that point.

In practice, many PRNGs exhibit artefacts which can cause them to fail statistical significance tests. These include:

   Shorter than expected periods for some seed states (see Linear Congruential Generators).
   Poor dimensional distribution (see Linear Congruential Generators).
   Some bits are more random than others (see Linear Congruential Generators).

The recent invention of the Mersenne Twister algorithm, by Makoto Matsumoto and Takuji Nishimura in 1997, has meant that it is now possible to choose a random number generator which suffers from none of these defects, and in addition has a colossal period of 2^19937-1 iterations. It is now becoming increasingly accepted as the random number generator of choice for all statistical simulations and generative modeling.