Importance Sampling

Description

Importance Sampling is a technique for estimating the expectation $\mu$ of a random variable $f(x)$ under distribution $p$ from samples of a different distribution $q$.

The key observation is that $\mu$ is can expressed as the expectation of a different random variable $f^{\text{*}}(x)=\frac{p(x)}{q(x)}$ under $q$

$$\begin{array}{rl}\mu & ={\mathbf{E}}_p[f(x)]\\ & \\ & =\sum _{x}p(x)f(x)\\ & \\ & =\sum _x\frac{q(x)}{q(x)}p(x)f(x)\\ & \\ & =\sum _x\frac{p(x)}{q(x)}q(x)f(x)\\ & \\ & ={\mathbf{E}}_q\frac{p(x)}{q(x)}f(x)\\ & \\ & ={\mathbf{E}}_q[f^{\text{*}}(x)]\end{array}$$

Technique condition: $q$ must have support everywhere $p$ dose. Without this condition, the equation is biased! Note: $q$ can support things that $p$ doesn’t.