Past exam of the mathematics course of the University of Cambridge / 2001 / iii / Paper 33 / 1 / a / i

Write $C={\int }_{\mathbb{R}}f(x)dx$, so $0<C<\infty$. The finite envelope condition means that $f\le Mg$ almost everywhere; in particular, the proposal must cover the support of the target.

For each independent proposal $Y\sim g$, generate an independent $U\sim \mathrm{Unif}(0,1)$ and accept $Y$ precisely whenDiscard a rejected proposal and continue. The ratio is in $[0,1]$ and is needed only where $g(Y)>0$. Neither evaluation of $C$ nor prior knowledge of the normalized target is required.

To prove the output law, for any measurable set $D$ the joint probability of acceptance and a proposal in $D$ isDividing by the total acceptance probability $C/M$ gives ${\int }_{D}f(y)/Cdy$, the target probability. Independent proposal-uniform pairs give independent accepted observations. With a finite proposal list there can be no accepted value; with continued independent trials, acceptance eventually occurs almost surely because $C/M>0$.