Pre-requisites

Overview

Definition

Suppose we want to compute the expectation of a function \(f(X)\) with respect to a distribution with density \(p(x)\). So \[I = \int f(x) p(x) dx.\] That is \[I = E[f(X)]\] where the expectation is taken over a random variable \(X\) with density \(p\). We could approximate \(I\) by “naive simulation”: \[I \approx (1/M) \sum_{m} f(X_m)\] where \(X_1,\dots,X_M \sim p(x)\).

Now let \(q(x)\) denote any other density function that is non-zero whenever \(p(x)\) is non-zero. (We need this condition to avoid dividing by 0 in what follows). Then we can rewrite this as \[I = \int f(x) [p(x)/q(x)] q(x) dx.\]

That is \[I = E[ f(X)p(X)/q(X)]\] where the expectation is taken over a random variable X with density \(q\). So we could also approximate \(I\) by simulation: \[I \approx (1/M) \sum_{m} f(X'_m)p(X'_m)/q(X'_m)\] where \(X'_1,\dots,X'_m \sim q(x)\).

This is called “Importance Sampling” (IS) and \(q\) is called the “Importance sampling function”.

The idea behind IS is that if \(q\) is well chosen then the approximation to \(I\) will be better than the naive approximation.

Examples

Suppose \(X \sim N(0,1)\), and we want to compute \(\Pr(X>z)\) for \(z = 10\). That is, \(f(x) = I(x>10)\) and \(p(x)= \phi(x)\) is the density of the standard normal distribution.

Let’s try naive simulation,
and compare it with the “truth”, as ascertained by the R function pnorm.

  set.seed(100)
  X = rnorm(100000)
  mean(1*(X>10))

[1] 0

  pnorm(10,lower.tail=FALSE)

[1] 7.619853e-24

You can see the problem with naive simulation: all the simulations are less than 10 (where f(x)=0), so you don’t get any precision.

Now we use IS. Here we code the general case for \(z\), using IS function \(q\) to be \(N(z,1)\). Note that because of this choice of \(q\) many of the samples are \(>z\), where \(f\) is non-zero, and we hope to get better precision. Of course, we could do this problem much better ways… this is just a toy illustration of IS.

pnorm.IS= function(z,nsamp=100000){
  y = rnorm(nsamp,z,1)
  w = exp(dnorm(y,0,1,log=TRUE) - dnorm(y,z,1, log=TRUE))
  mean(w*(y>z))
}
pnorm.IS(10)

[1] 7.673529e-24

pnorm(10,lower.tail=FALSE)

[1] 7.619853e-24

Example: computing with means on log scale

We just push this example a bit further, to illustrate a numerical issue that can arise quite generally (not just for IS).

Let’s try the above with \(z=100\).

pnorm.IS(100)

[1] 0

pnorm(100,lower.tail=FALSE)

[1] 0

Hmmm.. we are having numerical issues.

The trick to solving this is doing things on log scale. But the IS formula involves averaging, and we have to do the averaging on the raw scale, not the log scale. This function allows us to do this. Perhaps you can work out what is going on here?

#function to find the log of the mean of exp(lx).
lmean=function(lx){
  m = max(lx)
  m + log(mean(exp(lx-m))) 
}

Exploiting this we can now do IS for \(z=100\):

lpnorm.IS= function(z,nsamp=100000){
  y = rnorm(nsamp,z,1)
  w = dnorm(y,0,1,log=TRUE) - dnorm(y,z,1, log=TRUE)
  log(mean(y>z)) + lmean(w[y>z])
}
lpnorm.IS(100)
pnorm(100,lower.tail=FALSE,log=TRUE)

sessionInfo()

R version 3.3.2 (2016-10-31)
Platform: x86_64-pc-linux-gnu (64-bit)
Running under: Ubuntu 14.04.5 LTS

locale:
 [1] LC_CTYPE=en_US.UTF-8       LC_NUMERIC=C              
 [3] LC_TIME=en_US.UTF-8        LC_COLLATE=en_US.UTF-8    
 [5] LC_MONETARY=en_US.UTF-8    LC_MESSAGES=en_US.UTF-8   
 [7] LC_PAPER=en_US.UTF-8       LC_NAME=C                 
 [9] LC_ADDRESS=C               LC_TELEPHONE=C            
[11] LC_MEASUREMENT=en_US.UTF-8 LC_IDENTIFICATION=C       

attached base packages:
[1] stats     graphics  grDevices utils     datasets  methods   base     

other attached packages:
[1] rmarkdown_1.1

loaded via a namespace (and not attached):
 [1] magrittr_1.5    assertthat_0.1  formatR_1.4     htmltools_0.3.5
 [5] tools_3.3.2     yaml_2.1.13     tibble_1.2      Rcpp_0.12.7    
 [9] stringi_1.1.1   knitr_1.14      stringr_1.0.0   digest_0.6.9   
[13] gtools_3.5.0    evaluate_0.9