Weight Variance and Effective Sample Size in Importance Sampling

Importance sampling trades the target density for a proposal density and corrects the swap with a weight. Every draw is used, which is its advantage over rejection, but the draws are no longer equal: a few large weights can dominate the sum, and the estimator behaves as if the sample were much smaller than it is. The effective sample size quantifies that shrinkage, and the second moment of the weight ratio decides whether the technique helps or makes the estimate worse than plain Monte Carlo.

The likelihood ratio does the correction

To estimate $\mu = \int h(x) f(x), dx$ by sampling from a proposal $g$ that is nonzero wherever $h f$ is nonzero, write

$$\mu = \int h(x) \frac{f(x)}{g(x)} g(x), dx = \mathbb{E}_g!\left[h(X) \frac{f(X)}{g(X)}\right],$$

so drawing $X_i \sim g$ and averaging $h(X_i) f(X_i)/g(X_i)$ is an unbiased estimator of $\mu$. The ratio $f/g$ is the likelihood ratio, and it is the whole mechanism: the proposal generates $X$, the weight re-rates it as if it had come from $f$.

The self-normalized form is what is used when $f$ or $g$ is known only up to a constant. Drawing $X_i \sim g$ and writing $w_i = f(X_i)/g(X_i)$, the estimator

$$\hat\mu = \frac{\sum_i w_i h(X_i)}{\sum_i w_i}$$

divides by the sum of the weights rather than by $n$. It is biased by an amount of order $1/n$, and the bias vanishes as the sample grows, but for small samples the normalized and unnormalized estimators can disagree by more than either error bar. Normalization is mandatory when the normalizing constants are unknown, as with the posterior in a Bayesian problem.

The second moment sets the variance

The variance of the unnormalized estimator is $\frac{1}{n}$ times the variance of $h(X) f(X)/g(X)$ under $g$, which expands to

$$\mathrm{Var}_g\left(\frac{h f}{g}\right) = \int \frac{h(x)^2 f(x)^2}{g(x)}, dx - \mu^2.$$

A good proposal makes $g$ proportional to $|h| f$, which drives the variance to zero in the ideal case where $g \propto h f$ and $h$ has one sign. A bad proposal makes $g$ small where $h f$ is large, and the integrand $h^2 f^2 / g$ explodes. The failure is not rare: a proposal that misses a region where the integrand is significant produces occasional draws with enormous weights, and those draws dominate both the estimate and its variance.

The weight variance is therefore the diagnostic. The coefficient of variation of the weights, $\mathrm{CV}^2(w) = \mathrm{Var}(w)/\mathbb{E}(w)^2$, measures how unevenly the proposal has distributed the mass, and for the self-normalized estimator the variance is approximately $\frac{1}{n}\mathrm{Var}_g(hf/g)$ plus a term of order $\mathrm{CV}^2(w)/n$. When the weights are uniform the correction disappears; when one weight is a thousand times the next, the estimate is effectively a single draw.

Effective sample size as the accounting

The effective sample size compresses the weight distribution into a single number. The standard definition is

$$n_{\text{eff}} = \frac{(\sum_i w_i)^2}{\sum_i w_i^2} = \frac{n}{1 + \mathrm{CV}^2(w)},$$

which equals $n$ when all weights are equal and drops toward 1 when a single weight dominates. It is not an estimate of the statistical efficiency; it is a normalization of the concentration of the weights, and it is read as the number of independent target draws that would have the same variance under a first-order approximation.

def effective_sample_size(weights):
    s = sum(weights)
    if s == 0:
        return 0.0
    ss = sum(w * w for w in weights)
    return s * s / ss

The arithmetic is revealing for typical cases. Ten equal weights give $n_{\text{eff}} = 10$. Weights proportional to $1, 2, \dots, 10$ give $n_{\text{eff}} = 55^2 / 385 \approx 7.86$, so a linear spread already costs a fifth of the sample. An exponential spread $2^0, 2^1, \dots, 2^9$ gives $n_{\text{eff}} \approx 1.996$, meaning the entire sample carries the weight of two draws. The number moves fast, and a proposal that looks reasonable on a histogram of $X$ can be revealed as nearly useless by its $n_{\text{eff}}$.

Why the tails are the whole problem

The weight ratio is largest exactly where $g$ under-represents the tail of $f$. For a normal target and a normal proposal with the same mean but a larger standard deviation $\sigma_g > \sigma_f$, the ratio is

