Effective Sample Size

14 September 2017

Using the notation from the note on importance sampling, we investigate effective sample size (ESS), $$N_e$$, which is used to assess the quality of an importance sampler estimator: \begin{align} N_e &:= \frac{1}{\sum_{n = 1}^N w_n^2}, \end{align} where $$w_n$$ are the normalized weights.

Recall that variance of a Monte Carlo estimator, $$I_N^{\text{MC}}$$, is $$\Var[f(X)] / N$$. Intuitively, $$N_e$$ should provide the following approximation: \begin{align} \Var\left[\tilde I_N^{\text{IS}}\right] \approx \frac{\Var[f(X)]}{N_e}, \end{align} i.e., it approximates the variance of the importance sampling estimator by the variance of the Monte Carlo estimator with $$N_e$$ direct samples from $$p$$.

Derivation 1

(From Art Owen’s book chapter). Making an approximation that the weights are not random variables but fixed values, i.e. $$\tilde w_n$$ are the unnormalized weights and $$w_n = \tilde w_n / \sum_{k = 1}^N \tilde w_n$$ are the normalized weights. \begin{align} \Var\left[\tilde I_N^{\text{IS}}\right] &\approx \Var\left[\frac{\sum_{n = 1}^N \tilde w_n f(X_n)}{\sum_{n = 1}^N \tilde w_n}\right] \\
&= \Var\left[\sum_{n = 1}^N w_n f(X_n)\right] \\
&= \sum_{n = 1}^N w_n^2 \Var\left[f(X_n)\right]. \end{align} Rearranging to equal $$\frac{\Var[f(X)]}{N_e}$$, we obtain \begin{align} N_e &= \frac{1}{\sum_{n = 1}^N w_n^2}. \end{align}

Derivation 2

(From Sebastian Nowozin’s blogpost).