Importance Sampling

Definition

Importance sampling is used when we want to estimate the expectation $E_{p(x)}[f(x)]$ of a function $f$ under a probability distributtion $p(x)$, but sampling directly from the distribution is either inefficient or impossible. $E_{p(x)}[f(x)]=\int f(x)\frac{p(x)}{q(x)}q(x)dx=E_{q(x)}\left[f(x)\frac{p(x)}{q(x)}\right]\approx \frac{1}{N}\sum _{n=1}^N\frac{p(x_n)}{q(x_n)}f(x_n)$ Where

• $p(x)$ is the target distribution
• $q(x)$ is the proposal distribution whose support includes that of the support of the target distribution $p(x)$ ($\forall x,p(x)>0\Rightarrow q(x)>0$). The proposal distribution needs to be easy to evaluate and sample from. Also, to reduce the variance of the expectation, $q(x)$ should be high where $|p(x)f(x)|$ is high.
• $\frac{p(x)}{q(x)}$ is the importance weight.