Resampling and degeneracy

"A thousand particles set out to represent the posterior. By step fifty, nine hundred and ninety-nine were carrying weight zero and one was doing all the work. That one was very tired."

An Overworked AI Agent

This section assumes the particle-filter mechanics and importance weights of Section 10.3, plus comfort with sampling, variance, and the categorical distribution from the Chapter 4 primer. Nothing else is needed. We keep the notation of the chapter: a set of \(N\) particles \(\{\mathbf{x}_k^{(i)}\}\) with normalized weights \(\{w_k^{(i)}\}\) summing to one approximates the filtering posterior \(p(\mathbf{x}_k \mid \mathbf{z}_{1:k})\).

Why the weights collapse: the degeneracy problem

What happens. In sequential importance sampling, each new measurement multiplies every particle's weight by a likelihood factor and then the whole set is renormalized. Multiplying many random factors and renormalizing is exactly the recipe for one factor to dominate. A theorem of Doucet and colleagues makes it precise: the variance of the importance weights can only grow with time. There is no steady state where the weights stay balanced. Given enough steps, the normalized weight of a single particle converges to one and all others to zero.

Why it matters. A degenerate filter still produces a number, so like the mistuned Kalman filter of Section 9.4 it fails silently. Every particle except one contributes nothing to the posterior estimate, yet you still pay the full compute cost of propagating all \(N\) of them through the dynamics and the likelihood at every step. Worse, the surviving particle almost never sits at the true state, so the estimate is both expensive and wrong, and its reported spread collapses to a point that lies to you about your own uncertainty. That miscalibration is the same failure the book returns to in Chapter 18.

Measuring the damage: effective sample size

You cannot fix what you cannot detect, and the detector is the effective sample size (ESS), a single scalar that estimates how many of your \(N\) particles are actually pulling their weight. The standard approximation is

How to read it. When all weights are equal, \(w^{(i)} = 1/N\), the sum of squares is \(1/N\) and \(\widehat{N}_{\text{eff}} = N\): every particle counts. When one weight is one and the rest are zero, the sum of squares is one and \(\widehat{N}_{\text{eff}} = 1\): the filter has degenerated to a single sample. The ratio \(\widehat{N}_{\text{eff}}/N\) is therefore a health gauge running from 1 (perfect) toward \(1/N\) (dead). It is cheap, it needs no ground truth, and it is the trigger every practical particle filter watches.

The fix: resampling as survival of the fittest

What it does. Resampling replaces the weighted particle set with a new set of \(N\) equally weighted particles, drawn with replacement so that the expected number of copies of particle \(i\) is proportional to its weight \(N w^{(i)}\). High-weight particles get cloned several times; low-weight particles vanish. After resampling, all weights reset to \(1/N\), and the cloud is concentrated where the posterior mass actually is. The catch is that cloning creates duplicates: several new particles sit at identical states. The diversity of the cloud drops, and this is sample impoverishment. It is most dangerous when process noise is small, because then the dynamics barely separate the duplicates on the next step and the filter can collapse onto a single trajectory even though its weights look healthy.

How to draw the copies. The naive method, multinomial resampling, draws \(N\) independent uniforms and, for each, picks the particle whose cumulative weight interval it lands in. It is unbiased but adds the most Monte Carlo variance of any scheme. Three better methods reduce that variance by making the draws less independent:

• Stratified resampling partitions \([0,1)\) into \(N\) equal strata and draws one uniform inside each, guaranteeing coverage across the whole weight range.
• Systematic resampling goes further: it draws a single uniform \(u \sim \mathcal{U}[0, 1/N)\) and places the \(N\) sample points on the regular grid \(u + i/N\). It is \(O(N)\), the simplest to code, and has the lowest variance in practice, which is why it is the default in most libraries.
• Residual resampling deterministically keeps \(\lfloor N w^{(i)} \rfloor\) copies of each particle, then draws the remainder multinomially, cutting variance by handling the integer part exactly.

All four are unbiased in expectation; they differ only in the variance they inject. For sensor filters running at hundreds of hertz, systematic resampling is almost always the right default.

import numpy as np

def effective_sample_size(w):
    """Estimated number of 'active' particles from normalized weights w."""
    return 1.0 / np.sum(w**2)

def systematic_resample(w, rng):
    """Return indices of resampled particles. O(N), low variance."""
    N = len(w)
    positions = (rng.random() + np.arange(N)) / N     # one jitter, regular grid
    cumulative = np.cumsum(w)
    cumulative[-1] = 1.0                               # guard against round-off
    return np.searchsorted(cumulative, positions)

def maybe_resample(particles, w, rng, thresh_ratio=0.5):
    """Adaptive resampling: only when ESS drops below thresh_ratio * N."""
    N = len(w)
    if effective_sample_size(w) < thresh_ratio * N:
        idx = systematic_resample(w, rng)
        return particles[idx], np.full(N, 1.0 / N), True
    return particles, w, False                         # weights carried forward

The code above shows the discipline in full. The ESS is computed every step; resampling fires only when the health gauge crosses a threshold (a ratio of \(0.5\), meaning half the particles have effectively died, is the common choice). Between triggers the weights simply accumulate, so a filter watching a well-modelled, slowly changing state may go many steps without resampling at all, preserving diversity for free.

Keeping diversity alive: roughening and regularization

Adaptive resampling reduces how often you impoverish the cloud, but when process noise is genuinely tiny the duplicates still pile up. Two standard remedies inject diversity back. Roughening (also called jitter) adds a small zero-mean noise to each resampled particle, spreading the clones apart; the noise scale is typically tied to the inter-particle spacing so it shrinks as the cloud converges. The regularized particle filter makes this principled: instead of resampling from the discrete set, it resamples from a continuous kernel-density estimate built on the particles, so every child is a fresh, distinct sample. Both cost a little bias in exchange for robustness against collapse, and both are worth reaching for whenever a low-noise system keeps degenerating despite adaptive resampling. A different route, deferring diversity loss by analytically marginalizing part of the state, is the subject of Section 10.5.

from filterpy.monte_carlo import systematic_resample
from filterpy.monte_carlo import neff        # effective sample size

if neff(weights) < N / 2:                     # ESS below half the particles
    idx = systematic_resample(weights)       # validated, O(N)
    particles[:] = particles[idx]
    weights.fill(1.0 / N)                     # reset to uniform

When each choice is right

When to resample: almost always adaptively, on an ESS threshold near \(N/2\). Resample every step only if you have a specific reason, and expect faster impoverishment if you do. Which scheme: systematic by default for its low variance and \(O(N)\) cost; residual when you want to squeeze variance further; multinomial essentially never, except as a textbook baseline. When to add roughening or a regularized filter: when process noise is small enough that resampled duplicates do not naturally separate, the tell being an ESS that looks healthy while the distinct-particle count quietly collapses. These knobs, together with the proposal design of Section 10.3, are the whole tuning surface of a particle filter, and they recur wherever these filters power real systems, from the localization of Chapter 25 to the SLAM back ends of Chapter 52.

What's Next

In Section 10.5, we attack degeneracy from the other end. Instead of curing a collapsed cloud after the fact, Rao-Blackwellization shrinks the space the particles have to cover in the first place: it samples only the states that truly need it and solves the rest analytically with a Kalman filter riding on each particle. Fewer sampled dimensions means slower weight variance growth, so the same particle budget buys a far healthier filter.