10.3 Rejection Sampling
Result 10.3.1. Suppose the target density \(f\) satisfies \(f(x)\leq c\,g(x)\) for all \(x\), where \(g\) is a density that can already be simulated and \(c\geq 1\) is constant. Repeat: draw \(Y\) from \(g\) and \(U\sim \) UNIF\((0,1)\) independently; accept \(X=Y\) if \[U \leq \frac {f(Y)}{c\,g(Y)},\] otherwise discard and start again. The accepted value has density \(f\), and the expected number of attempts per acceptance is \(c\).
Proof. Conditioning on acceptance, \[P\left (Y\leq x,\ \text {accept}\right ) = \int _{-\infty }^{x} \frac {f(y)}{c\,g(y)}\,g(y)\,dy = \frac {1}{c}\int _{-\infty }^{x} f(y)\,dy .\] Taking \(x\rightarrow \infty \) gives \(P(\text {accept}) = 1/c\), so the expected number of trials is \(c\), and dividing, \[P\left (Y\leq x \mid \text {accept}\right ) = \int _{-\infty }^{x}f(y)\,dy ,\] which is the required distribution function. □
Remark. The constant \(c\) is the cost of the method: it is the expected number of draws per accepted value, so an envelope that fits badly is expensive. Since \(c \geq \sup _x f(x)/g(x)\), the art is choosing \(g\) with the same shape and heavier tails than \(f\). A normal envelope for a Cauchy target fails outright, because the ratio is unbounded — the tails of the target are heavier than the envelope’s, and no finite \(c\) exists.
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.