# 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).

## Properties of ESS

\begin{align}
p(x) &= 0.5 * \mathrm{Normal}(x; -10, 1) + 0.5 * \mathrm{Normal}(x; 10, 1) \\

q(x) &= \mathrm{Normal}(x; 10, 1) \\

f(x) &=
\begin{cases}
1 & \text{ if } x < 0 \\

0 & \text{ otherwise.}
\end{cases}
\end{align}

(From Exercise 9.11 from Art Owen’s book chapter).

[back]