### 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

$$$Z'_N = \frac{1}{N} \sum_{i=1}^N f(Y_i) \frac{p(Y_i)}{q(Y_i)}.$$$

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

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

#### 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'$$ .