Talk:Inverse transform sampling: Difference between revisions

Revision as of 18:51, 4 March 2009

Latest revision as of 23:54, 3 February 2024

(10 intermediate revisions by 8 users not shown)

Line 1:

{{WikiProject banner shell|class=B|

{{maths rating

{{WikiProject Mathematics|importance= Low |ACD=}}

|class= B

{{WikiProject Statistics|importance = Lowlow}}

}}

|field= probability and statistics

|vital=

|frequentlyviewed=

|ACD=

}}

{{WPStatistics}}

==Link==

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

Line 14 ⟶ 9:

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. [[User:89.244.181.5|89.244.181.5]] 17:29, 6 September 2007 (UTC)

== Moved from probability distribution ==

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

== Simulated sampling ==

{{Main|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).

<pre>

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)

</pre>

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.

<pre>

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

</pre>

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. [[User:Jackzhp|Jackzhp]] ([[User talk:Jackzhp|talk]]) 22:38, 28 January 2011 (UTC)

:In fact, it works for the general case using the generalized inverse. Details can be found [https://math.stackexchange.com/questions/4610019/inverse-transform-sampling-for-general-random-variables here]. [[User:Sowhates|Sowhates]] ([[User talk: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}) ?? <!-- Template:Unsigned --><span class="autosigned" style="font-size:85%;">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Aditya8795|Aditya8795]] ([[User talk:Aditya8795#top|talk]] • [[Special:Contributions/Aditya8795|contribs]]) 17:29, 9 August 2018 (UTC)</span>

:Yes; that's it; I've re-formatted with a superscript to make this clearer. [[User:Klbrain|Klbrain]] ([[User talk: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. <!-- Template:Unsigned --><span class="autosigned" style="font-size:85%;">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Azmisov|Azmisov]] ([[User talk:Azmisov#top|talk]] • [[Special:Contributions/Azmisov|contribs]]) 20:04, 21 December 2021 (UTC)</span> <!--Autosigned by SineBot-->