Content deleted Content added
m Proper minus signs and other cleanup. Report bugs, errors, and suggestions at User talk:MinusBot |
Citation bot (talk | contribs) Add: title. Changed bare reference to CS1/2. | Use this bot. Report bugs. | Suggested by BrownHairedGirl | Linked from User:BrownHairedGirl/Articles_with_bare_links | #UCB_webform_linked 338/2189 |
||
Line 25:
Computationally, this method involves computing the [[quantile function]] of the distribution — in other words, computing the [[cumulative distribution function]] (CDF) of the distribution (which maps a number in the ___domain to a probability between 0 and 1) and then inverting that function. This is the source of the term "inverse" or "inversion" in most of the names for this method. Note that for a [[discrete distribution]], computing the CDF is not in general too difficult: we simply add up the individual probabilities for the various points of the distribution. For a [[continuous distribution]], however, we need to integrate the [[probability density function]] (PDF) of the distribution, which is impossible to do analytically for most distributions (including the [[normal distribution]]). As a result, this method may be computationally inefficient for many distributions and other methods are preferred; however, it is a useful method for building more generally applicable samplers such as those based on [[rejection sampling]].
For the [[normal distribution]], the lack of an analytical expression for the corresponding quantile function means that other methods (e.g. the [[Box–Muller transform]]) may be preferred computationally. It is often the case that, even for simple distributions, the inverse transform sampling method can be improved on:<ref>{{cite book |author=Luc Devroye |url=http://www.eirene.de/Devroye.pdf |title=Non-Uniform Random Variate Generation |publisher=Springer-Verlag |place=New York |year=1986}}</ref> see, for example, the [[ziggurat algorithm]] and [[rejection sampling]]. On the other hand, it is possible to approximate the quantile function of the normal distribution extremely accurately using moderate-degree polynomials, and in fact the method of doing this is fast enough that inversion sampling is now the default method for sampling from a normal distribution in the statistical package [[R (programming language)|R]].<ref>{{Cite web|url=https://stat.ethz.ch/R-manual/R-devel/library/base/html/Random.html|title = R: Random Number Generation}}</ref>
==Definition==
| |||