Non-uniform random variate generation
Non-uniform random variate generation or pseudo-random number sampling is the numerical practice of generating pseudo-random numbers 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 intervalOne 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.
Formalizing this idea becomes easier by using the [cumulative distribution function
It is convenient to set F = 0. The n intervals are then simply F, F), [F, F),..., [F, F). The main computational task is then to determine i for which F ≤ X < F.
This can be done by different algorithms:
- [Linear search
Continuous distributions
- 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.
- 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
- Particle filters, when the observed data is connected in a Markov chain and should be processed sequentially
For generating a Poisson distribution:
- See Poisson distribution#Generating Poisson-distributed random variables
Software libraries
| Library | Beta | Binomial | Cauchy | Chi-squared | Dirichlet | Exponential | F | Gamma | Geometric | Gumbel | Hypergeometric | Laplace | Logistic | Log-normal | Logarithmic | Multinomial | Multivariate hypergeometric | Multivariate normal | Negative binomial | Noncentral chi-squared | Noncentral F | Normal | Pareto | Poisson | Power | Rayleigh | Students's t | Triangular | von Mises | Wald | Zeta |
| NumPy | |||||||||||||||||||||||||||||||
| GNU Scientific Library |
Literature
- Devroye, L. . New York: Springer
- Fishman, G.S. . New York: Springer
- Hörmann, W.; J Leydold, G Derflinger . Berlin: Springer.
- Knuth, D.E. The Art of Computer Programming, Vol. 2 Seminumerical Algorithms, Chapter 3.4.1.
- Ripley, B.D. Stochastic Simulation. Wiley.
Category:Non-uniform random numbers