Inverse transform sampling

From Wikipedia, the free encyclopedia

Inverse transform sampling, also known as the probability integral transform, is a method of generating sample numbers at random from any probability distribution given its cumulative distribution function (cdf). This method is generally applicable, but may be too computationally expensive in practice for some probability distributions. See Box-Muller transform for an example of an algorithm which is less general but more computationally efficient.

Contents

[edit] Definition

The "probability integral transform" states that if X is a continuous random variable with a strictly increasing cumulative distribution function FX, and if Y = FX(X), then Y has a uniform distribution on [0, 1].

[edit] The method

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

  • Let X be a random variable whose distribution can be described by the cdf F.
  • We want to generate values of X which are distributed according to this distribution.

Many programming languages have the ability to generate pseudo-random 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.

The inverse transform sampling method works as follows:

  1. Generate a random number from the standard uniform distribution; call this u.
  2. Compute the value x such that F(x) = u; call this xchosen.
  3. Take xchosen to be the random number drawn from the distribution described by F.

Expressed differently, given a continuous uniform variable U in [0, 1] and an invertible distribution function F, the random variable X = F −1(U) has distribution F (or, X is distributed F).

A treatment of such inverse functions as objects satisfying differential equations can be given.[1] Some such differential equations admit explicit power series solutions, despite their non-linearity.

[edit] Proof of correctness

Let F be a continuous cumulative distribution function, and let F − 1 be its inverse function:[2]

F^{-1}(u) = \inf\;\{x \mid F(x)=u, 0<u<1\}

Claim: If U is a uniform random variable on (0, 1) then F − 1(U) follows the distribution F.

Proof:

\begin{align} & \Pr(F^{-1}(U) \leq x) \\ & {} = \Pr(\inf\;\{x \mid F(x)=U\} \leq x)\quad \text{(by definition of }F^{-1}) \\ & {} = \Pr(U \leq F(x)) \quad \text{(applying }F,\text{ which is monotonic, to both sides)} \\ & {} = F(x)\quad \text{(because }\Pr(U \leq y) = y,\text{ since }U\text{ is uniform on the unit interval)} \end{align}

[edit] See also

[edit] References

  1. ^ Steinbrecher, G., Shaw, W.T. (2008). Quantile mechanics. European Journal of Applied Mathematics 19 (2): 87-112.
  2. ^ Luc Devroye. Non-Uniform Random Variate Generation. New York: Springer-Verlag, 1986. (online) See chapter 2, section 2, p. 28.

[edit] External links