Non-uniform random variate generation

Non-uniform random variate generation or pseudo-random number sampling is the numerical practice of generating pseudo-random numbers (PRN) that follow a given probability distribution. Methods are typically based on the availability of a uniformly distributed PRN generator. Computational algorithms are then used to manipulate a single random variate, X, or often several such variates, into a new random variate Y such that these values have the required distribution. The first methods were developed for Monte-Carlo simulations in the Manhattan Project,[citation needed] published by John von Neumann in the early 1950s.

Finite discrete distributions

For a discrete probability distribution with a finite number n of indices at which the probability mass function f takes non-zero values, the basic sampling algorithm is straightforward. The interval [0, 1) is divided in n intervals [0, f(1)), [f(1), f(1) + f(2)), ... The width of interval i equals the probability f(i). One draws a uniformly distributed pseudo-random number X, and searches for the index i of the corresponding interval. The so determined i will have the distribution f(i).

Formalizing this idea becomes easier by using the cumulative distribution function

F(i)=∑j=1if(j).

It is convenient to set F(0) = 0. The n intervals are then simply [F(0), F(1)), [F(1), F(2)), ..., [F(n − 1), F(n)). The main computational task is then to determine i for which F(i − 1) ≤ X < F(i).

This can be done by different algorithms:

Continuous distributions

Generic methods for generating independent samples:

Generic methods for generating correlated samples (often necessary for unusually-shaped or high-dimensional distributions):

For generating a normal distribution:

For generating a Poisson distribution:

Software libraries

Random distributions provided by software libraries
Distribution NumPy GNU Scientific Library
Beta Yes Yes
Binomial Yes Yes
Cauchy Yes Yes
Chi-squared Yes Yes
Dirichlet Yes Yes
Exponential Yes Yes
F Yes Yes
Gamma Yes Yes
Geometric Yes Yes
Gumbel Yes Yes
Hypergeometric Yes Yes
Laplace Yes Yes
Logistic Yes Yes
Log-normal Yes Yes
Logarithmic Yes Yes
Multinomial Yes Yes
Multivariate hypergeometric Yes No
Multivariate normal Yes Yes
Negative binomial Yes Yes
Noncentral chi-squared Yes No
Noncentral F Yes No
Normal Yes Yes
Pareto Yes Yes
Poisson Yes Yes
Power Yes ?
Rayleigh Yes Yes
Students's t Yes Yes
Triangular Yes No
von Mises Yes No
Wald Yes No
Zeta Yes No

See also

Literature