Editing Importance sampling (section)

=== Mathematical approach ===

Consider estimating by simulation the probability <math>p_t\,</math> of an event <math>X \ge t</math>, where <math>X</math> is a random variable with [[cumulative distribution function]] <math>F(x)</math> and [[probability density function]] <math>f(x)= F'(x)\,</math>, where prime denotes [[derivative]]. A <math>K</math>-length [[independent and identically distributed]] (i.i.d.) sequence <math>X_i\,</math> is generated from the distribution <math>F</math>, and the number <math>k_t</math> of random variables that lie above the threshold <math>t</math> are counted. The random variable <math>k_t</math> is characterized by the [[Binomial distribution]]

:<math>P(k_t = k)={K\choose k}p_t^k(1-p_t)^{K-k},\,\quad \quad k=0,1,\dots,K.</math>

One can show that <math>\mathbb{E} [k_t/K] = p_t</math>, and <math>\operatorname{var} [k_t/K] = p_t(1-p_t)/K</math>, so in the limit <math>K \to \infty</math> we are able to obtain <math>p_t</math>.  Note that the variance is low if <math>p_t \approx 1</math>.  Importance sampling is concerned with the determination and use of an alternate density function <math>f_*\,</math>(for <math>X</math>), usually referred to as a biasing density, for the simulation experiment. This density allows the event <math>{ X \ge t\ }</math> to occur more frequently, so the sequence lengths <math>K</math> gets smaller for a given [[estimator]] variance. Alternatively, for a given <math>K</math>, use of the biasing density results in a variance smaller than that of the conventional Monte Carlo estimate. From the definition of <math>p_t\,</math>, we can introduce <math>f_*\,</math> as below.

:<math>
\begin{align}
p_t & = \mathbb{E} [1_{\{X \ge t\}}] \\[6pt]
& = \int 1_{\{x \ge t\}} \frac{f(x)}{f_*(x)} f_*(x) \,dx \\[6pt]
& = \mathbb{E}_* [1_{\{X \ge t\}} W(X)]
\end{align}
</math>

where

:<math>W(\cdot) \equiv \frac{f(\cdot)}{f_*(\cdot)} </math>

is a likelihood ratio and is referred to as the weighting function. The last equality in the above equation motivates the estimator

:<math>\hat p_t = \frac{1}{K}\,\sum_{i=1}^K 1_{\{X_i \ge t\}} W(X_i),\,\quad \quad X_i \sim  f_*</math>

This is the importance sampling estimator of <math>p_t\,</math> and is unbiased. That is, the estimation procedure is to generate i.i.d. samples from <math>f_*\,</math> and for each sample which exceeds <math>t\,</math>, the estimate is incremented by the weight <math>W\,</math> evaluated at the sample value. The results are averaged over <math>K\,</math> trials. The variance of the importance sampling estimator is easily shown to be

:<math>
\begin{align}
\operatorname{var}_*\widehat p_t & = \frac{1}{K}\operatorname{var}_* [1_{\{X_i \ge t\}}W(X)] \\[5pt]
& = \frac{1}{K}\left\{\mathbb{E}_*[1_{\{X_i \ge t\}}^2 W^2(X)] - p_t^2\right\} \\[5pt]
& = \frac{1}{K}\left\{\mathbb{E}[1_{\{X_i \ge t\}}W(X)] - p_t^2\right\}
\end{align}
</math>

Now, the importance sampling problem then focuses on finding a biasing density <math>f_*\,</math> such that the variance of the importance sampling estimator is less than the variance of the general Monte Carlo estimate. For some biasing density function, which minimizes the variance, and under certain conditions reduces it to zero, it is called an optimal biasing density function.