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

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.