Alec's c.d.f-sidestepping sampling method

See generating samples from a distribution for and overview of methods used

Algorithm

Let $f(x)$ be a p.d.f for which computing $F^{-1}(x)$ is either difficult, impractical, impossible or otherwise unavailable, but where $f(x)$ itself is easy to compute.

Suppose that either:

• $\exists a,b\in\mathbb{R}\big[\forall x\in[a,b]\subseteq\mathbb{R}[f(x)>0]\big]$, there exists a closed interval, $[a,b]$ for which $f(x)>0$ on over, or:
• $\forall x\in\mathbb{R}[f(x)>0]$ - $f(x)>0$ everywhere

then we will sample $f(x)$ over $[a,b]$ or $\mathbb{R}$

• herein we will use $A:\eq[a,b]$ or $A:\eq\mathbb{R}$ for whichever case is chosen

Define the following function carefully:

• Define $h:A\rightarrow\mathbb{R}$ such that $\forall x\in A[h(x)>f(x)]$

Then the algorithm proceeds as follows:

Steps

To generate $X$, a sample from the distribution $f$:

1. Define $g:A\rightarrow\mathbb{R}$ by $$g(x):\eq\frac{h(x)}{\int_Ah(t)\mathrm{d}t}$$ - note that this makes $g$ itself a p.d.f
2. Generate $Y$ on $A$ from $g$
   • if $G:A\rightarrow [0,1]\subseteq\mathbb{R}$, or $G(x)$, is the c.d.f of $g$ then $G^{-1}:[0,1]\rightarrow A$ is how we usually sample from the distribution, $g$, we generate a random number, say $y$ uniformly from $[0,1]$, then $Y\eq G^{-1}(y)$ is a random sample from $g$
3. Generate $Z$ as an (independent of $Y$) uniformly on $[0,1]$
4. If $Z h(Y) \le f(Y)$ then:

   • Define $X:\eq Y$

   Else

   • Goto step $2$

Note that other methods may be used to generate either $Y$ or $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 $h$ approximation is to $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 $[0,1]$ always.

Proof

Grade: B

This page requires one or more proofs to be filled in, it is on a to-do list for being expanded with them.

Please note that this does not mean the content is unreliable. Unless there are any caveats mentioned below the statement comes from a reliable source. As always, Warnings and limitations will be clearly shown and possibly highlighted if very important (see template:Caution et al).
The message provided is:

The gist is outlined

TODO: Take a picture of sheet 242

and upload