Monte Carlo Importance Sampling

Question

I am reading the book on Monte Carlo by Sobol (A Primer for the Monte Carlo Method). In the section on Importance Sampling, he writes:

$I = \int_a^b g(x) \: dx$

"to compute this integral, we could use a random variable $\xi$, defined over the interval (a,b) with density $p(x) > 0$. In any case":

$M\begin{equation} \tag{equation 1} \eta = M(g(\xi)/p(\xi)) = I \end{equation}$

where $\eta = g(\xi)/p(\xi)$

and:

$\begin{equation} \tag{equation 2} M\eta = \int_a^b { g(x) \over p(x) } p(x) \: dx = I\end{equation}$

In Sobol's book, M stands for the expected value and D stands for variance. He then writes: "the variance $D\eta$, and hence, the estimate of this error of approximation depend on what variable $\xi$ we use, since:

$\begin{equation} \tag{equation 3} D\eta = M(\eta^2) - I^2 = \int_a^b { g^2(x) \over p(x) }\:dx - I^2 \end{equation}$

Let us prove that $D\eta$ is minised when the density $p(x)$ is proportional to $|g(x)|$. We will use an inequality well known in analysis:

$\begin{equation} \tag{equation 4} \left( \int_a^b |u(x)v(x)|\:dx\right)^2 \leq \int_a^b u^2(x) \: dx \int_a^b v^2 (x) dx \end{equation}$

If we set $u = g(x)/\sqrt{p(x)}$ and $v = \sqrt{p(x)}$, then we obtain:

\begin{equation} \tag{equation 5} \left( \int_a^b |g(x)|\:dx\right)^2 \leq \int_a^b { g^2(x) \over p(x) } \: dx \int_a^b p (x) dx \\ = \int_a^b {g^2(x)\over p(x)\:dx} \end{equation}

It follows from eq. 3 and eq. 5 that:

$D\begin{equation} \tag {equation 5} \eta \geq \left( \int_a^b |g(x)dx\right)^2 - I^2\end{equation}$

My questions:

• what would be the proof of equation 1? Why taking the expected value of g(x)/p(x) is equal to I? I don't understand that statement. I understand equation 2 because in the integral we divided g(x) by p(x) but also multiply by p(x). So the two terms cancel out. But I don't understand eq. 1.

• I know the formula for computing variance:

$Var(X) = E[X^2] - E[X]^2.$

which is where eq. 3 comes from. However I don't understand the first term on the right inside. Why would $E[X^2] = g^2(x)/p(x)$ and not $E[X^2] = g^2(x) / p^2(x)$?

• Where is equation 4 coming from. Sobol says it's a well known inequality but I would like to know where it comes from.

• Finally, I really don't understand the last part of the demonstration. What's the meaning of $\left(\int_a^b g(x) \:dx \right)^2 - I^2$ and why is the variance $D\eta$ greater than this equation since I thought we were trying to show that the variance of the general MC estimator was less than the basic MC estimator. Furthermore, as pointed by Sobol, isn't importance sampling only working if p(x) is more or less a function proportional to the integrand g(x). In other words, is it possible to come with a general proof that importance sampling works since it depends highly on the choice of the pdf.

Sorry lots of questions, but this seems critical for the understanding of the method, and hope this post will help other people after me.

Thanks for your help, spending time reading/answering the post and sharing your knowledge.

Answer 1

Equation 1 follows directly from the definition of expected value. If your random variable $\xi$ has density $p$, the expected value of a function $f(\xi)$ is defined to be $$ \int f(x)p(x)\,dx. $$ Thus $$ M(g(\xi)/p(\xi)) = \int \frac{g(x)}{p(x)}\,p(x)\,dx = \int p(x)\,dx. $$

The expected value of $g(\xi)^2/p(\xi)^2$ is $$ \int \frac{g(x)^2}{p(x)^2}\,p(x)\,dx = \int \frac{g(x)^2}{p(x)}\,dx. $$ Therefore, computing $D\eta$ gives $$ D(g(\xi)/p(\xi)) = \int \frac{g(x)^2}{p(x)}\,dx - \left(\int\frac{g(x)}{p(x)}\,p(x)\,dx\right)^2. $$

Your notation is really confusing. You can't write $E[X^2]=g(x)^2/p(x)$ because $X$ is a random variable, and $x$ is a variable for the value that $X$ might take. So $E[X^2]$ is a number, while $g(x)^2/p(x)$ is a function of $x$.

Equation 4 is called the Cauchy-Schwarz inequality, see here, here, or here.

As for your last question, the meaning of $\left(\int g(x)\,dx\right)^2-I^2$ is that the Cauchy-Schwarz inequality becomes an equality when the two functions $u$ and $v$ are proportional to each other, $u=cv$. Therefore, if we write $$ D\eta = \int \frac{g^2(x)}{p(x)}\,dx - I^2 \geq \left(\int |g(x)|\,dx\right)^2 - I^2, $$ we know that not only is the variance always at least as large as the right-hand side, it is equal to the right-hand side when $|g(x)|/\sqrt{p(x)}$ is proportional to $\sqrt{p(x)}$ (i.e., when $p$ is proportional to $|g|$, which is what he says).

I don't quite understand what you're asking in the rest of your question 4, but importance sampling will produce the correct estimate whenever $M\eta=I$ (i.e., whenever $g(x)\neq0$ implies $p(x)\neq0$). The thing that the choice of $p$ affects is the variance of the estimate: how quickly the estimate converges to its true value. The speed of convergence is why it makes sense to try and choose $p(x)$ well.

Answer 2

I know equation number 4 is the Cauchy-Schwarz inequality where they are defining their inner product of over this functional vector space as $$\langle f(x),g(x)\rangle=\int^{b}_{a} \left|f(x)g(x)\right|dx$$ and the Cauchy-Schwarz inequality is just $$\left(\langle f(x),g(x)\rangle\right)^{2}\leq \langle f(x),f(x)\rangle\langle g(x),g(x)\rangle$$

As for $M(\eta^{2})=\int \dfrac{g(x)^{2}}{p(x)^{2}}p(x)dx=\int \dfrac{g(x)^{2}}{p(x)}dx$ by LOTUS

Isn't also $\left(\int^{b}_{a}g(x)dx\right)^{2}=I^{2}$ so $\left(\int^{b}_{a}g(x)dx\right)^{2}-I^{2}=0$ and equation 5 shows that $D\eta\geq 0$

Also I feel as if equation 2 proves equation 1 but maybe that's all wrong Sorry about other questions I don't have enough experience with this subject matter to give you a meaningful answer.