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. 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 the set is renormalized. A theorem of Doucet and colleagues makes precise why this always ends badly: the variance of the importance weights can only grow with time, with no steady state where they stay balanced. The mechanism compounds rather than accumulates: the proposal distribution (almost always just the process model) never looks at the new measurement, so each likelihood factor carries genuine variance, and multiplying many such factors behaves like compounding interest, particles with a lucky run of high factors pull ahead multiplicatively, not additively. That is also why degeneracy bites hardest exactly where sensory AI needs particle filters most: high-dimensional states (a multi-joint pose, a full SLAM map) let the proposal drift further from the posterior with every added dimension, and precise sensors sharpen the likelihood enough that only a few particles land near it at all. 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 discussed in Chapter 9 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 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 concentrates where the posterior mass actually is. The catch is that cloning creates duplicates, several new particles sit at identical states, so the cloud's diversity drops. This is sample impoverishment, and it is most dangerous when process noise is small, because 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 picks, for each, the particle whose cumulative weight interval it lands in. It is unbiased but injects the most Monte Carlo variance of any scheme; three better methods cut 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, drawing a single uniform \(u \sim \mathcal{U}[0, 1/N)\) and placing the \(N\) sample points on the regular grid \(u + i/N\); it is \(O(N)\), simplest to code, and has the lowest variance in practice, the default in most libraries.
• Residual resampling deterministically keeps \(\lfloor N w^{(i)} \rfloor\) copies of each particle, then draws the remainder multinomially, 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

Resampling fires only when the health gauge crosses a threshold, a ratio of \(0.5\) (half the particles effectively dead) 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, with the noise scale 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 for robustness against collapse, 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 for a specific reason, since impoverishment then comes faster. Which scheme: systematic by default for its low variance and \(O(N)\) cost, residual to squeeze variance further, multinomial only 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 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.