Importance Sampling

Theory

Importance sampling is a general technique which allows the variance of the Monte-Carlo estimator for an integral to be reduced. The goal is still to compute \(\mathbb{E}_p[f]\). Let \(q\) be another probability on \(\mathbb{R}^n\). We rewrite \(\mathbb{E}_p[f]\) as

\[ \begin{align*} \mathbb{E}_p[f] &= \int_{\mathbb{R}^n} f(x) p(x) dx\\ &= \int_{\mathbb{R}^n} \frac{f(x) p(x)}{q(x)} q(x) dx \\ &= \mathbb{E}_q[f p / q] \end{align*}\]

Using i.i.d. RV \(Y_i \sim q\), we modify the estimator to

\[ \begin{equation} Z'_N = \frac{1}{N} \sum_{i=1}^N f(Y_i) \frac{p(Y_i)}{q(Y_i)}. \end{equation}\]

Denoting \(\sigma_q^2 = \mathbb{E}_p[f^2 p/q] - \mathbb{E}_p[f]^2\), one has:

\[ \begin{equation} \label{eq:var_importance_sampling} \left\{ \begin{aligned} &\mathbb{E}[Z'_N] = \mathbb{E}_p[f] \\ &Var(Z'_N) = \sigma_q^2 / N \end{aligned} \right. \end{equation}\]

Remark

If \(q(x) = f(x)p(x) / \mathbb{E}_p[f]\) then \(\sigma_q = 0\). In this case, the estimator has 0 variance and will give the correct result for any \(N\). Unfortunately, this requires knowing the result beforehand.

Choosing a probability \(q\) roughly proportional to \(f p\) reduces \(\sigma_q^2\) and therefore the variance of the estimator \(Z_N'\) .

Python example