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

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.

For normal rejection sampling with an exponential envelope, complete the square in the probability density function ratio:The maximum occurs at $x=\lambda$, which lies in the support because $\lambda >0$. ThusThe PDF exponent is $e^{{\lambda }^2}$ inside the square root; this distinction is lost in the converted TeX.

The acceptance rule simplifies toAn exponential proposal can be generated as $Y=-{\lambda }^{-1}\log V$ from an independent uniform distribution value $V$. Since the target is normalized, the overall acceptance probability is $1/M(\lambda )$. To maximize it,Therefore the optimal rate is $\lambda =1$, with acceptance probability $\sqrt{\pi /(2e)}$.

Finally, give each accepted half-normal distribution value $Y$ an independent fair sign $R\in \{-1,1\}$ and output $Z=RY$. On each half-line its probability density function is half the reflected half-normal distribution probability density function:Consequently $Z\sim N(0,1)$. The sign must be drawn independently; rejection itself does not supply it.