Search for probability and statistics terms on Statlect
StatLect
Index > Asymptotic theory

Importance sampling

by , PhD

Importance sampling is a variance reduction technique used to reduce the variance of the approximation error made when approximating an expected value with Monte Carlo integration.

Table of Contents

Table of contents

  1. Equivalent expectations

  2. Importance samples

  3. Approximation errors

  4. The ideal sample

  5. Intuition

  6. Example

Equivalent expectations

Importance sampling is based on a simple technique that allows to compute expected values in many different but equivalent ways.

The next proposition shows how the technique works for discrete random vectors.

Proposition Let X be a Kx1 discrete random vector with support R_X and joint probability mass function [eq1]. Let g(x) be a function [eq2]. Let Y be another Kx1 discrete random vector Y with joint probability mass function [eq3] and such that [eq4] whenever [eq5]. Then, [eq6]

Proof

This is obtained as follows:[eq7]

An almost identical proposition holds for continuous random vectors.

Proposition Let X be a continuous Kx1 random vector with support R_X and joint probability density function [eq8]. Let g(x) be a function [eq2]. Let Y be another continuous random vector Y with joint probability density function [eq10] and such that [eq11] whenever [eq12]. Then, [eq13]

Proof

This is obtained as follows:[eq14]where we have used[eq15]as a shorthand for the multiple integral over the coordinates of x.

Importance samples

Suppose we need to compute the expected value[eq16] of a function of a random vector X by Monte Carlo integration.

The standard way to proceed is to use a computer-generated sample $x_{1}$,...,$x_{n}$ of realizations of n independent random vectors X_1,...,X_n having the same distribution as X, and use the sample mean [eq17]to approximate the expected value.

Thanks to the propositions in the previous section, we can compute an alternative Monte Carlo approximation of [eq18] by extracting n independent draws [eq19] from the distribution of another random vector Y (in what follows we assume that it is discrete, but everything we say applies also to continuous vectors) and by using the sample mean[eq20]as an approximation. This technique is called importance sampling.

The reason why importance sampling is used is that Y can often be chosen in such a way that the variance of the approximation error is much smaller than the variance of the standard Monte Carlo approximation.

Approximation errors

In the case of the standard Monte Carlo approximation, the variance of the approximation error is[eq21]while, in the case of importance sampling, the variance of the approximation error is[eq22]

Proof

In the standard case, the approximation error is[eq23]and its variance is[eq24]In the case of importance sampling, we have[eq25]

The ideal sample

Ideally, we would like to be able to choose Y in such a way that [eq26]is a constant, which would imply that the variance of the approximation error is zero.

The next proposition shows when this ideal situation is achievable.

Proposition If [eq27] for any $y$, then[eq28]when Y has joint probability mass function[eq29]

Proof

The ratio [eq30]is constant if the proportionality condition[eq31]holds. By imposing that [eq32] be a legitimate probability density function, we get[eq33]or[eq34]

Of course, the denominator [eq35] is unknown (otherwise we would not be discussing how to compute a Monte Carlo approximation for it), so that it is not feasible to achieve the optimal choice for Y. However, the formula for the probability mass function of the optimal Y gives us some indications about the choice of Y. In particular, the formula[eq34]tells us that the probability mass function of Y should place more mass where the product between the probability mass function of X and the value of the function $g$ is larger. In other words, the probability mass function of X should be tilted so as to give more weight to the values of X for which $gleft( X ight) $ is larger.

Intuition

In the previous sections we have seen that importance sampling consists in computing an alternative Monte Carlo approximation of [eq37] by extracting n independent draws [eq38] from the distribution of another random vector Y and by using the sample mean[eq39]as an approximation. We have also seen that this approximation has small variance when the probability mass function of Y puts more mass than the probability mass function of X on the values of X for which $gleft( X ight) $ is larger. This makes intuitive sense: if $gleft( X ight) $ is larger at some points, then we should try to sample $gleft( X ight) $ more frequently at those "important" points (in order to be more accurate about the value of $gleft( X ight) $ at those points); then, when we average our samples, we should take into account the fact that we over-sampled the important points by weighting them down with the weights [eq40]which are smaller than 1 when [eq41] is smaller than [eq42].

Example

Let us now illustrate importance sampling with an example.

Suppose X has a standard normal distribution (i.e., with mean $mu =0$ and standard deviation $sigma =1$) and [eq43]The function g(x) attains its maximum at the point $x=3$ and then rapidly goes to 0 for values of x that are smaller or larger than $3 $. On the contrary, the probability density function [eq44] of a standard normal random variable is almost zero at $x=3$. As a consequence, if we use a standard Monte Carlo approximation, we extract lots of values of x for which g(x) is almost zero, but we extract very few values for which g(x) is different from zero, and this results in a high variance of the approximation error.

In order to shift weight towards $x=3$, we can sample from Y, where Y has a normal distribution with mean $mu =3$ and standard deviation $sigma =1$.

The following MATLAB code shows how to do so and computes the standard Monte Carlo (MC) and the importance sampling (IS) approximations by using samples of $n=10,000$ independent draws from the distributions of $X $ and Y. 

rng(0)
n=10000;
x=randn(n,1);
g=10*exp(-5*(x-3).^4);
MC=mean(g)
stdMC=sqrt((1/n)*var(g))
y=3+randn(n,1);
g=10*exp(-5*(y-3).^4);
gWeighted=g.*normpdf(y,0,1)./normpdf(y,3,1);
IS=mean(gWeighted)
stdIS=sqrt((1/n)*var(gWeighted))

The standard deviations of the two approximations (stdMC and stdIS) are estimated by using the sample variances of [eq45] and [eq46]. If you run the code you can see that indeed the importance sampling approximation achieves a significant reduction in the approximation error (from 0.0084 to 0.0012).

How to cite

Please cite as:

Taboga, Marco (2017). "Importance sampling", Lectures on probability theory and mathematical statistics, Third edition. Kindle Direct Publishing. Online appendix. https://www.statlect.com/asymptotic-theory/importance-sampling.

The books

Most of the learning materials found on this website are now available in a traditional textbook format.

Featured pages
Explore
Main sections
About
Glossary entries
Share
  • To enhance your privacy,
  • we removed the social buttons,
  • but don't forget to share.