Past exam of the mathematics course of the University of Cambridge / 2022 / ii / Paper 4 / 28K (Principles of Statistics)

Generate $U\sim \mathrm{Uniform}[0,1]$ and setFor $x\ge 0$,which is the distribution function of an exponential distribution with rate one. This is inverse transform sampling.

In one proposal of rejection sampling, the probability of both proposing a value in $dx$ and accepting it isIntegrating shows that the acceptance probability is $1/M$. Conditional on acceptance, the density of the proposed value is thereforeEach unsuccessful proposal restarts independently, so the eventual output $Y$ has the same conditional density:

Take the proposal density $h(x)=e^{-x}{1}_{x\ge 0}$. For the target half-normal distribution,The ratio is maximized at $x=1$, so the sharp envelope constant isGenerate $X=-\log U_1$ and an independent uniform $U_2$, and accept $X$ when

Each independent proposal is accepted with probability $1/M$. The number of proposals is therefore a geometric distribution with mean

The accepted $Y$ has the half-normal distribution, so $Y=|G|$ in distribution for $G\sim N(0,1)$. Multiplying it by an independent random sign that is positive and negative with equal probabilities restores the two symmetric halves of the Gaussian density. Thus

For an exponential proposal of rate $\lambda >0$,and the smallest valid rejection constant isbecause the exponent is maximized at $x=\lambda$. Differentiating its logarithm givesThe unique minimum occurs at $\lambda =1$. Since rejection efficiency is $1/M(\lambda )$, choosing any $\lambda \ne 1$ makes the algorithm less efficient: