---
tag: 4PPT08K2M1
kind: statement
role: theorem
name: Importance sampling
msc: [65C05, 62D05]
uses: [A01GEGWKVB, HWP11G3HTN, 0ZY9DX8FBF, 0477R9PYAE, 0RFWW56Y22]
about: [A01GEGWKVB]
sources:
  - url: https://en.wikipedia.org/wiki/Importance_sampling
same_as:
  wikidata: Q1539564
  wikipedia: Importance sampling
---

## Statement

Let $p$ and $g$ be [[probability density functions|0ZY9DX8FBF]] on $\R^d$, and let $h \colon \R^d \to \R$ be measurable with $\int \abs{h}\, p < \infty$ and $q = \int h(x) p(x)\, dx$.
Assume that $g(x) > 0$ whenever $h(x) p(x) \ne 0$.
Let $Y_1, \ldots, Y_n$ be independent with density $g$, and let
$$\hat q_n = \frac{1}{n} \sum_{i=1}^{n} h(Y_i)\, \frac{p(Y_i)}{g(Y_i)},$$
with the convention that a term with $g(Y_i) = 0$ is $0$.
Then:

1. $\mathbb E \hat q_n = q$;
2. $\operatorname{Var} \hat q_n = \frac{1}{n} \left( \int \frac{h(x)^2 p(x)^2}{g(x)}\, dx - q^2 \right)$, where the integral runs over $\set{g > 0}$ and may be $+\infty$;
3. among all such $g$, the variance is smallest for $g^* = \abs{h} p / \int \abs{h} p$ (when $\int \abs{h} p > 0$), and its minimum is $\frac1n \bigl( (\int \abs{h} p)^2 - q^2 \bigr)$; in particular it is $0$ if $h \ge 0$.

## Remarks

Clause 1: $\mathbb E[h(Y) p(Y)/g(Y)] = \int_{g > 0} h p = q$, since $h p = 0$ where $g = 0$.
Clause 2 is the same computation for the second moment, divided by $n$ for independent samples.
Clause 3 follows from the [[Cauchy–Schwarz inequality|0RFWW56Y22]]: $\left( \int \abs{h} p \right)^2 = \left( \int \frac{\abs{h} p}{\sqrt g} \sqrt g \right)^2 \le \int \frac{h^2 p^2}{g}$, with equality when $g$ is proportional to $\abs{h} p$.
The optimal $g^*$ needs $\int \abs{h} p$, which is essentially the unknown; in practice one picks $g$ close in shape to $\abs{h} p$.
Example: let $X$ be standard normal and $q = P(X > 4) \approx 3.17 \times 10^{-5}$.
Plain sampling sees almost no hits.
Sampling from the normal density with mean $4$ puts half the samples in the event and reduces the relative error by orders of magnitude.
A badly chosen $g$ with lighter tails than $\abs{h} p$ can make the integral in clause 2 infinite, so the estimate converges very slowly and erratically.

## Explanations

### L1 human

Importance sampling estimates an average by sampling more often where the integrand matters most, and correcting for this bias with weights.
Each sample is weighted by the ratio $p/g$ of the target density to the sampling density, so the estimate stays exactly right on average.
If the sampling density follows the shape of the integrand, the weighted values are nearly constant and the estimate becomes very precise.
It is especially useful for rare events, which plain sampling almost never hits.

### L2 human

This is a [[variance reduction|A01GEGWKVB]] technique for the [[Monte Carlo method|HWP11G3HTN]], and also a change of measure: $g$ defines a new probability measure and $p/g$ is the Radon–Nikodym derivative.
When $p$ is known only up to a constant, one uses the self-normalised estimator $\sum w_i h(Y_i) / \sum w_i$ with $w_i = p(Y_i)/g(Y_i)$, which is biased but consistent.
The effective sample size $(\sum w_i)^2 / \sum w_i^2$ is a common diagnostic of weight degeneracy.
In rare-event simulation, exponential tilting of $p$ is a standard way to build $g$, and in sequential Monte Carlo the idea is applied step by step.