Results on Monte Carlo estimates produced by importance sampling

Question

I have been working on importance sampling fairly closely for the past year and have a few open-ended questions that I was hoping to get some help with.

My practical experience with importance sampling schemes has been that they can occasionally produce fantastic low-variance and low-bias estimates. More frequently, however, they tend to produce high-error estimates that have low sample variance but very high bias.

I am wondering whether anyone can explain exactly what kinds of factors affect the validity of importance sampling estimates? In particular, I am wondering:

1) Are importance sampling estimates guaranteed to converge to the correct result when the biasing distribution has the same support as the original distribution? If so, why does this appear to take so long in practice?

2) Is there a quantifiable relationship between the the error in an estimate produced through importance sampling and the "quality" of biasing distribution (i.e. how much it matches the zero-variance distribution)

3) Partially based on 1) and 2) - is there a way to quantify 'how much' you have to know about a distribution before you were better off using an importance sampling design than a simple Monte Carlo method.

Answer 1

Importance sampling has exactly the same validation as the basic Monte Carlo approach. At its core, it is basic Monte Carlo. Indeed, it is simply a change of reference measure, going from $$ \int h(x) f(x) \text{d}x $$ to $$ \int h(x) \dfrac{f(x)}{g(x)} g(x) \text{d}x $$ Thus the convergence is garanteed by the law of large numbers in both cases, i.e whether you simulate from $f$ or from $g$. In addition, if the term $$ \int h^2(x) \dfrac{f^2(x)}{g(x)} \text{d}x $$ is finite, the central limit theorem also applies and the speed of convergence is $\text{O}(1/\sqrt{n})$. If it "takes so long in practice", it is because the above variance factor in the CLT can be quite large. But, and I insist, the speed is the same as with regular Monte Carlo, $\text{O}(1/\sqrt{n})$.

The quality of an importance sampling distribution is thus directly related with the above variance factor, which goes to zero for the "zero-variance distribution" proportional to $|h(x)|f(x)$.

Answer 2

Xi'an has covered the standard importance sampling results. If you are asking about self-normalized importance sampling, where you only know $f$ and $g$ up to some unknown normalizing constant, some techiques are discussed in chapter 4 of both of the Xi'an and Casella books Monte Carlo Statistical Methods, and Introducing Monte Carlo Methods with R. I am sure that Xi'an can elaborate in much more detail on this than I can, so in a sense this answer is bear baiting.

With self normalized importance sampling you are attempting to approximate $$\delta=\int h(x)f(x)\text{d}x$$ by choosing $x_1,\ldots,x_n$ from a distribution whose density function is proportional to $g(x)$ and computing $$\hat{\delta}=\frac{\sum_{i=1}^n h(x)f(x)/g(x)}{\sum_{i=1}^n f(x)/g(x)}.$$ Using the delta method (basically taking up to the linear terms of the taylor series of $X/Y$) and letting $\omega(X)=f(x)/g(X)$ we get $$E_g(\hat{\delta})\approx \delta + \frac{\delta \text{Var}_g(\omega(X))-\text{Cov}_g(\omega(X),h(X)\omega(X))}{n}$$ and $$\text{Var}_g(\hat{\delta})\approx\frac{\text{Var}_g(h(X)\omega(X))-2\delta\text{Cov}_g(\omega(X),h(X)\omega(X))+\delta^2\text{Var}_g(\omega(X))}{n}.$$

So, intuitvely, to get small bias and small variance, you want $\text{Var}_g(\omega(X))$ to be small and $\text{Cov}_g(\omega(X),h(X)\omega(X))$ to be positive. Unfortunately these approximations are not perfect (and accurately determining the variances and covariances is likely to be as difficult as solving the initial problem).