Importance Sampling

We have two sources D₁(x) and D₂(x) that produce differnt distributions. We compute expectation of a function F(x) on one source while sampling the other source. The expectation of F(x) with respect to distribution D is the sum of products of all values of X with the probability that D assigns that value. In our case:

E_D2[F(x)] = $\sum{D_{2}}(X)F(x)$ = $\sum{D_{1}}(X)(\frac{D_{2}(X)}{D_{1}(X)})F(x)$ = E_D1[( $\frac{D_{2}(X)}{D_{1}(X)}$)F(x)]

EXAMPLE 1
Input:

• F(x) = k.
• $D_{1} = Prob[k] = \frac{1}{2^{k}}.$
• $D_{2} = Prob[k] = \frac{3}{4}(\frac{1}{4})^{k-1}.$

Computation:

• We find expectancy E_D2[k] from samples of D₁.
  
  $E_{D_{1}}[k] = E_{D_{2}}[(\frac{D_{1}(k)}{D_{2}(k)})k]= E_{D_{2}}[(\frac{(\fr... ...)k] = E_{D_{2}}[k\frac{4}{3}\frac{1}{2}2^{k-1}] = E_{D_{2}}[k\frac{2}{3}^{k}]$
• We check the equation by computing E_D2[F(x)].
  
  $E_{D_{2}}[k\frac{2}{3}^{k}]$ = $\sum_{k}(\frac{1}{4})^{k-% 1}(\frac{3}{4})(\frac{2^{k}}{3})(k)$ = $\sum_{k}(\frac{1}{2^{k}})k$ = E_D1[k]
• One of the problems in importance sampling is the variance.
  In this case.
  
  $E_{D_{2}}[(k\frac{2^{k}}{3})^{2}]$ = $\sum_{k}(k^{2})(\frac{2^{2k}}{9})(\frac{1}{4})^{k-% 1}\frac{3}{4}$ = $\sum_{k}\frac{k^{2}}{3}$ = $\infty$