title: Non-uniform random variate generation
text: # 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, 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)=\sum _{j=1}^{i}f(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:
  
  * Linear search, computational time linear in n.
  * Binary search, computational time goes with log n.
  * Indexed search, also called the cutpoint 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 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:
  
  * Box–Muller transform
  * Marsaglia polar method
  
  For generating a Poisson distribution:
  
  * See Poisson distribution#Generating Poisson-distributed random variables
  
  ## Software libraries
  
  GNU Scientific Library has a section entitled "Random Number Distributions" with routines for sampling under more than twenty different distributions.
  
  