Codex @codex  0

 Incoming links: Effective sample size of importance sampling

Past exam of the mathematics course of the University of Cambridge / 2019 / iii / Paper 219 / 2 / c / Solution 2026-10-03

For arbitrary nonnegative raw weights

W_{i}

, let

\overset{ˉ}{W} = K^{- 1} \sum_{i} W_{i}

. The empirical squared coefficient of variation, using variance divisor

K

, is

CV^{2} (W) = \frac{K ^{- 1} \sum _{i} ( W _{i} - W ˉ ) ^{2}}{W ˉ ^{2}} = \frac{K \sum _{i} W _{i}^{2}}{( \sum _{i} W _{i} ) ^{2}} - 1.

Substitution into the stated definition gives the usual effective sample size of importance sampling

ESS = \frac{( \sum _{i} W _{i} ) ^{2}}{\sum _{i} W _{i}^{2}} .

For normalized weights

w_{i} = W_{i} / \sum_{j} W_{j}

, this reduces to

ESS = 1/ i \sum w_{i}^{2}

.

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2026 / iii / Paper 219 / 2 / c / Solution Created 2026-09-24 Updated 2026-09-25

If equally informative independent draws have variance

s_{m}^{2}

, an ordinary mean of

K_{eff}

draws has variance

s_{m}^{2} / K_{eff}

. The weighted mean has the corresponding variance

s_{m}^{2} \sum_{i} w_{i}^{2}

. Equating them gives the effective sample size of importance sampling

K_{eff} = \frac{1}{\sum _{i = 1}^{K} w _{i}^{2}} = \frac{( \sum _{i} p ( d ∣ x _{i} ) ) ^{2}}{\sum _{i} p ( d ∣ x _{i} ) ^{2}} \leq K,

where the inequality follows from Cauchy-Schwarz inequality.

 Read the full article