Importance sampling

Consider estimating by simulation the probability ${\displaystyle p_{t}\,}$ of an event ${\displaystyle X\geq t}$, where ${\displaystyle X}$ is a random variable with distribution ${\displaystyle F}$ and probability density function ${\displaystyle f(x)=F'(x)\,}$, where prime denotes derivative. A ${\displaystyle K}$-length independent and identically distributed (i.i.d.) sequence ${\displaystyle X_{i}\,}$ is generated from the distribution ${\displaystyle F}$, and the number ${\displaystyle k_{t}}$ of random variables that lie above the threshold ${\displaystyle t}$ are counted. The random variable ${\displaystyle k_{t}}$ is characterized by the Binomial distribution

${\displaystyle P(k_{t}=k)={K \choose k}p_{t}^{k}(1-p_{t})^{K-k},\,\quad \quad k=0,1,\dots ,K.}$

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

${\displaystyle {\begin{aligned}p_{t}&={E}[1(X\geq t)]\\[6pt]&=\int 1(x\geq t){\frac {f(x)}{f_{*}(x)}}f_{*}(x)\,dx\\[6pt]&=E_{*}[1(X\geq t)W(X)]\end{aligned}}}$

where

${\displaystyle W(\cdot )\equiv {\frac {f(\cdot )}{f_{*}(\cdot )}}}$

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

${\displaystyle {\hat {p}}_{t}={\frac {1}{K}}\,\sum _{i=1}^{K}1(X_{i}\geq t)W(X_{i}),\,\quad \quad X_{i}\sim f_{*}}$

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

${\displaystyle {\begin{aligned}\operatorname {var} _{*}{\widehat {p}}_{t}&={\frac {1}{K}}\operatorname {var} _{*}[1(X\geq t)W(X)]\\[5pt]&={\frac {1}{K}}\left\{{E_{*}}[1(X\geq t)^{2}W^{2}(X)]-p_{t}^{2}\right\}\\[5pt]&={\frac {1}{K}}\left\{{E}[1(X\geq t)W(X)]-p_{t}^{2}\right\}\end{aligned}}}$

Now, the importance sampling problem then focuses on finding a biasing density ${\displaystyle f_{*}\,}$ 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.

Although there are many kinds of biasing methods, the following two methods are most widely used in the applications of importance sampling.

Shifting probability mass into the event region ${\displaystyle {X\geq t\ }}$ by positive scaling of the random variable ${\displaystyle X\,}$ with a number greater than unity has the effect of increasing the variance (mean also) of the density function. This results in a heavier tail of the density, leading to an increase in the event probability. Scaling is probably one of the earliest biasing methods known and has been extensively used in practice. It is simple to implement and usually provides conservative simulation gains as compared to other methods.

In importance sampling by scaling, the simulation density is chosen as the density function of the scaled random variable ${\displaystyle aX\,}$, where usually ${\displaystyle a>1}$ for tail probability estimation. By transformation,

${\displaystyle f_{*}(x)={\frac {1}{a}}f{\bigg (}{\frac {x}{a}}{\bigg )}\,}$

and the weighting function is

${\displaystyle W(x)=a{\frac {f(x)}{f(x/a)}}\,}$

While scaling shifts probability mass into the desired event region, it also pushes mass into the complementary region ${\displaystyle X<t\,}$ which is undesirable. If ${\displaystyle X\,}$ is a sum of ${\displaystyle n\,}$ random variables, the spreading of mass takes place in an ${\displaystyle n\,}$ dimensional space. The consequence of this is a decreasing importance sampling gain for increasing ${\displaystyle n\,}$, and is called the dimensionality effect. A modern version of importance sampling by scaling is e.g. so-called sigma-scaled sampling (SSS) which is running multiple Monte Carlo (MC) analysis with different scaling factors. In opposite to many other high yield estimation methods (like worst-case distances WCD) SSS does not suffer much from the dimensionality problem. Also addressing multiple MC outputs causes no degradation in efficiency. On the other hand, as WCD, SSS is only designed for Gaussian statistical variables, and in opposite to WCD, the SSS method is not designed to provide accurate statistical corners. Another SSS disadvantage is that the MC runs with large scale factors may become difficult, e. g. due to model and simulator convergence problems. In addition, in SSS we face a strong bias-variance trade-off: Using large scale factors, we obtain quite stable yield results, but the larger the scale factors, the larger the bias error. If the advantages of SSS does not matter much in the application of interest, then often other methods are more efficient.

Another simple and effective biasing technique employs translation of the density function (and hence random variable) to place much of its probability mass in the rare event region. Translation does not suffer from a dimensionality effect and has been successfully used in several applications relating to simulation of digital communication systems. It often provides better simulation gains than scaling. In biasing by translation, the simulation density is given by

${\displaystyle f_{*}(x)=f(x-c),\quad c>0\,}$

where ${\displaystyle c\,}$ is the amount of shift and is to be chosen to minimize the variance of the importance sampling estimator.

The fundamental problem with importance sampling is that designing good biased distributions becomes more complicated as the system complexity increases. Complex systems are the systems with long memory since complex processing of a few inputs is much easier to handle. This dimensionality or memory can cause problems in three ways:

• long memory (severe intersymbol interference (ISI))
• unknown memory (Viterbi decoders)
• possibly infinite memory (adaptive equalizers)

In principle, the importance sampling ideas remain the same in these situations, but the design becomes much harder. A successful approach to combat this problem is essentially breaking down a simulation into several smaller, more sharply defined subproblems. Then importance sampling strategies are used to target each of the simpler subproblems. Examples of techniques to break the simulation down are conditioning and error-event simulation (EES) and regenerative simulation.

In order to identify successful importance sampling techniques, it is useful to be able to quantify the run-time savings due to the use of the importance sampling approach. The performance measure commonly used is ${\displaystyle \sigma _{MC}^{2}/\sigma _{IS}^{2}\,}$, and this can be interpreted as the speed-up factor by which the importance sampling estimator achieves the same precision as the MC estimator. This has to be computed empirically since the estimator variances are not likely to be analytically possible when their mean is intractable. Other useful concepts in quantifying an importance sampling estimator are the variance bounds and the notion of asymptotic efficiency. One related measure is the so-called Effective Sample Size (ESS).[6]

Variance is not the only possible cost function for a simulation, and other cost functions, such as the mean absolute deviation, are used in various statistical applications. Nevertheless, the variance is the primary cost function addressed in the literature, probably due to the use of variances in confidence intervals and in the performance measure ${\displaystyle \sigma _{MC}^{2}/\sigma _{IS}^{2}\,}$.

An associated issue is the fact that the ratio ${\displaystyle \sigma _{MC}^{2}/\sigma _{IS}^{2}\,}$ overestimates the run-time savings due to importance sampling since it does not include the extra computing time required to compute the weight function. Hence, some people evaluate the net run-time improvement by various means. Perhaps a more serious overhead to importance sampling is the time taken to devise and program the technique and analytically derive the desired weight function.

When different proposal distributions, ${\displaystyle g_{n}(x)}$ , ${\displaystyle n=1,\ldots ,N,}$ are jointly used for drawing the samples ${\displaystyle x_{1},\ldots ,x_{N},}$ different proper weighting functions can be employed (e.g., see [7][8][9][10]). In an adaptive setting, the proposal distributions, ${\displaystyle g_{n,t}(x)}$ , ${\displaystyle n=1,\ldots ,N,}$ and ${\displaystyle t=1,\ldots ,T,}$ are updated each iteration ${\displaystyle t}$ of the adaptive importance sampling algorithm. Hence, since a population of proposal densities is used, several suitable combinations of sampling and weighting schemes can be employed.[11][12][13][14][15][16][17]