Random Number Generation

Random number generation produces sequences of numbers that behave as if drawn from a target probability distribution, supplying the stochastic inputs on which Monte Carlo simulation, resampling, and randomized algorithms depend.

Definition

Random number generation is the construction and analysis of algorithms that generate numbers approximating independent draws from a specified probability distribution, beginning from a uniform source on the unit interval.

Scope

This area covers the deterministic algorithms that produce uniform pseudorandom sequences, the transformations that turn uniform variates into samples from arbitrary distributions, acceptance-rejection schemes for densities that cannot be inverted in closed form, and variance-reduction devices that improve the efficiency of simulation estimators. Hardware entropy sources and cryptographic generators are noted as boundary cases but the focus is on generators for statistical simulation.

Sub-topics

• inverse transform sampling
• pseudorandom number generators
• rejection sampling
• variance reduction techniques

Core questions

• How can a deterministic algorithm produce sequences that pass statistical tests for randomness and uniformity?
• Given a uniform generator, how are samples obtained from an arbitrary target distribution?
• When direct inversion is intractable, how does acceptance-rejection sample from a density?
• How can the variance of a simulation estimator be reduced without increasing the sample size?

Key theories

Pseudorandom uniform generation

A recurrence with a long period and good lattice structure produces deterministic sequences that are statistically indistinguishable from independent uniform draws; quality is assessed by period length, equidistribution, and batteries of empirical tests.

Transformation methods

The probability integral transform and its relatives map uniform variates to a target distribution: applying the inverse cumulative distribution function yields exact samples whenever it can be evaluated.

Acceptance-rejection sampling

By proposing from an easy-to-sample envelope that dominates the target density and accepting proposals with a probability equal to the density ratio, one obtains exact samples from densities that cannot be inverted, at a cost set by the envelope's tightness.

Clinical relevance

Reliable random number generation underpins Monte Carlo integration, bootstrap and permutation inference, Bayesian posterior sampling, randomized experiments and simulation studies across the sciences; poor generators with short periods or lattice artifacts can silently bias simulation results, so generator quality is a foundational reproducibility concern.

History

Early Monte Carlo work at Los Alamos relied on simple congruential and middle-square schemes; subsequent decades exposed their defects and produced rigorous theory of lattice structure and equidistribution, culminating in long-period generators and standardized test suites for assessing randomness.

Key figures

• Luc Devroye
• Donald Knuth
• Pierre L'Ecuyer
• John von Neumann

Seminal works

• devroye1986
• knuth1997

Frequently asked questions

Are computer-generated random numbers truly random?

Most are pseudorandom: a deterministic algorithm produces a reproducible sequence from a seed. Well-designed generators have very long periods and pass statistical tests, so the output is indistinguishable from genuine randomness for simulation purposes, while remaining exactly reproducible when the seed is fixed.

Why is the inverse cumulative distribution function so central?

If U is uniform on (0,1), then applying the inverse cumulative distribution function of any distribution to U yields a sample from that distribution. This probability integral transform is exact and is the default method whenever the inverse can be computed.