Talk:Inverse transform sampling

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated B-class, Low-importance)
WikiProject Mathematics
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)
WikiProject icon

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-Class article 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.
 

Link[edit]

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[edit]

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

Simulated sampling[edit]

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)
    return last key we added

  return cdfInverse

Note that often, mathematics environments and computer algebra systems will have some way to represent probability distributions and sample from them. This functionality might even have been developed in third-party libraries. Such packages greatly facilitate such sampling, most likely have optimizations for common distributions, and are likely to be more elegant than the above bare-bones solution.


discontinuous case[edit]

I heard that the the inverse method also works for the discontinuous case, despite the discontinuity. Jackzhp (talk) 22:38, 28 January 2011 (UTC)