Past exam of the mathematics course of the University of Cambridge / 2003 / iii / Paper 43 / 1 / a

Assume the target probability density function is supported where the proposal probability density function is positive and that the envelope constant is finite. Any $C\ge M$ satisfies $f(x)\le Cg(x)$, and integration gives $C\ge 1$. For each attempt draw independently $Y\sim g$ and $U\sim U(0,1)$. Accept $Y$ if $U\le f(Y)/(Cg(Y))$; otherwise discard it and repeat. Independent attempts give independent accepted values. A finite pre-generated list of independent proposal draws can be screened with independent uniforms in the same way, though the number retained is random. If $M=\infty$, this fixed-envelope rejection sampling method cannot be used with that proposal.

For any measurable set $A$, integrating the joint acceptance event in rejection sampling givesSetting $A$ equal to the whole support yields $P(\text{accept})=1/C$. ThusTo verify repeated attempts directly, the probability that the first accepted observation falls in $A$ isWith finite $C$, eventual acceptance has probability one. Applying the same argument after each success proves that the retained sequence consists of independent draws from the target.

The acceptance probability is $1/C$, soFor the given proposal probability density function $g$, every valid envelope must have $C\ge \sup f/g=M$. Rejection increases with $C$, so the optimal envelope is $C=M$, giving rejection probability $1-1/M$. This optimizes the constant for the fixed proposal; it does not assert that $g$ is the best possible proposal. For densities specified only almost everywhere, an essential supremum is sufficient.