Past exam of the mathematics course of the University of Cambridge / 2006 / iii / Paper 47 / 3

For rejection sampling, independently generate a proposal $Y$ with density $g$ and a uniform $U$ on $(0,1)$. Accept $Y$ if $U\le f(Y)/(Mg(Y))$; otherwise generate a fresh independent pair and repeat. Set the ratio to zero on $g=0$ where necessarily $f=0$. The envelope condition makes the acceptance threshold at most one.

For any measurable set $A$, a single attempt satisfiesTaking the whole space shows that acceptance has probability $1/M$. Conditioning on acceptance therefore gives density $f$. Repeating rejected independent attempts preserves that conditional law and terminates almost surely; the number of attempts is geometric with mean $M$.

For fixed proposal density, admissibility requires $M\ge {\sup }_{g(x)>0}f(x)/g(x)$ under the pointwise convention in the question. Since $1/M$ decreases with $M$, the smallest valid envelope gives the greatest acceptance probability:For densities specified only almost everywhere, replace the supremum by the essential supremum. Integration of the envelope also gives $M\ge 1$.

Use the uniform proposal on $[1,7]$, with density $g=1/6$. The triangular distribution peaks at $x=3$ with height $1/3$, so the optimal constant for this proposal is $M=2$. At each attempt take two fresh pseudo-random uniforms $U,V$, and propose $Y=1+6U$. The rejection method accepts according toIndeed these bounds are $f(Y)/(2g(Y))=3f(Y)$. Part (a) proves that the accepted value has the required density. Acceptance probability is $1/2$, so the method needs two proposal attempts on average, and hence four uniforms on average if each attempt uses two. The validity of the ideal algorithm presumes independent uniform draws; merely belonging to $[0,1]$ does not by itself make a pseudo-random sequence uniform or independent.

Integrating the two linear pieces gives the cumulative distribution functionThe split probability is $F(3)=1/3$. Invert each branch to obtain the method of inversion:Both expressions equal three at the split. For an ideal uniform draw, monotonicity gives $\mathbb{P}(F^{-1}(U)\le x)=\mathbb{P}(U\le F(x))=F(x)$, proving the target law. Inversion is preferable here: its quantile is explicit, it uses one uniform and one square root per output, and has no rejected draws. Rejection remains useful for densities with no convenient inverse CDF.