= Solution
Draw <independent and identically distributed random variables> $Y_1,\ldots,Y_n\sim q$ and use the <importance weight> $w=p/q$. The <importance sampling> estimator is
$$
\boxed{\widehat\theta_n^{\mathrm{IS}}=\frac1n\sum_{i=1}^nw(Y_i)\phi(Y_i).}
$$
The envelope supplies the <support condition for importance sampling>. Since $\mathbb E_q[w(Y)\phi(Y)]=\mathbb E_p\phi(X)=\theta$, this is an <unbiased estimator>. Moreover, $0\leq w\leq M$, so
$$
\begin{aligned}
\mathbb E_q[w(Y)^2\phi(Y)^2]
&=\int w(x)\phi(x)^2p(x)\,dx\\
&=\mathbb E_p[w(X)\phi(X)^2]\\
&\leq M\mathbb E_p[\phi(X)^2]
=M(1+\theta^2).
\end{aligned}
$$
Here $\mathbb E_p\phi^2=\operatorname{Var}_p(\phi)+\theta^2=1+\theta^2$. Subtracting the squared <expected value> and dividing by $n$ proves the <bounded-weight importance-sampling moment bound> in the requested form:
$$
\boxed{\operatorname{Var}(\widehat\theta_n^{\mathrm{IS}})
=\frac{\mathbb E_p[w\phi^2]-\theta^2}{n}
\leq\frac{M+(M-1)\theta^2}{n}.}
$$
Back to article page
