View source for Alec's c.d.f-sidestepping sampling method

: See [[generating samples from a distribution]] for and overview of methods used
__TOC__
==Algorithm==
Let {{M|f(x)}} be a [[probability density function|p.d.f]] for which computing {{M|F^{-1}(x)}} is either difficult, impractical, impossible or otherwise unavailable, but where {{M|f(x)}} itself is easy to compute.


Suppose that either:
* {{M|\exists a,b\in\mathbb{R}\big[\forall x\in[a,b]\subseteq\mathbb{R}[f(x)>0]\big]}}, there exists a [[closed interval]], {{M|[a,b]}} for which {{M|f(x)>0}} on over, or:
* {{M|\forall x\in\mathbb{R}[f(x)>0]}} - {{M|f(x)>0}} everywhere
then we will sample {{M|f(x)}} over {{M|[a,b]}} or {{M|\mathbb{R} }}
* [[herein]] we will use {{M|A:\eq[a,b]}} or {{M|A:\eq\mathbb{R} }} for whichever case is chosen


Define the following function carefully:
* Define {{M|h:A\rightarrow\mathbb{R} }} such that {{M|\forall x\in A[h(x)>f(x)]}}

Then the algorithm proceeds as follows:
===Steps===
To generate {{M|X}}, a sample from the distribution {{M|f}}:
# Define {{M|g:A\rightarrow\mathbb{R} }} by {{MM|g(x):\eq\frac{h(x)}{\int_Ah(t)\mathrm{d}t} }} - note that this makes {{M|g}} itself a [[probability density function|p.d.f]]
# [[Generating samples from the inverse of a cumulative distribution function|Generate]] {{M|Y}} on {{M|A}} from {{M|g}}
#* if {{M|G:A\rightarrow [0,1]\subseteq\mathbb{R} }}, or {{M|G(x)}}, is the [[cumulative distribution function|c.d.f]] of {{M|g}} then {{M|G^{-1}:[0,1]\rightarrow A}} is how we usually sample from the distribution, {{M|g}}, we generate a random number, say {{M|y}} [[continuous uniform distribution|uniformly]] from {{M|[0,1]}}, then {{M|Y\eq G^{-1}(y)}} is a random sample from {{M|g}}
# Generate {{M|Z}} as an (independent of {{M|Y}}) [[continuous uniform distribution|uniformly]] on {{M|[0,1]}}
# If {{M|Z h(Y) \le f(Y) }} then:
#:* Define {{M|X:\eq Y}}
#: Else
#:* Goto step {{M|2}}


Note that other methods may be used to generate either {{M|Y}} or {{M|Z}}, it is only important that we generate them somehow.


It is possible (although extremely unlikely for high numbers) for this to loop a lot of times before generating a sample, that is the trade-off it makes compared with [[generating samples from the inverse of a cumulative distribution function]]. The better the {{M|h}} approximation is to {{M|f}} the higher the throughput of generated samples.

Also unlike [[generating samples from the inverse of a cumulative distribution function]] it requires ''at least 2'' generated values unlike the inverse c.d.f generating method which requires only on generated uniform value on {{M|[0,1]}} always.
==Proof==
{{Requires proof|grade=B|msg=The gist is outlined}}
{{XXX|Take a picture of sheet '''242'''}} and upload
==Notes==
<references group="Note"/>
==References==
<references/>
[[Category:Statistics]][[Category:Probability]]
{{Algorithm Of|Probability|Statistics}}