Past exam of the simulation and statistical programming course of the University of Oxford / 2021 / 1

Write $s={\sigma }^2\ge 1$. The two multivariate normal distribution probability density functions have ratioHere $\Vert x\Vert$ is the Euclidean norm. Consequently the smallest rejection sampling envelope constant, and its acceptance probability, areThe supremum is attained at $x=0$; hence no smaller constant can dominate the ratio. Draw $Y\sim N(0,s{I}_d)$ and an independent $U$ from the uniform distribution on $(0,1)$. Accept $Y$ whenotherwise repeat with fresh independent random variables. One can generate $Y=\sqrt{s}G$ using a random vector $G$ with independent standard normal distribution coordinates.

For any measurable set $B$, the joint acceptance probability is ${\int }_{B}q(y)p(y)/(M_{\ast }q(y))dy=M_{\ast }^{-1}{\int }_{B}p(y)dy$. Dividing by $1/M_{\ast }$ proves that the returned random vector has probability density function $p$. The number of proposals has a geometric distribution on the positive integers, with expected value $M_{\ast }$. When $s=1$, every proposal is accepted.

The moment-generating function of a standard normal distribution gives $\mathbb{E}[e^{t{X}_j}]=e^{t^2/2}$. Using independence of the coordinates,The accepted draws are independent and identically distributed random variables, so their sample mean is an unbiased estimator and has varianceThis counts $n$ accepted draws, requiring $n{\sigma }^d$ proposals in expectation.

An importance weight has expected value ${\mathbb{E}}_q[w(Z)]=\int p(z)dz=1$. From the ratio in (a),The supplied normal distribution transform applies with quadratic coefficient $-(1-s^{-1})$, giving each factor $(2s-1{)}^{-1/2}$. ThusFor $s>1$, the base $A:=s/\sqrt{2s-1}$ exceeds one because $s^2-(2s-1)=(s-1{)}^2>0$: importance weight variance increases exponentially with dimension. For $s=1$, the importance weight is identically one and its variance is zero. This calculation concerns the importance weight, rather than the weighted integrand.

For the new integrand, $\theta ={\mathbb{E}}_p[e^{-X_1}]=e^{1/2}$ and ${\mathrm{Var}}_p(e^{-X_1})=e^2-e$, independently of dimension. Chebyshev's inequality therefore yieldsA sufficient positive integer sample count isThe ceiling function ensures that the bound is at most $\delta$, so the strict-error event in the question has probability at least $1-\delta$. The required number of accepted draws is independent of $d$; their expected proposal count is $n{\sigma }^d$.

At equal sample count, rejection sampling eventually has smaller variance for fixed ${\sigma }^2>1$; at equal expected proposal cost, importance sampling eventually wins. The distinction matters because a sample of the rejection sampling estimator means an accepted draw.

For the importance sampling estimator, all coordinates contribute to the importance weight although only one enters the integrand. The same normal distribution transform as in (c), now with linear coefficient $-2$ for coordinate one, givesBoth estimators are unbiased estimators of $\sqrt{e}$, andFor fixed $s>1$, the first variance grows exponentially while the second stays constant. This is the benefit of returning exact target draws in rejection sampling. However, obtaining those draws costs $s^{d/2}$ proposals each on average.

To compare computational work, multiply each variance by its expected proposal count. For importance sampling that count is $n$; for rejection sampling it is $n{s}^{d/2}$. The ratio of the resulting cost-normalized variances isbecause $A/\sqrt{s}=\sqrt{s/(2s-1)}<1$. Thus importance sampling eventually gives better precision for the same expected number of proposals, assuming comparable work per proposal. This is an asymptotic cost comparison, not a guarantee that a fixed small computing budget produces any accepted draws. Both methods still deteriorate exponentially in this comparison. For $s=1$ they coincide and every proposal is accepted.

A practical improvement is to exploit the integrand's one-coordinate structure directly: average $e^{-G_1}$ for standard normal distribution draws $G_1$, without generating unused coordinates. The optimal change of proposal distribution in (iii) improves further.

The integrand is positive, so the minimum-variance importance distribution is its target-weighted probability density function, normalized by $\theta =\sqrt{e}$:By completing the square,Thus $q^{\star }$ is the multivariate normal distribution $N(-e_1,I_d)$, where $e_1=(1,0,\dots ,0)$ is the first standard basis vector. Its importance weight and weighted integrand areA variance cannot be negative, and this proposal makes every summand constant, proving optimality directly. It is admissible under the arbitrary-proposal condition even though its mean vector is not zero. Although optimal proposals usually involve an unknown normalizing integral, here both that integral and the resulting normal distribution are explicit.