# What is the requirement on the instrumental density in importance sampling?

1. From Rubinstein's Simulation Monte Carlo Method

I was wondering why $g$ is required to dominate $Hf$?

2. From Wikipedia

The basic idea of importance sampling is to change the probability $P$ so that the estimation of $E[X;P]$ is easier. Choose a random variable $L\geq 0$ such that $E[L;P]=1$ and that $P$-almost everywhere $L(\omega)\neq 0$. The variate $L$ defines another probability $P^{(L)}=L\, P$ that satisfies $$\mathbf{E}[X;P] = \mathbf{E}\left[\frac{X}{L};P^{(L)}\right].$$

The conditions on the instrumental density $L$ are $L\geq 0$ such that $E[L;P]=1$ and that $P$-almost everywhere $L(\omega)\neq 0$. I think I can understand them, because they are equivalent to say that $L$ is a density of $P^{(L)}$ wrt $P$, and the denominator in $\frac{X}{L}$ is zero only on a subset of probability measure zero so that it won't affect the expectation/integration.

Given that the two sources seem to give different answers, I wonder what conditions should be put on the instrumental density? Thanks and regards!

We need the condition $$g(x) = 0 \Rightarrow H(x)f(x)=0$$

else if $g(x)$ is 0, we would be dividing by 0, but if $f(x)$ is zero too, then we are safe. (handwavey arguments). It's also known as: $f$ is absolutely continuous w.r.t $g$.

To compare this to the wikipedia idea, $L := g(X) \ge 0$ where $X$ is sampled according to $g$. I'm not sure why $E[L;P] = 1$ though.

• It is not true that "if $g(x)$ is 0 we would be dividing by 0". The probability is 0 of obtaining a sample $x^l$ where $g(x^l)=0$, and thus the need to divide by 0 would not occur. Dec 6, 2012 at 20:54
• Of course that is true. The condition is more to guarantee integrability of the integral. Dec 6, 2012 at 22:42
• No, you only divide by $g(x^l)$ if you have a sample from there and you would not have obtained the sample $x^l$ in the first place if $g(x^l)$ were 0. Dec 6, 2012 at 23:03
• I see your point, but the issue is more about when the integral itself is defined. For a toy example, consider $\int_0^1 x dx$, and using some simple algebra rewrite this as $\int_0^1 \frac{x}{g(x)} g(x) dx$. This integral is only meaningful if it is integrable. In this case, it is integrable if either $g(x) \not = 0$ in [0,1], or $x$ is dominated by $g(x)$. In practice, you could choose any distribution $g$ for IS, so long as the resulting integral is still defined. Dec 6, 2012 at 23:44
• @Cam.Davidson.Pilon: I agree that the integral should be well defined. " it is integrable if either g(x)≠0 in [0,1], or x is dominated by g(x)." I wonder why x is dominated by g(x) will make the integral well defined? You can have $\frac{0}{0}$ in the integrand. See the comments after Jonathan's reply.
– Tim
Dec 10, 2012 at 17:46

The condition "$H f$ is dominated by $g$" in Rubenstein corresponds to the condition "$P$-almost everywhere $L(\omega) \neq 0$" (i.e., greater than zero) in the Wikipedia article. Rubenstein's condition is slightly weaker, because we actually don't need (in Wikipedia-notation) $L$ to have mass where $X$ has no mass. The condition that $\mathbf E[L;P]=1$ in Wikipedia is not actually necessary, it just simplifies the math a bit.

So, why do you need the dominating condition? Otherwise, the random variable $X$ (using Wikipedia's notation) will have positive mass in areas where $L$ will not. Since you can't ever sample those areas under $L$, that part of $X$ will be ignored by the importance sampling, which means that your results will be biased in unpredictable ways.

As jerad notes, although not theoretically required, in practice it is good for $L$ to have reasonably high mass everywhere $X$ does (it helps reduce the variance of the estimator). Heavy-tailed distributions are often used for $L$ because of this.

• +1.Thanks! I think, the condition that E[L;P]=1 and L being nonnegative in Wikipedia means that L is a density function.
– Tim
Dec 6, 2012 at 3:18
• (1) What is the relation between $g$ and $L$? (2) Does "Rubinstein's condition being weaker than Wikipedia's condition" mean that "P-almost everywhere $L(ω)≠0$" implies "$Hf$ is dominated by $g$"? Thanks!
– Tim
Dec 9, 2012 at 18:03
• (1) $g$ and $L$ are two different names for the same thing in the two different notations. (2) Yep. Dec 9, 2012 at 20:30
• Thanks! (1) Why? $g: \mathbb{R} \to \mathbb{R}$ while $L: \Omega \to \mathbb{R}$, where $(\Omega, \mathcal{F}, P)$ is the underlying probability space, with $\Omega$ not necessarily same as $\mathbb{R}$. (2) Why "P-almost everywhere $L(ω)≠0$" implies "$Hf$ is dominated by $g$"?
– Tim
Dec 9, 2012 at 20:33
• (1) Wikipedia's treatment is slightly more general in using $\Omega$ rather than $\mathbb{R}$ as the domain of $L$, but $L$ and $g$ play exactly the same role in the two presentations. Rubenstein's could easily be re-written with $g: \Omega \rightarrow \mathbb{R}$, but in practice the domain of a random variable doesn't matter anyway (because an equivalent random variable can be constructed on infinitely many arbitrary domains). Dec 9, 2012 at 20:41

The essential requirement is to chose a proposal distribution that is not 0 or too small in areas where the target distribution could have significant mass.

The idea is that you're approximating one distribution with a another, and to the extent that they're similar it will take fewer samples to obtain a good approximation. Let $p(z)$ be some intractable target distribution and $q(z)$ be some convenient distribution that your favorite language has a built in sampler for. You can visualize your goal as trying to use $N$ samples from $q(z)$ to make a histogram that looks like $p(z)$. So, obviously you would like your samples to concentrate in regions where $p(z)$ is large. But if $q(z)$ is very small in such regions, then you're unlikely to obtain very many samples there. And if $q(z)=0$ in such regions then you will never obtain samples there.

Here's the relevant excerpt from Bishop's Pattern Recognition and Machine Learning, page 534

"If, as is often the case, $p(z)f(z)$ is strongly varying and has a significant proportion of its mass concentrated over relatively small regions of z space, then the set of importance weights {rl} may be dominated by a few weights having large values, with the remaining weights being relatively insignificant. Thus the effective sample size can be much smaller than the apparent sample size L. The problem is even more severe if none of the samples falls in the regions where $p(z)f(z)$ is large. In that case, the apparent variances of $r_l$ and $rlf(z(l))$ may be small even though the estimate of the expectation may be severely wrong. Hence a major drawback of the importance sampling method is the potential to produce results that are arbitrarily in error and with no diagnostic indication. This also highlights a key requirement for the sampling distribution $q(z)$, namely that it should not be small or zero in regions where $p(z)$ may be significant."

• +1. Thanks! Can you explain why "chose a proposal distribution that is not 0 or too small in areas where the target distribution could have significant mass", and compare it and the two sources in my post?
– Tim
Dec 6, 2012 at 0:54
• @Tim updated my answer with more explanation and reference. Dec 6, 2012 at 20:35