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 BoxMuller 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 F_{X}, then the random variable Y = F_{X}(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 F_{X}, then the cumulative distribution function of the random variable is F_{X} .
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 b − a of that subinterval.
Full article ▸
