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