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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.