Inverse transform sampling

related topics
{math, number, function}
{rate, high, increase}

Inverse transform sampling, also known as the inverse probability integral transform or inverse transformation method or Smirnov transform, is a method for generating sample numbers at random from any probability distribution given its cumulative distribution function (cdf). Subject to the restriction that the distribution is continuous, this method is generally applicable (and can be computationally efficient if the cdf can be analytically inverted), but may be too computationally expensive in practice for some probability distributions. The Box-Muller transform is an example of an algorithm that is specific to generating samples from a normal distribution, but is more computationally efficient. It is often the case that, even for simple distributions, the inverse transform sampling method can be improved on[1]: see, for example, the ziggurat algorithm and rejection sampling.

Contents

Definition

The probability integral transform states that if X is a continuous random variable with cumulative distribution function FX, then the random variable Y = FX(X) has a uniform distribution on [0, 1]. The inverse probability integral transform is just the inverse of this: specifically, if Y has a uniform distribution on [0, 1] and if X has a cumulative distribution FX, then the cumulative distribution function of the random variable F_X^{-1}(Y) is FX .

The method

The problem that the inverse transform sampling method solves is as follows:

Many programming languages have the ability to generate pseudorandom numbers which are effectively distributed according to the standard uniform distribution. If a random variable has that distribution, then the probability of its falling within any subinterval (a, b) of the interval from 0 to 1 is just the length ba of that subinterval.

Full article ▸

related documents
Discrete probability distribution
Disjunctive normal form
Irreducible fraction
Urysohn's lemma
Unit interval
Unitary matrix
Injective function
Algebraic closure
Euler's identity
NP-equivalent
Bernoulli's inequality
Parse tree
Klein four-group
Null set
Complete graph
Class (set theory)
Elias gamma coding
Earley parser
Minkowski's theorem
Linear function
Special functions
Cipher
Automorphism
Inner automorphism
Regular graph
Connectedness
Just another Perl hacker
Profinite group
Field of fractions
Specification language