Non-uniform random variate generation

Non-uniform random variate generationorpseudo-random number samplingis thenumericalpractice of generatingpseudo-random numbers(PRN) that follow a givenprobability distribution. Methods are typically based on the availability of auniformly distributedPRN generator.Computational algorithms are then used to manipulate a singlerandom variate,X,or often several such variates, into a new random variateYsuch that these values have the required distribution. The first methods were developed forMonte-Carlo simulationsin theManhattan project,published byJohn von Neumannin the early 1950s.

Finite discrete distributions

For adiscrete probability distributionwith a finite numbernof indices at which theprobability mass functionftakes non-zero values, the basic sampling algorithm is straightforward. The interval [0, 1) is divided innintervals [0,f(1)), [f(1),f(1) +f(2)),... The width of intervaliequals the probabilityf(i). One draws a uniformly distributed pseudo-random numberX,and searches for the indexiof the corresponding interval. The so determinediwill have the distributionf(i).

Formalizing this idea becomes easier by using the cumulative distribution function

$F(i)=\sum _{j=1}^{i}f(j).$

It is convenient to setF(0) = 0. Thenintervals are then simply [F(0),F(1)), [F(1),F(2)),..., [F(n− 1),F(n)). The main computational task is then to determineifor whichF(i− 1) ≤X<F(i).

This can be done by different algorithms:

• Linear search,computational time linear inn.
• Binary search,computational time goes with logn.
• Indexed search,also called thecutpoint method.
• Alias method,computational time is constant, using some pre-computed tables.
• There are other methods that cost constant time.

Continuous distributions

Generic methods for generatingindependentsamples:

• Rejection samplingfor arbitrary density functions
• Inverse transform samplingfor distributions whoseCDFis known
• Ratio of uniforms,combining a change of variables and rejection sampling
• Slice sampling
• Ziggurat algorithm,for monotonically decreasing density functions as well as symmetric unimodal distributions
• Convolution random number generator,not a sampling method in itself: it describes the use of arithmetics on top of one or more existing sampling methods to generate more involved distributions.

Generic methods for generatingcorrelatedsamples (often necessary for unusually-shaped or high-dimensional distributions):

• Markov chain Monte Carlo,the general principle
• Metropolis–Hastings algorithm
• Gibbs sampling
• Slice sampling
• Reversible-jump Markov chain Monte Carlo,when the number of dimensions is not fixed (e.g. when estimating amixture modeland simultaneously estimating the number of mixture components)
• Particle filters,when the observed data is connected in aMarkov chainand should be processed sequentially

For generating anormal distribution:

• Box–Muller transform
• Marsaglia polar method

For generating aPoisson distribution:

• SeePoisson distribution#Generating Poisson-distributed random variables

Software libraries

GNU Scientific Libraryhas a section entitled "Random Number Distributions" with routines for sampling under more than twenty different distributions.

See also

• Beta distribution#Random variate generation
• Dirichlet distribution#Random variate generation
• Exponential distribution#Random variate generation
• Gamma distribution#Random variate generation
• Geometric distribution#Random variate generation
• Gumbel distribution#Random variate generation
• Laplace distribution#Random variate generation
• Multinomial distribution#Random variate distribution
• Pareto distribution#Random variate generation
• Poisson distribution#Random variate generation

Literature

• Devroye, L. (1986)Non-Uniform Random Variate Generation.New York: Springer
• Fishman, G.S. (1996)Monte Carlo. Concepts, Algorithms, and Applications.New York: Springer
• Hörmann, W.; J Leydold, G Derflinger (2004,2011)Automatic Nonuniform Random Variate Generation.Berlin: Springer.
• Knuth, D.E.(1997)The Art of Computer Programming,Vol. 2Seminumerical Algorithms,Chapter 3.4.1 (3rd edition).
• Ripley, B.D. (1987)Stochastic Simulation.Wiley.