# Efficiency of importance sampling in terms of the size of the the support of sampling distribution

In importance sampling, one proposes to compute an integral $$I:=\mathbb E_{x \sim P}[h(x)]$$ by rewritting it as $$I=\mathbb E_{x \sim Q}\left[w(x)h(x)\right],\text{ with }w(x):=\frac{p(x)}{q(x)},$$ for some appropriately chosen sampling distribution $$Q$$ with density $$q$$. Note that $$w(x)$$ is itself a random variable.

The general procedure is as follows:

• Sample $$x_1,\ldots,x_N$$ iid from $$Q$$.
• Compute $$\hat{I}^{(N)}_q := \dfrac{\sum_{i=1}^nw_ih(x_i)}{\sum_{i=1}^N w_i}$$, where $$w_i = w(x_i) := p(x_i)/q(x_i)$$.

It's known that the key condition (in addition to some finite-moment conditions) for the $$\hat{I}^{(N)}_q$$'s converge $$Q$$-a.s. to $$I$$ is that $$\operatorname{supp}(p) \cap \operatorname{supp}(h) \subseteq \operatorname{supp}(q),$$ where $$\operatorname{supp}(q)$$ is the support of $$q$$. In fact, under the above condition one has (see Theorem 2.2 of this material)

$$\begin{split} \mathbb E_{x \sim q}[\hat{I}^{(N)}_q] &= I + \frac{\mu \operatorname{Var}_{x \sim q}[w_q(x)] - \operatorname{Cov}_{x \sim q}[w_q(x), w_{q}(x)h(x)]}{N} + \mathcal O\left(\frac{1}{N^2}\right),\text{ and }\\ \operatorname{Var}_{x \sim q}[\hat{I}^{(N)}_q] &= \frac{\operatorname{Var}_{x \sim q}[w_{q}(x)h(x)] - 2\mu\operatorname{Cov}_{x \sim q}[w_q(x), w_{q}(x)h(x)] + \mu^2 \operatorname{Var}_{x \sim q}[w_q(x)]}{N}\\ &\quad\quad\quad + \mathcal O\left(\frac{1}{N^2}\right) \end{split}$$

Thus asymptotically, the estimates $$\hat{I}^{(N)}_q$$ are unbiased and have no variance.

On notes that, if (other things being equal) $$\operatorname{supp}(q)$$ is very large compared to the support of the integral $$I$$, namely $$\operatorname{supp}(p) \cap \operatorname{supp}(h)$$, then the estimates $$\hat{I}^{(N)}_q$$ will not be very "efficient" as most points sampled for the computation, will not yield any information, and $$w_i$$'s will have high variance, etc. In an attempt to understand more formally how $$\operatorname{supp}(q)$$ affects the performance of the estimates $$\hat{I}_n$$, for $$0 \le \epsilon < 1$$ and $$C \supseteq \operatorname{supp}(q)$$, define the contaminated density $$q_\epsilon = (1-\epsilon) q + \epsilon u_C$$ where $$u_C$$ is the uniform distribution on $$C$$.

# Question

• How does $$\operatorname{Var}_{x \sim q}(w_{q}(x)$$ compare to $$\operatorname{Var}_{x \sim q_\epsilon}(w_{q_\epsilon}(x))$$ ? I suspect the former is larger than the latter, but don't have rough guess of the orders of magnitude.
• How does $$\operatorname{Var}_{x \sim q_\epsilon}(w_{q_\epsilon}(x)h(x))$$ compare to $$\operatorname{Var}_{x \sim q}(w_{q}(x)h(x))$$ ? (same remarks as above).
• How does $$\operatorname{Cov}_{x \sim q_\epsilon}(w_{q_\epsilon}, w_{q_\epsilon}(x)h(x))$$ compare to $$\operatorname{Cov}_{x \sim q}(w_q(x), w_{q}(x)h(x))$$ ? (same remarks as above).