$$\frac{f(x)}{g(x)} \propto \exp!\left(\frac{x^2}{2}\left(\frac{1}{\sigma_f^2} - \frac{1}{\sigma_g^2}\right)\right),$$

which grows without bound in $|x|$. A heavier proposal tail than the target keeps the ratio bounded; a lighter one makes it explode. The rule is asymmetric: the proposal must have tails at least as heavy as the target, and the penalty for violating it is an infinite weight variance, not a large one.

The same requirement is why estimating a rare-event probability is the canonical success of importance sampling. To estimate $p = P(X \in A)$ with $p$ near $10^{-6}$, plain sampling needs around $10^8$ draws just to see a handful of hits, and its variance is $p(1-p)$. Shifting the proposal to center on $A$ makes the event common, and the weight $f/g$ is small but finite on the typical proposal draw. The estimator then has the variance of a common-event estimator divided by the square of a weight of order $p$, which can be orders of magnitude smaller than $p/n$ when the shift is well chosen.

The failure mode is a shift that overshoots. If the proposal concentrates too hard on $A$, the few draws that fall outside $A$ carry weights large enough to dominate the sum, and the variance grows again. There is an optimal proposal for the problem, and the entire practical art of rare-event simulation is approximating it without knowing the answer in advance.

The two ways the weight variance hides

A large weight variance does not announce itself with a large estimate. The self-normalized estimator is a ratio, and both numerator and denominator are pulled up by the same heavy draws, so the reported value can sit near a plausible number while the effective sample size is in single digits. The only reliable signal is the weight distribution itself: a table of the largest weights, their indices, and the effective sample size. A single draw carrying half the total weight is a one-point estimator regardless of what the mean and standard error printed next to it say.

The second hiding place is in a fixed seed. A run that produces one enormous weight does so at a specific point in the stream, and rerunning with the same seed reproduces the same giant weight exactly, so the estimator is not noisy in the way a debugging session expects. Changing the seed moves the giant weight to a different draw, and the estimate jumps by more than the error bar. This seed-dependence is the practical signature of a proposal with heavy weight tails, and it is reproduced rather than diagnosed by any analysis that keeps the seed fixed.

Choosing a proposal is therefore a tail decision before it is a location decision. The mean and variance of the proposal set where the draws land; the tail weight of the proposal, relative to the target, sets whether the weights are bounded and whether the estimator has finite variance at all. An estimator with infinite variance converges, in the sense that the sample mean tends to the target mean, but its fluctuations are governed by a stable law with a tail index below 2, and neither the standard error nor the effective sample size is a meaningful summary of it.

Self-normalization and its bias

The normalized estimator divides by $\sum_i w_i$, which is random, so $\hat\mu$ is a ratio of two dependent random quantities. Its bias is of order $1/n$, and a delta-method expansion shows the leading bias term is proportional to the covariance of the weights with $h$ times the weight variance. The practical consequence is that the normalized estimator is biased low when the large weights are associated with small values of $h$, and biased high in the opposite case, with the bias shrinking like $1/n$ and therefore swamped by the standard error only when $n_{\text{eff}}$ is comfortably large.

For the unnormalized estimator the weights are required to have expectation exactly 1 under $g$, and a proposal whose normalization constant is wrong by a factor of $c$ scales every weight by $c$ and the estimate by $c$. The normalized form is immune to this particular error, which is one reason it is preferred in practice despite the bias. A code that normalizes is silently correct under a wrong $g$ constant; a code that does not is silently wrong.

Resampling closes the loop in particle methods. Given a weighted sample, resampling draws $n$ new indices with probability proportional to the weights and returns the corresponding $X_i$ with equal weights. The resampled set has an effective sample size of its own, smaller than $n$, and the resampling step is where the weight variance is converted into actual sample depletion. A filter that resamples too often wastes information by discarding diversity; one that resamples too rarely carries a handful of enormous weights that make every subsequent estimate collapse toward a single particle. The two failure modes are the same number, $n_{\text{eff}}$, read from opposite ends.

The interaction with the rest of a simulation is direct. The square-root convergence applies to the reweighted estimator with the effective sample size in place of the raw count, so a proposal with $n_{\text{eff}} = 50$ out of $10^4$ draws has the error of a 50-draw run. Rejection sampling avoids the weights entirely at the price of discarding draws, as described in the envelope analysis; the two methods sit at the two ends of a trade between throwing work away and carrying a weight.