# Talk:Inverse transform sampling

WikiProject Mathematics (Rated B-class, Low-importance)
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
 B Class
 Low Importance
Field: Probability and statistics
WikiProject Statistics (Rated B-class, Low-importance)

This article is within the scope of the WikiProject Statistics, a collaborative effort to improve the coverage of statistics on Wikipedia. If you would like to participate, please visit the project page or join the discussion.

B  This article has been rated as B-Class on the quality scale.
Low  This article has been rated as Low-importance on the importance scale.

## Contents

The link in the reference at the bottom is 404'ed. (Non-Uniform Random Variate Generation)

Here are working links: Book Chapter 2 as of 13:45, 4 August 2006 (UTC)

Can this page also show up on a search for "Inversion Method"? I have looked all over for this article, and then found it through a link somewhere else which then linked through to this article with the text "Inversion Method". I would do this but am not sure how. 89.244.181.5 17:29, 6 September 2007 (UTC)

## Moved from probability distribution

This could be incorporated here somewhere MisterSheik (talk) 00:37, 22 October 2010 (UTC)

## Simulated sampling

The following algorithm lets one sample from a probability distribution (either discrete or continuous). This algorithm assumes that one has access to the inverse of the cumulative distribution (easy to calculate with a discrete distribution, can be approximated for continuous distributions) and a computational primitive called "random()" which returns an arbitrary-precision floating-point-value in the range of [0,1).

define function sampleFrom(cdfInverse (type="function")):
// input:
//   cdfInverse(x) - the inverse of the CDF of the probability distribution
//     example: if distribution is [[Gaussian]], one can use a [[Taylor approximation]] of the inverse of [[erf]](x)
//     example: if distribution is discrete, see explanation below pseudocode
// output:
//   type="real number" - a value sampled from the probability distribution represented by cdfInverse

r = random()

while(r == 0):    (make sure r is not equal to 0; discontinuity possible)
r = random()

return cdfInverse(r)


For discrete distributions, the function cdfInverse (inverse of cumulative distribution function) can be calculated from samples as follows: for each element in the sample range (discrete values along the x-axis), calculating the total samples before it. Normalize this new discrete distribution. This new discrete distribution is the CDF, and can be turned into an object which acts like a function: calling cdfInverse(query) returns the smallest x-value such that the CDF is greater than or equal to the query.

define function dataToCdfInverse(discreteDistribution (type="dictionary"))
// input:
//   discreteDistribution - a mapping from possible values to frequencies/probabilities
//     example: {0 -> 1-p, 1 -> p} would be a [[Bernoulli distribution]] with chance=p
//     example: setting p=0.5 in the above example, this is a [[fair coin]] where P(X=1)->"heads" and P(X=0)->"tails"
// output:
//   type="function" - a function that represents (CDF^-1)(x)

define function cdfInverse(x):
integral = 0
go through mapping (key->value) in sorted order, adding value to integral...
stop when integral > x (or integral >= x, doesn't matter)