Rejection sampling

Remarks

For a measurable set $A$, $P(Y_j \in A,\ \text{accepted}) = \int_A g(y) \frac{f(y)}{M g(y)}\, dy = \frac{1}{M} \int_A f(y)\, dy$, where the integral runs over the points with $g > 0$, which carry all the mass of $f$ since $f \le M g$. Taking $A = \R^d$ gives clause 1, and dividing by $1/M$ gives clause 2. Clause 3 follows because the trials are independent and $X$ is the value of the first success. Example: to sample the density $f(x) = 2x$ on $[0, 1]$, take $g = 1$ on $[0, 1]$ and $M = 2$; a uniform $Y$ is accepted when $V \le Y$, which happens half the time. The bound $f \le M g$ is necessary: if $f > M g$ on a set of positive measure, the accepted values follow the density proportional to $\min(f, M g)$, not $f$. The method needs $f$ only up to a constant factor: if $f = c \tilde f$ with unknown $c$, one uses $\tilde f \le \tilde M g$ and the acceptance test $V \le \tilde f(Y)/(\tilde M g(Y))$.

Going deeper

For a student

Rejection sampling, due to von Neumann, is exact, needs no inverse distribution function, and works in any dimension. Its weakness is the acceptance rate $1/M$, which typically decays exponentially with the dimension, so in high dimension Markov chain Monte Carlo is used instead. Many fast samplers are refinements of it. The ziggurat algorithm uses a cheap envelope made of rectangles. Adaptive rejection sampling builds the envelope from tangent lines of $\log f$ when $f$ is log-concave. The number of trials before acceptance is geometric, so the cost per sample is random but with all moments finite.