Importance sampling and example

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

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: