In importance sampling, why should the importance density have heavier tails?

Question

Why should the importance density (or biasing density) $g$ have heavier tails than the original distribution $f$?

Equivalently, why should

$$\frac{f(x)}{g(x)}<M , \forall x$$ for some $M>0$?

Answer 1

Heuristically, it's because, for many situations of interest, what happens in the tails of the distribution is important, maybe more important than what happens in the middle, so undersampling the tails results in relatively inaccurate estimates of the target quantity.

More formally, consider a known function $h(x)$, along with original distribution $f$ and importance sampling distribution $g$. Assume we are attempting to estimate:

$$\mu = \mathbb{E}h = \int h(x)f(x)\text{d}x$$

but we are forced by circumstance to resort to importance sampling. Our importance sampling estimate $\hat{\mu}_h$ is:

$$\hat{\mu}_h = \frac{1}{n}\sum_{i=1}^nh(x_i)f(x_i)/g(x_i)$$

where the $x_i \sim g$. The variance of our estimate is:

$$\sigma^2(\hat{\mu}) = {1 \over n}\left[\int {[h(x)f(x)]^2 \over g(x)} \text{d}x - \mu^2\right] = {1 \over n}\left[\int \left({f(x) \over g(x)}\right) h^2(x)f(x)\text{d}x - \mu^2 \right]$$

For comparison, if we had a sample of $h(x)$ with $x$ drawn from $f$, the variance of the sample mean of the $h$ is $\sigma^2(\bar{h}) = {1 \over n}\left[\int h^2(x)f(x)\text{d}x - \mu^2 \right]$.

Now, consider $f,g$ such that $f/g$ is unbounded. Typically this would happen in the tails of the two distributions and would come about because your sampling density $g$ has thinner tails than $f$, although you could easily construct examples where it happened in the center. Depending upon $h^2f$, this could result in a very large or even infinite $\sigma^2(\hat{\mu})$. (If $h = 0$ over the regions where $f/g$ is large, of course, you won't have an issue - but that is a very problem-specific, and I expect rare, situation.) On the other hand, if $f/g < M$ for some $M > 1$, it is clear that $\sigma^2(\hat{\mu}) \leq M \sigma^2(\bar{h})$. We'll have not only prevented a possible catastrophe in estimation, we'll have bounded how poorly we do relative to using the sample mean of the $h$ as an estimate.

In fact, importance sampling can be a variance-reduction technique, even relative to the sample mean. By "over-sampling" those regions which contribute disproportionately heavily to $h^2f$, we can increase the accuracy of our final estimate. A trivial example of this is when $h = 0$ outside some region; an importance sampling distribution that also equals zero outside that region will prevent us from wasting samples on $x_i$ from a region that contributes $0$ to $\mathbb{E}h$. A more realistic example is estimating $h = $ the mean absolute deviation of a $t(3)$ variate which we know is centered at $0$; we'll compare the sample mean, an importance sampling estimate based upon the Normal distribution, and an importance sampling estimate based upon the Cauchy distribution. Our sample size is 100, and we repeat the experiment $N = 10,000$ times to evaluate the performance of the three estimators.

N <- 10000
results <- data.frame(list(Normal=rep(0,N), Cauchy=rep(0,N), t3=rep(0,N)))
for (i in 1:N) {
   x_norm <- rnorm(100)
   x_cauchy <- rt(100, df=1)
   results[i,1] <- mean(abs(x_norm)*dt(x_norm, df=3)/dnorm(x_norm))
   results[i,2] <- mean(abs(x_cauchy)*dt(x_cauchy, df=3)/dt(x_cauchy, df=1))
   results[i,3] <- mean(abs(rt(100, df=3)))
}
apply(results,2,var)

Repeating this five times results in the following estimated variances of the three estimates of MAD:

      Normal      Cauchy          t3 
 3.392863921 0.005228449 0.016933091 
 4.987301438 0.005108166 0.018078036 
21.527506149 0.005078266 0.018151188 
 1.314209463 0.005108059 0.017396005 
 2.829562814 0.005163212 0.017341226 

Clearly the Cauchy-based estimator is the winner, and that "21.52..." result for the Normal-based estimator should make us suspect that the true variance might not be finite.

The moral of the story is: use proposal distributions with heavier tails than the original, unless you have a good reason not to.