Importance sampling and example

December 27, 2013 by Leave a comment

1. Importance sampling idea

We have random variable X_{1} , it has pdf (probability density function) p(x),

we have known
E\left ( f\left ( X_{1} \right ) \right )= \int f\left ( x \right )p\left ( x \right )dx

And according Monte Carlo estimator, if we want evaluate function f(x) by samples from p(x), we got
E\left ( f\left ( X_{1} \right ) \right ) \approx \frac{1}{n}\sum_{1}^{n}f\left ( x_{i} \right ) where x_{i} is sample from X_{1}

Let’s say we want( or can only) to sample from another distribution function q(x), but we still want to get the value E\left ( f\left ( X_{1} \right ) \right ) by Monte Carlo method, what we should do?

For clear, we use another random variable X_{2} , its pdf  q(x)

A little trick
E\left ( f\left ( X_{1} \right ) \right )= \int f\left ( x \right )p\left ( x \right )dx=\int f\left ( x \right )\frac{p\left ( x \right )}{q\left ( x \right )}q\left ( x \right )dx

it just looks like we want evaluate function f\left ( x \right )\frac{p\left ( x \right )}{q\left ( x \right )} by samples from q(x), using the new random variable X_{2} , we have

\int f\left ( x \right )\frac{p\left ( x \right )}{q\left ( x \right )}q\left ( x \right )dx = E\left ( f\left ( X_{2} \right )\frac{p\left ( X_{2} \right )}{q\left ( X_{2} \right )} \right )

According Monte Carlo like above, we should have
E\left ( f\left ( X_{2} \right )\frac{p\left ( X_{2} \right )}{q\left ( X_{2} \right )} \right ) \approx \frac{1}{n}\sum_{1}^{n}f\left ( x_{i} \right )\frac{p\left ( x_{i} \right )}{q\left ( x_{i} \right )}

so we have
E\left ( f\left ( X_{1} \right ) \right ) \approx \frac{1}{n}\sum_{1}^{n}f\left ( x_{i} \right )\frac{p\left ( x_{i} \right )}{q\left ( x_{i} \right )}

where x_{i} is sample from X_{2}

this is what importantce sampling does, it uses samples from another distribution funtion, but still evaluate the old function for old random variable.

2. why Importance sampling can do better

let’s caculate variance on

\sigma ^2 \left ( \frac{1}{n}\sum_{1}^{n}f\left ( x_{i} \right ) \right ) = \frac{1}{n^2} \sigma ^2 \left ( \sum_{1}^{n}f\left ( x_{i} \right ) \right ) = \frac{1}{n} \sigma ^2 \left ( f\left ( x \right ) \right )

\sigma ^2 \left ( \frac{1}{n}\sum_{1}^{n}f\left ( x_{i} \right )\frac{p\left ( x_{i} \right )}{q\left ( x \right )} \right ) = \frac{1}{n} \sigma ^2 \left ( f\left ( x \right ) \frac{p\left ( x \right )}{q\left ( x \right )} \right )

so it we select q(x) smartly, we can get a much smaller \sigma^2

 

Advertisement

Filed under Tech Log