Non-uniform random variate generation orpseudo-random number sampling is thenumerical practice 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 variateY such that these values have the required distribution.The first methods were developed forMonte-Carlo simulations in theManhattan Project,^{[citation needed]} published byJohn von Neumann in the early 1950s.^[1]

For adiscrete probability distribution with a finite numbern of indices at which theprobability mass functionf takes non-zero values, the basic sampling algorithm is straightforward. The interval [0, 1) is divided inn intervals [0, f(1)), [f(1), f(1) + f(2)), ... The width of intervali equals the probability f(i).One draws a uniformly distributed pseudo-random numberX, and searches for the indexi of the corresponding interval. The so determinedi will have the distribution f(i).

Formalizing this idea becomes easier by using the cumulative distribution function

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

It is convenient to setF(0) = 0. Then intervals are then simply [F(0), F(1)), [F(1), F(2)), ..., [F(n − 1), F(n)). The main computational task is then to determinei for whichF(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 thecutpoint 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 generatingindependent samples:

• Rejection sampling for arbitrary density functions
• Inverse transform sampling for distributions whoseCDF 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 generatingcorrelated 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 amixture model and simultaneously estimating the number of mixture components)
• Particle filters, when the observed data is connected in aMarkov chain and 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

• 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

• 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.

• Pseudorandom number generators
• Non-uniform random numbers

• Wikipedia articles needing page number citations from June 2011
• Use American English from March 2019
• All Wikipedia articles written in American English
• Articles with short description
• Short description matches Wikidata
• All articles with unsourced statements
• Articles with unsourced statements from June 2011