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

Write $w=p/q$ where $q>0$, assigning zero elsewhere. The envelope ensures $0\le w/M\le 1$, and $\pi$ is nonnegative. Integrating its joint probability density over the auxiliary coordinate givesConsequently ${\int }_{\Omega }{\int }_0^1\pi (x,u)dudx={\int }_{\Omega }p(x)dx=1$. This proves normalization of a probability distribution; the change of integration order is justified by Tonelli's theorem.

The coordinates are generally dependent. For $p(x)>0$, their conditional probability density isThus $U\mid X=x$ has a uniform distribution on an interval whose endpoint depends on $x$. They are independent exactly when $w(x)$ is constant for $p$-almost every $x$, since only then do these conditional laws agree. In particular, $p=q$ is an exception: $X\sim p$ and $U\sim \mathrm{Unif}(0,1/M)$ are independent. An unconditional answer that they can never be independent would therefore be too strong.

Integrating the joint probability density over the auxiliary coordinate, as in (i), gives the marginal distributionIn particular, augmenting with $U$ preserves the target probability distribution of $X$. The other marginal distribution, though not needed to identify $X$, is ${\pi }_U(u)=M{\int }_{\Omega }q(x)1_{\{w(x)\ge Mu\}}dx$ for $0<u<1$. It need not be a uniform distribution on $(0,1)$.

For the proposed joint probability density $\rho$, define the acceptance indicator functionOn the proposal's support the importance weight is $\pi (Y_i,V_i)/\rho (Y_i,V_i)=M{A}_i$. Therefore the requested augmented-space importance sampling estimator isIts expected value is $\theta$, provided ${\mathbb{E}}_p|\varphi (X)|<\infty$. This is not the ordinary estimator $n^{-1}{\sum }_{i}w(Y_i)\varphi (Y_i)$ from question 1. Taking the conditional expectation of this augmented estimator given all $Y_i$ produces that ordinary estimator, because $\mathbb{E}[A_i\mid Y_i]=w(Y_i)/M$. This is the Rao-Blackwell identity for a fixed-denominator rejection estimator.

Use the same acceptance indicator functions and set $K_n={\sum }_{i=1}^n{A}_i$, $S_n={\sum }_{i=1}^n{A}_i\varphi (Y_i)$. The rejection sampling estimator based on these $n$ proposals is the mean over the accepted observations:For $K_n=0$, any fixed convention, such as zero, is harmless asymptotically. The $A_i$ are independent and identically distributed random variables with Bernoulli distribution and success probability $1/M$, so the strong law of large numbers gives $K_n/n\to 1/M$ almost surely. In particular $K_n>0$ eventually almost surely. The exact identitythen holds whenever $K_n>0$. Wherever $S_n\ne 0$, it follows thatA qualification is missing from the printed claim: the quotient must be defined eventually. A convenient sufficient assumption is ${\mathbb{E}}_p|\varphi |<\infty$ and $\theta \ne 0$. Indeed, another application of the strong law of large numbers gives $S_n/n\to \theta /M$, ensuring that $S_n$ is eventually nonzero. This proves the stated quotient limit under that assumption.

As printed, the assertion is false as a universally defined quotient. For example, $\varphi \equiv 0$ makes both estimates zero for every $n$. Even excluding that example is insufficient: take $p=q$ to be the uniform distribution on $(0,1)$, $M=1$, and $\varphi (y)=1$ for $y<1/2$ and $-1$ otherwise. Then $S_n$ is a simple symmetric random walk, which returns to zero infinitely often almost surely, leaving the quotient undefined infinitely often.

With integrability but no assumption $\theta \ne 0$, the exact multiplicative identity remains valid, and both estimates converge to $\theta$ almost surely. In particular ${\hat{\theta }}_n^{\mathrm{IS}}-{\hat{\theta }}_n^{\mathrm{RS}}\to 0$ almost surely. One may alternatively define the quotient's removable $0/0$ cases as $M{K}_n/n$; that explicitly extended quantity always converges to one. These are valid repairs of the source's unrestricted statement.

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.