Past exam of the simulation and statistical programming course of the University of Oxford / 2023 / 1 / c / ii / Solution

The definition of $a$ and (c)(i) give $a\le M$. Nonnegativity of the variance strengthens the lower bound toIn fact the variance of one weighted observation is exactlyIt is finite by the envelope. For $v_{\mathrm{IS}}>0$, the central limit theorem gives approximate two-sided coverage $2\Phi (0.01\sqrt{n/v_{\mathrm{IS}}})-1$, so the paper's rounded quantile yieldsIf $v_{\mathrm{IS}}=0$, the weighted observation equals $\theta$ almost surely, and one draw is sufficient. These are theoretical budgets: $a$ and $\theta$ may themselves be unknown and need preliminary estimation in an implementation.

Compare with the average rejection sampling cost $66,564M$. Ignoring integer rounding, importance sampling uses fewer proposal draws at the same approximate precision precisely whenFor literal integer budgets, the comparison is $\lceil 66,564v_{\mathrm{IS}}\rceil <66,564M$. The simpler strict inequality is the intended leading-order condition. The bound $a\le M$ alone does not ensure an improvement when $\theta \ne 0$; this is a proposal-budget variance comparison of importance and rejection sampling.