= Solution
{c}
\b[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, gives
$$
\mathbb E_q[(w(Z)e^{-Z_1})^2]
=A^d\exp\!\left(\frac{2s}{2s-1}\right),\qquad A=\frac{s}{\sqrt{2s-1}}.
$$
Both estimators are <unbiased estimators> of $\sqrt e$, and
$$
\boxed{\operatorname{Var}(\widehat\theta_n^{\mathrm{IS}})
=\frac{A^d e^{2s/(2s-1)}-e}{n},\qquad
\operatorname{Var}(\widehat\theta_n^{\mathrm{RS}})=\frac{e^2-e}{n}.}
$$
For 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 $ns^{d/2}$. The ratio of the resulting cost-normalized <variances> is
$$
\boxed{\frac{A^d e^{2s/(2s-1)}-e}{s^{d/2}(e^2-e)}\longrightarrow0\quad(d\to\infty),}
$$
because $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.
\Image[/past-exam-of-the-simulation-and-statistical-programming-course-of-the-university-of-oxford/2021-gaussian-sampling-cost.png]
{title=Sample-count and expected-proposal-cost comparisons for the one-coordinate integrand at sigma squared equal to two}
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.
Back to article page
