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 on.

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 consigned most of these problems to the history books, however. It has a colossal period of 2^19937-1 iterations, is proven to be equidistributed in 623 dimensions (for 32-bit values) and runs faster than all but the worst Linear Congruential Generators. It is now becoming increasingly accepted as the random number generator of choice for all statistical simulations and generative modeling.