Importance Sampling

Algorithm Importance Sampling
Given a distribution , and a proposed distribution :

1. For
   1. Generate from
   2. Give a weight
      are weighted samples from .

Prop Weighted expectations under act as expectations under .
Proof Suppose weights . Then

Fact Variability of Weights
If weights are highly variable (i.e. is high), then it’s bad for importance sampling. For best performance, we prefer low variability weights.

Def Effective Sample Size
The effective sample size is usually used to measure weights variance, higher effective sample size, lower variability of weights:where are normalized weights.
Prop

• if for all except for some
• when for all
• To maximize , choose proposed to closely match .

Algorithm Sequential Importance Sampling