Results on Monte Carlo estimates produced by importance sampling

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.

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

• I suspect, given that the OP is reporting small variance estimators that are biased, but seem to have small variance, that he may be asking about self normalized importance sampling. See Radford Neal's rant on the Harmonic mean estimator for a good example, that takes what would be an importance sampling estimate with 0 variance, and returns nonsense. I am not certain that this does not ever occur in regular importance sampling, but it is certainly rare. Mar 21 '12 at 15:29
• Even if this was not the OP's intention, I would be interested in some pointers on how to figure out when self-normalization will go horribly wrong. Mar 21 '12 at 15:29
• @deinst I was not aware of the self-normalization procedure and its pitfalls so thank you for this! In any case, I think the issues may be relevant to the properties of my IS scheme so I would like to explore this idea some more if any of you have ideas. Mar 22 '12 at 3:29
• @deinst The IS scheme that I am using is designed to work without a sampling distribution $g(x)$ at hand. The scheme first uses an MCMC procedure to simulate $M$ points $x_1..x_M$ from the zero variance distribution $g^*(x) = h(x)f(x)/\int{h(x)f(x)dx}$. Next it uses Kernel Density Estimation on $x_1..x_M$ to produce $\hat{g(x)}$. With $\hat{g(x)}$ in hand, I can then sample $N$ new points $y_1...y_N$ form my IS estimate as $\sum{ h(y_i)f(y_i)/hat{g(y_i)}$ Mar 22 '12 at 3:38
• Using a non-parametric estimate introduces variability of an higher order than the Monte Carlo variability, so I would not advise it. Mar 22 '12 at 11:02

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).

• Thank you for this. I'm just a little unsure about the notation / not sure if there is a typo. To clarify, what exactly are $X/Y$ and $G$ in your explanation? Mar 22 '12 at 2:57
• @BerkUstun The capital G is a typo for a small that I will fix promptly. X/Y is just a generic ratio of random variables. IIRC all this is explained in Liu's Monte Carlo book (something with scientific in the title.) Mar 22 '12 at 3:52
• @deinst: Great point! Indeed, the properties of the self-normalised versions are quite different from those of the unbiased importance sampling estimator. In theory, one would need a separate importance sampler to estimate the denominator. Mar 22 '12 at 11:00