Editing Importance sampling (section)

== Basic theory ==
<!-- '''E'''[''X;P''] / \mathbf{E}[X;P] represents the expectation of ''X''. -->

Let <math>X\colon \Omega\to \mathbb{R}</math> be a [[random variable]] in some [[probability space]] <math>(\Omega,\mathcal{F},\mathbb{P})</math>. We wish to estimate the [[expected value]] of <math>X</math> under <math>\mathbb{P}</math>, denoted <math>\mathbb{E}_\mathbb{P}[X]</math>. If we have statistically independent random samples <math>X_1, \ldots, X_n</math>, generated according to <math>\mathbb{P}</math>, then an empirical estimate of <math>\mathbb{E}_{\mathbb{P}}[X]</math> is just

: <math>
  \widehat{\mathbb{E}}_{\mathbb{P}}[X] = \frac{1}{n} \sum_{i=1}^n X_i \quad \mathrm{where}\; X_i \sim \mathbb{P}(X)
</math>

and the precision of this estimate depends on the variance of <math>X</math>:

: <math>
   \operatorname{var}_\mathbb{P}\big[\widehat{\mathbb{E}}_{\mathbb{P}}[X]\big] = \frac{\operatorname{var}_\mathbb{P}[X]} n.
</math>

The basic idea of importance sampling is to sample from a different distribution to lower the variance of the estimation of <math>\mathbb{E}_\mathbb{P}[X]</math>, or when sampling directly from <math>\mathbb{P}</math> is difficult.

This is accomplished by first choosing a random variable <math>Y\geq 0</math> such that <math>\mathbb{E}_\mathbb{P}[Y] = 1</math> and that <math>\mathbb{P}</math>-[[almost everywhere]] <math>Y(\omega)\neq 0</math>.
With the variable <math>Y</math> we define a probability <math>\mathbb{Q}</math> that satisfies
: <math>
  \mathbb{E}_{\mathbb{P}}[X] = \mathbb{E}_{\mathbb{Q}}\left[\frac{X}{Y}\right].
</math>

The variable <math>X/Y</math> will thus be sampled under <math>\mathbb{Q}</math> to estimate <math>\mathbb{E}_{\mathbb{P}}[X]</math> as above and this estimation is improved when
: <math>
  \operatorname{var}_{\mathbb{Q}}\left[\frac{X}{Y}\right] < \operatorname{var}_{\mathbb{P}}[X].
</math>

When <math>X</math> is of constant sign over <math>\Omega</math>, the best variable <math>Y</math> would clearly be <math>Y^*=\frac{X}{\mathbb{E}_{\mathbb{P}}[X]}\geq 0</math>, so that <math>X/Y^*</math> is the searched constant <math>\mathbb{E}_{\mathbb{P}}[X]</math> and a single sample under <math>\mathbb{Q}^*</math> suffices to give its value. Unfortunately we cannot take that choice, because <math>\mathbb{E}_{\mathbb{P}}[X]</math> is precisely the value we are looking for! However this theoretical best case <math>Y^*</math> gives us an insight into what importance sampling does: for all <math> x \in \mathbb{R}</math>, the density of <math>\mathbb{Q}^*</math> at <math>X=x</math> can be written as
: <math>\begin{align}
\mathbb{Q}^*\big(X\in[x;x+dx]\big) &= \int_{\omega\in\{X\in[x;x+dx]\}} \frac{X(\omega)}{\mathbb{E}_{\mathbb{P}}[X]} \, d\mathbb{P}(\omega) \\[6pt] &= \frac{1}{\mathbb{E}_{\mathbb{P}}[X]}\; x\,\mathbb{P}(X\in[x;x+dx]).
\end{align}
</math>
To the right, <math>x\,\mathbb{P}(X\in[x;x+dx])</math> is one of the infinitesimal elements that sum up to <math>\mathbb{E}_{\mathbb{P}}[X]</math>:

: <math>\mathbb{E}_{\mathbb{P}}[X] = \int_{-\infty}^{+\infty} x\,\mathbb{P}(X\in[x;x+dx]) </math>
therefore, a good probability change <math>\mathbb{Q}</math> in importance sampling will redistribute the law of <math>X</math> so that its samples' frequencies are sorted directly according to their contributions in <math>\mathbb{E}_{\mathbb{P}}[X]</math> as opposed to <math>\mathbb{E}_{\mathbb{P}}[1]</math>. Hence the name "importance sampling."

Importance sampling is often used as a [[Monte Carlo integration|Monte Carlo integrator]].
When <math>\mathbb{P}</math> is the uniform distribution over <math>\Omega =\mathbb{R}</math>, the expectation <math>\mathbb{E}_{\mathbb{P}}[X]</math> corresponds to the integral of the real function <math>X\colon \mathbb{R}\to\mathbb{R}</math>.