What makes one pseudorandom generator better than another?

A good generator has a very long period, distributes its outputs uniformly even in many dimensions, passes standard statistical test batteries, and is fast and reproducible. Poor generators can have short periods or visible lattice patterns that bias simulations.

Why does the seed matter?

The seed fixes the starting state, so the entire sequence is determined by it. Recording the seed makes a simulation exactly reproducible, while choosing seeds carelessly can cause overlapping or correlated streams across parallel runs.

Pseudorandom Number Generators

A pseudorandom number generator is a deterministic recurrence that, from an initial seed, produces a long reproducible sequence of numbers that mimics independent draws from the uniform distribution on the unit interval.

Definition

A pseudorandom number generator is an algorithm defined by a state, a transition function that advances the state, and an output function that maps each state to a number, producing a periodic sequence intended to be statistically indistinguishable from uniform random numbers.

Scope

This topic covers the construction of uniform generators (linear congruential, lagged-Fibonacci, generalized feedback shift register, and combined generators), the structural properties that determine their quality such as period length and lattice or equidistribution behaviour, and the empirical and theoretical tests used to certify them. Cryptographically secure generators are mentioned only as a contrasting design goal.

Core questions

What recurrences yield long periods and good high-dimensional uniformity?
How is the quality of a generator measured by its lattice structure and equidistribution?
Which empirical test batteries detect departures from randomness?
How are generators seeded and combined to extend period and improve statistical properties?

Key concepts

Seed and state
Period length
Equidistribution
Lattice structure
Spectral test
Combined generators

Key theories

Linear recurrence generators: Linear congruential and shift-register recurrences advance an integer state by modular arithmetic; their period and the lattice structure of successive outputs are determined by number-theoretic properties of the multiplier and modulus.
Equidistribution and the Mersenne Twister: Generators based on twisted generalized feedback shift registers achieve enormous periods and provable equidistribution in many dimensions, making them a widely adopted default for statistical simulation.

Clinical relevance

The default generator in a statistical package determines the reproducibility and validity of every simulation, bootstrap and Monte Carlo result it produces; understanding period and equidistribution helps practitioners avoid generators whose hidden regularities can corrupt high-dimensional simulations.

History

Lehmer proposed the linear congruential method in 1949; later analysis revealed the lattice defects of poorly chosen parameters, motivating the spectral test, combined generators, and ultimately long-period equidistributed designs such as the Mersenne Twister in 1998.

Key figures

Donald Knuth
Pierre L'Ecuyer
Makoto Matsumoto
Derrick Henry Lehmer

Seminal works

knuth1997
matsumoto1998

Frequently asked questions

What makes one pseudorandom generator better than another?: A good generator has a very long period, distributes its outputs uniformly even in many dimensions, passes standard statistical test batteries, and is fast and reproducible. Poor generators can have short periods or visible lattice patterns that bias simulations.
Why does the seed matter?: The seed fixes the starting state, so the entire sequence is determined by it. Recording the seed makes a simulation exactly reproducible, while choosing seeds carelessly can cause overlapping or correlated streams across parallel runs.