# 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$