Talk:Inverse transform sampling

Link

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

Main article: Inverse transform 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)
    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

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

In fact, it works for the general case using the generalized inverse. Details can be found here. Sowhates (talk) 09:24, 3 January 2023 (UTC)

Unclear value in table

Someone should edit 1-2^{-52} to something that makes sense. is it supposed to be 1 - 1/(2^{52})  ?? — Preceding unsigned comment added by Aditya8795 (talk • contribs) 17:29, 9 August 2018 (UTC)

Yes; that's it; I've re-formatted with a superscript to make this clearer. Klbrain (talk) 10:15, 24 June 2021 (UTC)

Resolved

Long-winded intro

The concept is pretty simple: to generate a random sample X with CDF, you can take Y from a uniform distribution and transform it via X = invCDF(Y).

I think the intro should be much more concise, and clearly get to the point. I shouldn't need to dig through the article for 2 minutes to figure out how inverse transform sampling works. — Preceding unsigned comment added by Azmisov (talk • contribs) 20:04, 21 December 2021 (UTC)