Past exam of the simulation and statistical programming course of the University of Oxford / 2023 / 2 / b

Fix a proposal $y$ with $\tilde{q}(y)>0$, and abbreviate $B=M\tilde{q}(y)$, $H=h(y)$ and $P=\tilde{p}(y)$. The envelope says $0\le H\le P\le B$. Assuming fresh independent uniform distribution draws at both stages, the law of total probability givesThe second term includes both reaching the residual test and passing it. If $H=B$, the envelope forces $P=B$ and the first test accepts with probability one; the second-stage $0/0$ ratio is never evaluated. This is squeeze rejection sampling.

Average the conditional probability in (i) over $Y\sim q=\tilde{q}/Z_q$:This is exactly the acceptance mass for an unnormalized rejection envelope. In normalized form the envelope is $p\le (M{Z}_q/Z_p)q$, giving the same acceptance probability. Here $M$ bounds the ratio of the unnormalized functions, so its value need not equal the envelope constant for the normalized probability density functions.

The squeeze changes the number of expensive target evaluations, while preserving the per-proposal acceptance probability. The expected number of proposals per accepted draw is $M{Z}_q/Z_p$.

For a measurable set $C$, (i) gives the joint acceptance probabilityDivide by $Z_p/(M{Z}_q)$ from (ii). The resulting conditional probability isThus every accepted value has target probability density function $p$. Repeating rejected trials with fresh independent random variables does not change this law: the contribution from acceptance on trial $j$ is multiplied by $(1-Z_p/(M{Z}_q){)}^{j-1}$, and summing that geometric series gives the same conditional law. Independent repetitions produce independent target draws.

The proposal's normalization of a probability distribution isThis is the Laplace distribution with location zero and scale one. For example, generate its magnitude from the exponential distribution with rate one and give it an independent fair sign. The target is the standard normal distribution, with $Z_p=\sqrt{2\pi }$.

To obtain the tight envelope, let $t=|x|$. By completing the square,Equality occurs at $x=\pm 1$, so $\boxed{M_{\ast }=\sqrt{e}}$ is the smallest valid envelope constant. It maximizes the acceptance probability for this fixed proposal. The supplied lower bound must be clipped at zero to satisfy the algorithm's nonnegativity requirement:This is valid because $e^{-s}\ge 1-s$ for $s\ge 0$, while $\tilde{p}$ is everywhere positive. Its support is $[-\sqrt{2},\sqrt{2}]$.

Here is the fully specified squeeze rejection sampling procedure. Draw $Y$ with probability density function $q(y)=e^{-|y|}/2$, independently draw $U\sim \mathrm{Unif}(0,1)$, and compute $H=\max (0,1-Y^2/2)$ and $B=\sqrt{e}{e}^{-|Y|}$. If $U\le H/B$, return $Y$ immediately. Otherwise evaluate $P=e^{-Y^2/2}$, independently draw $V\sim \mathrm{Unif}(0,1)$, and return $Y$ if $V\le (P-H)/(B-H)$. On rejection restart with fresh draws. In this example $B>H$ everywhere, so the residual denominator is positive.

Avoiding a target evaluation means accepting at the first test. Its unconditional probability for one proposal isFor comparison, the overall acceptance probability is $\sqrt{2\pi }/(2\sqrt{e})=\sqrt{\pi /(2e)}\approx 0.760173$. The first-stage saving $0.571843$ is the fraction of proposals requiring no target evaluation, including both eventual accepted and rejected proposals in the denominator; it is not conditional on acceptance.