0
$\begingroup$

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).
$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.