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

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.