= Solution
The definition of $a$ and (c)(i) give $a\leq M$. Nonnegativity of the <variance> strengthens the lower bound to
$$
\boxed{\frac{\theta^2}{1+\theta^2}\leq a\leq M.}
$$
In fact the <variance> of one weighted observation is exactly
$$
v_{\mathrm{IS}}:=\operatorname{Var}_q(w(Y)\phi(Y))
=a(1+\theta^2)-\theta^2.
$$
It 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> yields
$$
\boxed{n_{\mathrm{IS}}=\left\lceil66{,}564\,[a(1+\theta^2)-\theta^2]\right\rceil.}
$$
If $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 when
$$
a(1+\theta^2)-\theta^2<M,
\qquad
\boxed{a<\frac{M+\theta^2}{1+\theta^2}.}
$$
For literal integer budgets, the comparison is $\lceil66{,}564v_{\mathrm{IS}}\rceil<66{,}564M$. The simpler strict inequality is the intended leading-order condition. The bound $a\leq M$ alone does not ensure an improvement when $\theta\ne0$; this is a <proposal-budget variance comparison of importance and rejection sampling>.
Back to article page
