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

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.

Write $Z={\int }_a^{\infty }{x}^{\alpha -1}{e}^{-\beta x}dx$. A proper target requires $\beta >0$, and a proper proposal requires $b>0$. Normalization gives $f(x)=x^{\alpha -1}{e}^{-\beta x}/Z$ and the Pareto distribution proposal $g(x)=b{a}^b{x}^{-b-1}$ on $x>a$. Their ratio isThe derivative of its logarithm is $(\alpha +b)/x-\beta$. It is positive before $x_{\ast }=(\alpha +b)/\beta$ and negative after it. Since $a<\alpha /\beta <x_{\ast }$, the maximum occurs within the proposal support. Consequently the tight envelope for truncated gamma rejection sampling with a Pareto envelope isThe accompanying acceptance rule can be evaluated without $Z$:

Integrating the Pareto distribution proposal yields $G(x)=1-(a/x{)}^b$ for $x\ge a$. For an independent uniform random variable $U$, solve $G(Y)=U$ to obtain the inverse transform sampling ruleEquivalently $Y=a{U}^{-1/b}$ because $1-U$ is also uniformly distributed. In implementation choose $U$ strictly between zero and one so that the inverse is finite.

Every independent proposal/uniform pair succeeds with probability $p=1/M$. The number $K$ retained from a fixed budget of 100 attempts therefore has a binomial distribution, rather than a fixed value:Conditioned on the accept/reject indicators, each retained value still has the target probability density function; the random output count is a separate issue from the correctness of those retained draws.