Loading AI tools

Generating pseudo-random numbers that follow a probability distribution From Wikipedia, the free encyclopedia

**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.^{[1]}

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

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:

- Linear search, computational time linear in
*n*. - Binary search, computational time goes with log
*n*. - Indexed search,
^{[2]}also called the*cutpoint method*.^{[3]} - Alias method, computational time is constant, using some pre-computed tables.
- There are other methods that cost constant time.
^{[4]}

Generic methods for generating independent samples:

- Rejection sampling for arbitrary density functions
- Inverse transform sampling for distributions whose CDF is 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 generating correlated samples (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 a mixture model and simultaneously estimating the number of mixture components)
- Particle filters, when the observed data is connected in a Markov chain and should be processed sequentially

For generating a normal distribution:

For generating a Poisson distribution:

GNU Scientific Library has a section entitled "Random Number Distributions" with routines for sampling under more than twenty different distributions.^{[5]}

- 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

Seamless Wikipedia browsing. On steroids.

Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.

Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.