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

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$.

The acceptance mass for an unnormalized rejection envelope follows by integrating the proposal-specific acceptance probability:The inequality $f\le Mg$ also gives $C\le M$, so this is a valid probability. It is the same at every independent trial.

If $J_i$ indicates acceptance of the $i$th proposal, then $J_1,\dots ,J_n$ are independent Bernoulli distribution variables with parameter $C/M$. Hence the accepted count $K={\sum }_i{J}_i$ satisfiesIts variance is $n{p}_{\mathrm{acc}}(1-p_{\mathrm{acc}})$. Conditional on any acceptance pattern, the accepted values have independent target probability density function $h$; mixing over patterns retains this product law conditional on their count.