Nonparametric Filters

Histograms, importance sampling, particle filters, and the art of resampling — how a belief stops being a formula and becomes a population.

The problem with one ellipse

Rusty is in the Hallway. Three identical doors, one binary door detector, no idea where it started. The detector fires.

The true posterior is trimodal: three peaks of equal mass, and a lot of nearly-zero corridor between them. Hand that posterior to a Gaussian filter and it must answer with a mean and a covariance. Moment-match it honestly and the mean lands at the centroid of three separated hypotheses — a location the evidence never argued for, and one the robot is at most a third likely to be near — while the covariance inflates until it spans the corridor, reporting an uncertainty that is technically correct and operationally useless. Let the filter track a single mode instead, as an EKF started near one door will, and it becomes confidently wrong two times out of three with nothing in its state to record that a choice was ever made.

This is not a tuning problem. A Gaussian has one mode; the posterior has three; the mismatch is structural. So represent the belief with something that can hold three answers at once.

Watch a few full cycles before reading on. Three things are happening, and each is a section of this chapter.

The cloud is a distribution, not a list of guesses. The dashed purple line is the weighted mean, and during the multimodal phase it wanders across the corridor tracking the centroid of the surviving hypotheses rather than any one of them. That is not a bug in the readout — it is the correct expectation of a genuinely multimodal belief, and it is exactly the number a Gaussian filter would have been forced to report. The particles are the answer; the mean is a lossy summary of them, and in this corridor it is the worst summary available.

Weighting and resampling are different operations, and only one of them destroys anything. During the green phase nothing moves: the ticks change size because their weights changed. During the purple phase nothing changes size: the ticks move, because low-weight hypotheses were deleted and high-weight ones were cloned. Weighting is reversible bookkeeping. Resampling is selection, and selection is irreversible.

Diversity is a finite resource. Press Deprivation preset — 30 particles, a razor-sharp sensor — and re-roll the seed a few times. In a sizeable fraction of runs every particle near Rusty dies in one unlucky weighting, and from then on the filter converges tightly and confidently onto the wrong door and never recovers. It cannot recover: resampling only ever redistributes hypotheses that already exist, and the motion noise is far too small to walk one back.

Building intuition

Both representations in this chapter answer the same question — how do you write down a distribution you cannot write down? — and they answer it in opposite ways.

The histogram filter partitions the state space in advance and stores the probability mass of each region. It commits to a resolution before seeing any data. Everything the belief could ever want to say must be expressible as "this much mass in this box", so a fine grid can say a lot and costs a lot. Nothing is adaptive; the same arithmetic runs whether the robot is lost or perfectly localized.

The particle filter stores nothing in advance. It carries $M$ hypotheses, each a complete state vector, each with a weight, and the hypotheses themselves move — they follow the mass rather than waiting for it. Resolution is not a parameter; it is wherever the particles happen to be. That is the whole trade: the grid pays for the region it might need, the particle set pays for the region it currently believes in.

The particle filter's rhythm has three beats, and it is worth naming them before formalizing them.

Thrun's metaphor for the third beat is a roulette wheel whose arcs are the weights, spun $M$ times. It is the right picture and the wrong algorithm, and the next few pages are about why.

The mathematics

Notation this chapter adds

Chopping the space

Start with the easy half. If the state space is finite — the robot is in one of $K$ rooms, the door is open or closed — then Chapter 5's integral is a sum, and the Bayes filter is implementable exactly as written, with no approximation of any kind.

This is Thrun's Table 4.1, and it is the same two lines as the Bayes filter with $\int$ replaced by $\sum$. Line 2 is $O(K^2)$ because in principle every cell can reach every other; in practice a robot moving a bounded distance per step has a banded kernel — only $W$ neighbours are reachable — and the cost drops to $O(K \cdot W)$. Line 3 is $O(K)$ always.

The interesting case is a continuous state space chopped into cells, which is where the word "histogram filter" applies and where approximation finally enters.

The ladder is where the curse of dimensionality stops being a slogan. A 1-D corridor at 2 cm resolution is 500 cells and a rounding error of a computation. The same resolution over $(x, y, \theta)$ — the state that Chapter 12 actually needs — is $500^3 \approx 1.3 \times 10^8$ cells, and the naive prediction sum over ordered pairs of cells is $10^{16}$ operations per step. Banding rescues the exponent on the pair count but not on the cell count itself: you still have to store, touch, and normalize $r^d$ numbers. Grids survive in robotics exactly where $d \le 2$ and the map is static — which is to say, in Chapter 13, and essentially nowhere else.

The binary Bayes filter, and why it deserves its own box

Before leaving grids, one special case earns disproportionate attention: a state that is binary and static. Is this cell occupied? Is that door open? The state does not change, so there is no prediction step at all — the filter is pure evidence accumulation.

Write the belief in log odds:

Log odds run from $-\infty$ to $+\infty$, which means no amount of confidence can numerically round to exactly 0 or 1 — the truncation problem that kills naive product-of-probabilities updates.

Two features of that line are worth staring at. First, the update is an addition — the entire filter is +=. Second, the measurement enters through the inverse model $p(x \mid z_t)$, not the familiar forward model $p(z_t \mid x)$. That inversion is not laziness: when the state is one bit and the measurement is a 1080p image or a 1080-beam scan, it is far easier to write down "how likely is occupancy given this reading" than to describe the distribution over all readings that a wall produces.

Importance sampling, from first principles

Now the other branch. We want samples from the posterior $f$. We cannot draw them, because we cannot even evaluate $f$ without the normalizer. What we can do is draw from something else.

Let $g$ be any density we can sample, with the single condition that it covers $f$'s support: $f(x) > 0 \Rightarrow g(x) > 0$. Then for any statistic $\phi$,

Multiply and divide by $g$; recognize an expectation under $g$. That is the entire idea, and it is worth appreciating how much it buys: you may sample from the wrong distribution on purpose, provided you carry a weight that records how wrong it was.

The particle filter targets the posterior

Now specialize. Take the target to be the posterior over the whole trajectory, $\bel(x_{0:t}) = p(x_{0:t} \mid z_{1:t}, u_{1:t})$ — not because we want trajectories, but because in that space the algebra has no integrals in it.

That is Thrun's Table 4.3, unchanged since 1999, and it is still the core of the localizer that ships as the ROS 2 navigation default in 2026. What has changed is lines 7–10, which modern implementations do not run every step and do not run this way.

Resampling, and the variance nobody mentions

Lines 8–9 as written are multinomial resampling: $M$ independent draws from the categorical distribution defined by the weights. Thrun's roulette wheel, spun $M$ times.

It is unbiased. It is also needlessly noisy, and the noise is not free — it is added directly to the estimator the filter is trying to compute.

Degeneracy, deprivation, and when not to resample

Two failure modes wear similar names and have opposite cures.

Weight degeneracy is what happens if you never resample. The weights are products of likelihoods, and a product of many terms concentrates: after a few dozen steps one particle holds essentially all the mass, $M_{\mathrm{eff}} \to 1$, and the other $M-1$ particles are consuming CPU to represent nothing. The cure is to resample.

Particle deprivation is what happens if you resample too much. Every resample deletes hypotheses, and only the motion model's noise creates new ones. Thrun's thought experiment makes it vivid: a robot that is not moving and has no sensors. The state transition is deterministic, so no new states are ever introduced; the resampling step is pure random deletion. With probability one, the population collapses to $M$ identical copies of a single state — and to an outside observer the robot appears to have determined its position exactly, despite having no sensors at all. The cure is to resample less.

The standard reconciliation is to make resampling conditional on the diagnostic we already derived:

with the weights carried multiplicatively across steps when no resample happens ($w_t^{[i]} = p(z_t \mid x_t^{[i]})\, w_{t-1}^{[i]}$, resetting to $1/M$ when one does). The threshold $M/2$ is a convention, not a theorem; Exercise 7 sweeps it and reports where the optimum actually sits for the Hallway.

Three further defences, in increasing order of honesty:

1. Use the low-variance sampler. Free, and it removes the single largest source of unnecessary deletion — the 37% figure above.
2. More particles. Effective, and expensive, and it treats the symptom: if the proposal is bad, more samples from it are still bad samples.
3. Inject fresh hypotheses when the evidence says you are lost. This is Augmented MCL, and Chapter 12 derives it properly, using the average measurement likelihood as the "am I lost?" detector.

KLD-adaptive sample size

There is a better answer than a fixed $M$, and it comes from asking what $M$ is for.

During global localization the belief covers the whole map and needs thousands of particles to represent it. Ten seconds later it is a 20 cm blob and thirty particles would do. A fixed $M$ must be sized for the worst case and then wastes 99% of its work for the rest of the run. Fox's KLD-sampling makes $M$ a function of the belief's spread, measured as the number of histogram bins the samples actually occupy.

At $\varepsilon = 0.05$ and $\delta = 0.01$ (so $z_{0.99} = 2.3263$), the bound reads:

In practice this is not called once per step but inside the resampling loop: draw a particle, check whether it landed in a bin nothing has landed in yet, and if so recompute the bound. Stop as soon as the number drawn meets it. The loop discovers how many particles it needs while it is filling the set. Toggle KLD-adaptive M in the arena at the top of this chapter and watch the population fall from the ceiling to a few dozen as the three clouds become one.

A worked example you can check by hand

Five particles, weights already normalized:

Effective sample size. $\sum_i w_i^2 = 0.01 + 0.09 + 0.0025 + 0.16 + 0.0225 = 0.285$, so

That is above the $M/2 = 2.5$ threshold, so a well-behaved filter would not resample here. We will do it anyway, to have something to check.

The comb. Take $r = 0.15$, which is a legal draw from $U[0,\, 1/5)$. The pointers are $u_m = r + (m-1)/5 = 0.15,\, 0.35,\, 0.55,\, 0.75,\, 0.95$, and we walk them against the cumulative weights:

Offspring counts $(0, 2, 0, 2, 1)$. Particles 1 and 3 die; nobody is drawn more than $\lceil M w_i \rceil$ times; the total is 5, as it must be. Notice particle 4: $M w_4 = 2$ exactly, and it gets exactly 2 offspring for every legal value of $r$ — the comb is deterministic wherever the expectation is a whole number.

The variance gap. Multinomial gives $\Var[N_i] = M w_i(1-w_i)$; the comb gives $f_i(1-f_i)$ with $f_i = M w_i - \lfloor M w_i \rfloor$:

Same expectation, one quarter the variance. Set the wheel widget above back to its defaults, press Spin ×1000, and the measured bars converge on exactly these two columns.

Implementation in Rust

The library is crates/ch08_particles. It depends on bayes_core (the BayesFilter trait from Chapter 5) and sim (the Hallway from Chapter 4), and it is consumed later by localize (Ch. 12), ch13_occgrid, and ch17_fastslam. Two design decisions drive the whole module.

Weights live in log space. A likelihood is a product over beams; in a 360-beam scan that product underflows f64 long before it becomes uninteresting. Every weight in this crate is a log weight, normalized by log-sum-exp, and exponentiated only at the boundary where a resampler needs actual probabilities.

The proposal and the likelihood are traits, not functions. Chapter 9's motion samplers and Chapter 10's sensor models plug into these two slots unchanged, which is what makes Chapter 12's MCL a fifty-line file rather than a rewrite.

use rand::rngs::SmallRng;

/// A weighted particle set. Weights are **log** weights, always.
///
/// `S` is deliberately unconstrained: the Hallway filter instantiates it with
/// `f64`, Chapter 12 with `Se2`, Chapter 17 with a pose *and* a map. Nothing in
/// this file cares.
pub struct ParticleSet<S> {
    pub states: Vec<S>,
    pub log_w: Vec<f64>,
}

impl<S> ParticleSet<S> {
    /// A fresh set with uniform weights: log(1/M) each.
    pub fn uniform(states: Vec<S>) -> Self {
        let m = states.len();
        Self { log_w: vec![-(m as f64).ln(); m], states }
    }

    pub fn len(&self) -> usize {
        self.states.len()
    }

    /// Subtract the log-sum-exp so the weights sum to one in probability space.
    ///
    /// Shifting by the maximum first is the whole trick: it makes the largest
    /// exponential exactly 1, so nothing overflows and the smallest terms
    /// underflow to 0 harmlessly instead of poisoning the sum with NaN.
    pub fn normalize(&mut self) {
        let max = self.log_w.iter().copied().fold(f64::NEG_INFINITY, f64::max);
        if !max.is_finite() {
            // Every particle is impossible. Refuse to invent information:
            // fall back to ignorance rather than propagate NaN.
            let uniform = -(self.len() as f64).ln();
            self.log_w.iter_mut().for_each(|l| *l = uniform);
            return;
        }
        let log_z = max + self.log_w.iter().map(|l| (l - max).exp()).sum::<f64>().ln();
        self.log_w.iter_mut().for_each(|l| *l -= log_z);
    }

    /// Weights in probability space. Assumes `normalize` has been called.
    pub fn weights(&self) -> Vec<f64> {
        self.log_w.iter().map(|l| l.exp()).collect()
    }

    /// M_eff = 1 / Σ wᵢ².  M when uniform, 1 when one particle owns everything.
    pub fn ess(&self) -> f64 {
        let s: f64 = self.log_w.iter().map(|l| (2.0 * l).exp()).sum();
        if s > 0.0 { 1.0 / s } else { 0.0 }
    }
}

/// The proposal slot. Chapter 9's `sample_motion_model_odometry` implements it.
pub trait Proposal<S> {
    type Control;
    fn sample(&self, x: &S, u: &Self::Control, rng: &mut SmallRng) -> S;
}

/// The likelihood slot. Chapter 10's beam and likelihood-field models implement it.
pub trait Likelihood<S> {
    type Measurement;
    /// Log p(z | x). Log, because a 360-beam product is not representable otherwise.
    fn log_lik(&self, z: &Self::Measurement, x: &S) -> f64;
}

/// The occupancy seed: one static binary cell, in log odds. Chapter 13 tiles this.
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct LogOdds(pub f64);

impl LogOdds {
    /// ℓ = log(p / (1 − p)); ℓ = 0 is "no idea", which is p = 0.5.
    pub fn from_prob(p: f64) -> Self {
        LogOdds((p / (1.0 - p)).ln())
    }

    pub fn prob(self) -> f64 {
        1.0 - 1.0 / (1.0 + self.0.exp())
    }

    /// `binary_Bayes_filter` — Thrun et al., Table 4.2.
    ///
    /// `inverse_model` is p(x | z), *not* p(z | x): with a one-bit state and a
    /// megapixel measurement, the inverse is the only one anyone can write down.
    /// Subtracting the prior is what stops repeated readings from double-counting it.
    pub fn update(&mut self, inverse_model: f64, prior: LogOdds) {
        self.0 += (inverse_model / (1.0 - inverse_model)).ln() - prior.0;
    }

    /// The guard Chapter 13 inherits: bound how certain a cell may become, so
    /// that a world which changes can still change the robot's mind.
    pub fn clamp_to(&mut self, bound: f64) {
        self.0 = self.0.clamp(-bound, bound);
    }
}

The resampler is the fifteen-line listing the chapter has been building toward, and it is a direct transcription of Table 4.4.

use rand::{Rng, rngs::SmallRng};

/// `Low_variance_sampler(𝒳ₜ, 𝒲ₜ)` — Thrun et al., Table 4.4.
///
/// One random number and one monotone sweep. Two consequences make this the
/// default everywhere: any particle with wᵢ ≥ 1/M is guaranteed at least one
/// offspring, and the pass is O(M) with a purely sequential access pattern
/// instead of O(M log M) with a binary search per draw.
pub fn low_variance_resample<S: Clone>(
    states: &[S],
    weights: &[f64],
    rng: &mut SmallRng,
) -> Vec<S> {
    let m = states.len();
    let step = 1.0 / m as f64;
    let r: f64 = rng.random_range(0.0..step); // the *only* randomness in here
    let mut out = Vec::with_capacity(m);
    let mut c = weights[0];
    let mut i = 0usize;
    for k in 0..m {
        let u = r + k as f64 * step;
        // The comb tooth walks forward; `i` never goes back, which is why the
        // whole sweep is linear rather than M independent searches.
        while u > c && i + 1 < m {
            i += 1;
            c += weights[i];
        }
        out.push(states[i].clone());
    }
    out
}

/// The same sweep, reporting offspring counts instead of particles.
///
/// This is what the chapter's worked example asserts on and what the in-page
/// wheel widget draws — the test and the figure share one implementation.
pub fn offspring_counts(weights: &[f64], r: f64) -> Vec<usize> {
    let m = weights.len();
    let step = 1.0 / m as f64;
    let mut counts = vec![0usize; m];
    let mut c = weights[0];
    let mut i = 0usize;
    for k in 0..m {
        let u = r + k as f64 * step;
        while u > c && i + 1 < m {
            i += 1;
            c += weights[i];
        }
        counts[i] += 1;
    }
    counts
}

/// Multinomial resampling — M independent draws. Kept for the comparison in
/// §"Resampling, and the variance nobody mentions", never used in anger.
pub fn multinomial_resample<S: Clone>(
    states: &[S],
    weights: &[f64],
    rng: &mut SmallRng,
) -> Vec<S> {
    let cdf: Vec<f64> = weights
        .iter()
        .scan(0.0, |acc, w| {
            *acc += w;
            Some(*acc)
        })
        .collect();
    (0..states.len())
        .map(|_| {
            let u: f64 = rng.random_range(0.0..*cdf.last().unwrap());
            let i = cdf.partition_point(|&c| c < u);
            states[i.min(states.len() - 1)].clone()
        })
        .collect()
}

The filter itself is then almost anticlimactic: propagate, add log-likelihoods, normalize, conditionally resample.

use bayes_core::BayesFilter;
use rand::{Rng, SeedableRng, rngs::SmallRng};
#[cfg(not(target_arch = "wasm32"))]
use rayon::prelude::*;

use crate::set::{Likelihood, ParticleSet, Proposal};
use crate::resample::low_variance_resample;

pub struct ParticleFilter<S, P: Proposal<S>, L: Likelihood<S>> {
    pub set: ParticleSet<S>,
    pub proposal: P,
    pub likelihood: L,
    /// Resample iff M_eff < threshold · M. 0.5 is the usual convention.
    pub resample_threshold: f64,
    pub rng: SmallRng,
}

impl<S, P, L> BayesFilter for ParticleFilter<S, P, L>
where
    S: Clone + Send + Sync,
    P: Proposal<S> + Sync,
    L: Likelihood<S> + Sync,
{
    type Belief = ParticleSet<S>;
    type Control = P::Control;
    type Measurement = L::Measurement;

    fn predict(&mut self, u: &Self::Control) {
        let Self { set, proposal, rng, .. } = self;
        // Reborrow immutably: a `&mut P` captured by a closure is a unique
        // borrow and would not be shareable across rayon's threads.
        let proposal: &P = proposal;
        // One seed per particle, drawn *serially* from the filter's generator.
        // This is what buys reproducibility under rayon: the seeds are a
        // function of the filter's seed alone, so thread scheduling cannot
        // change the result. `thread_rng()` here would silently destroy it.
        let seeds: Vec<u64> = (0..set.len()).map(|_| rng.random()).collect();

        #[cfg(not(target_arch = "wasm32"))]
        let states = set.states.par_iter_mut().zip(seeds.par_iter());
        #[cfg(target_arch = "wasm32")]
        let states = set.states.iter_mut().zip(seeds.iter());

        states.for_each(|(x, &seed)| {
            let mut r = SmallRng::seed_from_u64(seed);
            *x = proposal.sample(x, u, &mut r);
        });
    }

    fn correct(&mut self, z: &Self::Measurement) -> f64 {
        let Self { set, likelihood, .. } = self;
        // w ← w · p(z | x), in logs: the importance weight *is* the likelihood,
        // because the proposal was the motion model. See the derivation above.
        for (w, x) in set.log_w.iter_mut().zip(set.states.iter()) {
            *w += likelihood.log_lik(z, x);
        }
        // Before normalizing, the sum of weights is the evidence p(z | z₁:ₜ₋₁).
        // Chapter 12 uses a running average of it to notice it has been kidnapped.
        let evidence = set.log_w.iter().map(|l| l.exp()).sum::<f64>();
        set.normalize();

        if set.ess() < self.resample_threshold * set.len() as f64 {
            let w = set.weights();
            set.states = low_variance_resample(&set.states, &w, &mut self.rng);
            let uniform = -(set.len() as f64).ln();
            set.log_w.iter_mut().for_each(|l| *l = uniform);
        }
        evidence
    }

    fn belief(&self) -> &ParticleSet<S> {
        &self.set
    }
}

Finally, the KLD bound and the tests that pin the chapter's worked example.

use statrs::distribution::{ContinuousCDF, Normal};

/// `KLD_sample_size(k, ε, δ)` — Fox (2003), eq. 7.
///
/// `k_bins` counts the bins the particles *occupy*, not the bins in the grid.
/// An empty bin costs nothing, which is precisely why this number collapses as
/// the belief condenses.
///
/// This returns the raw bound. Clamping it to `[M_min, M_max]` is the caller's
/// job — the draw loop in `filter.rs` owns those limits because they are a
/// budget, not a statistical claim.
pub fn kld_sample_size(k_bins: usize, epsilon: f64, delta: f64) -> usize {
    if k_bins <= 1 {
        return 0;
    }
    let z = Normal::standard().inverse_cdf(1.0 - delta);
    let k1 = (k_bins - 1) as f64;
    let a = 2.0 / (9.0 * k1);
    let inner = 1.0 - a + a.sqrt() * z;
    ((k1 / (2.0 * epsilon)) * inner.powi(3)).ceil() as usize
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::resample::offspring_counts;
    use approx::assert_relative_eq;
    use rand::{Rng, SeedableRng, rngs::SmallRng};

    /// The chapter's worked example, exactly: r = 0.15 on the five weights.
    #[test]
    fn worked_example_offspring_counts() {
        let w = [0.10, 0.30, 0.05, 0.40, 0.15];
        assert_eq!(offspring_counts(&w, 0.15), vec![0, 2, 0, 2, 1]);
    }

    #[test]
    fn worked_example_effective_sample_size() {
        let w = [0.10, 0.30, 0.05, 0.40, 0.15];
        let ess = 1.0 / w.iter().map(|x| x * x).sum::<f64>();
        assert_relative_eq!(ess, 3.508_771_929_824_56, epsilon = 1e-9);
        assert!(ess > 5.0 / 2.0, "above M/2 — a sane filter would not resample here");
    }

    /// Unbiasedness is a claim about a mean, so test it as one — and tightness
    /// is a claim about every single draw, so test that per draw.
    #[test]
    fn comb_is_unbiased_and_within_one() {
        let w = [0.10, 0.30, 0.05, 0.40, 0.15];
        let expected: Vec<f64> = w.iter().map(|x| 5.0 * x).collect();
        let mut rng = SmallRng::seed_from_u64(8);
        let trials = 100_000;
        let mut sums = [0.0f64; 5];

        for _ in 0..trials {
            let r: f64 = rng.random_range(0.0..0.2);
            let counts = offspring_counts(&w, r);
            for i in 0..5 {
                // Never more than one away from M·wᵢ — the comb's whole point.
                assert!((counts[i] as f64 - expected[i]).abs() < 1.0);
                sums[i] += counts[i] as f64;
            }
        }

        for i in 0..5 {
            assert_relative_eq!(sums[i] / trials as f64, expected[i], epsilon = 0.02);
        }
    }

    /// Three rows of the table printed in the KLD section.
    #[test]
    fn kld_sample_size_matches_the_chapter_table() {
        assert_eq!(kld_sample_size(3, 0.05, 0.01), 93);
        assert_eq!(kld_sample_size(10, 0.05, 0.01), 217);
        assert_eq!(kld_sample_size(100, 0.05, 0.01), 1347);
    }
}

Putting it together: the Hallway duel

The crate ships one example that settles the chapter's argument empirically:

$ cargo run --release --example hallway_duel -p ch08_particles

seed 8 · hallway 10.0 m · 3 doors · sensor p(hit) = 0.90 · motion σ = 0.14 m

 t   histogram(K=128)      particles(M=1000)     M_eff    resampled
 1   modes=3  MAP=2.02     modes=3  MAP=1.98     612.4    no
 2   modes=3  MAP=4.51     modes=3  MAP=4.55     318.7    yes
 …
12   modes=1  MAP=7.48     modes=1  MAP=7.51      41.2    yes
     |MAP − truth| = 0.04 m                0.01 m

 predict cost/step:  16 384 mul-add        1 000 motion samples
 weights/step:          128 evals            1 000 evals
 wall clock/step:      0.31 ms              0.12 ms  (8 threads)
                                            0.74 ms  (wasm32, 1 thread)

deprivation sweep, M = 50, 10 seeds: 3 / 10 runs converged to the wrong door
                   M = 200, 10 seeds: 0 / 10

Three things in that output are worth more than the rest of this chapter's prose.

Both filters agree. The histogram filter is the reference — its only approximation is the grid — and the particle filter tracks it to within a cell. That agreement is not decoration; it is how you know a stochastic implementation is correct.

The particle filter is cheaper and gets cheaper faster. 1,000 particles beat 128 cells in a one-dimensional problem, and the gap becomes absurd in three. The histogram's cost is fixed by the grid whether the robot is lost or not; the particle filter's is fixed by $M$, and KLD sampling drops $M$ by an order of magnitude the moment the belief collapses to a single mode.

The failure rate is not zero and the honest number is printed. At $M = 50$, three runs in ten converge to the wrong door and stay there. This is particle deprivation, measured. It is the same phenomenon the arena's preset dramatizes, and the reason Chapter 12 adds recovery particles rather than trusting the filter to notice on its own.

Where this goes next: Chapter 12 turns this machinery into Monte Carlo localization by plugging in Chapter 9's samplers and Chapter 10's likelihood fields; Chapter 13 tiles the log-odds box across a map; Chapter 17 shows that a particle can carry a map as well as a pose if you Rao-Blackwellize the rest; Chapter 22 plans directly over particle beliefs; and Chapter 23 runs importance sampling over control sequences instead of states, which is the same derivation with the arrows turned around.

Exercises

1. Foundation exerciseFDifficulty 2 of 3The effective sample size, derived

   Starting from $M_{\mathrm{eff}} = M / (1 + \Var_g[\tilde w])$ with $\tilde w$ the weights scaled to mean one, show that for normalized weights summing to one, $M_{\mathrm{eff}} = 1/\sum_i (w^{[i]})^2$. Then verify the two extremes analytically: it equals $M$ exactly when all weights are $1/M$, and equals 1 exactly when one particle holds all the mass. Finally compute it for the chapter's five weights and confirm the value 3.5088.

2. Foundation exerciseFDifficulty 3 of 3Both schemes are unbiased; only one is tight

   Prove that $\E[N_i] = M w_i$ for both multinomial and comb resampling. Then prove that the comb's offspring count is always $\lfloor M w_i \rfloor$ or $\lceil M w_i \rceil$, and use that to derive $\Var[N_i] = f_i(1-f_i)$ where $f_i$ is the fractional part of $M w_i$. Compare with the multinomial's $M w_i (1 - w_i)$, and state the condition under which the comb's variance is exactly zero. Which of the two facts — same mean, smaller variance — is the reason the comb is preferred?

3. Foundation exerciseFDifficulty 2 of 3Order does not matter, until it does

   Telescope the log-odds recursion to show that $\ell_t$ depends on the multiset of measurements but not on their order. Now suppose the binary state can flip with probability $q$ per step (a door someone opens). Write the prediction step for that case, show that it is not additive in log odds, and explain in one sentence why this is the assumption Chapter 13 makes when it declares the map static — and what it costs when a person walks through the room.

4. Conceptual exerciseCDifficulty 1 of 3Predict, then spin

   In w8.2, press Degenerate to set the weights to $(0.96, 0.01, 0.01, 0.01, 0.01)$ with $M = 5$. Before pressing Spin ×1000, predict both offspring histograms. Specifically: under each scheme, what is the probability that particle 1 receives fewer than four offspring, and can particle 1 ever receive zero? Then run it and check. (Hint for the comb: what is $M w_1$, and what does Exercise 2 say about offspring counts when that number is not an integer?)

5. Conceptual exerciseCDifficulty 2 of 3Find the deprivation cliff

   In w8.1, load the deprivation preset and bisect on the $M$ slider to find the smallest particle count for which fewer than 2 of 20 re-rolled seeds converge to the wrong door. Now switch on KLD mode and read the steady-state population once the belief has a single mode. The two numbers will disagree — KLD's will be smaller. Explain why, in terms of what each number is protecting against. (One is sizing for representing a converged belief; the other is sizing for surviving the transient.)

6. Practical exercisePDifficulty 2 of 3Stratified resampling, and a variance ranking

   Implement stratified_resample — one uniform draw per comb interval, $u_m \sim U[(m-1)/M,\ m/M)$ — beside the two schemes in resample.rs. Derive its per-particle offspring variance, then measure all three over $10^5$ trials on the chapter's weights and rank them. Does the measured ranking match your derivation? Add the measurement as a test with a tolerance wide enough to be seed-stable but tight enough to fail if someone swaps the schemes.

7. Practical exercisePDifficulty 3 of 3When not to resample, measured

   Sweep resample_threshold from 0.0 (never resample) to 1.0 (resample every step) in steps of 0.1. For each value, run the Hallway filter at $M = 100$ across 50 seeds and record two numbers: the deprivation rate (fraction of runs whose final MAP is at the wrong door) and the mean $M_{\mathrm{eff}}$ over the run. Plot both against the threshold. You should find a U-shaped failure curve — degeneracy on the left, deprivation on the right — and the bottom of that U is the empirical version of the $M/2$ convention. Report where it actually lands for this problem.

References

1. Thrun, S., Burgard, W., and Fox, D. (2005) Probabilistic Robotics. MIT Press.link to Probabilistic Robotics (opens in a new tab)

   Chapter 4 is this chapter's spine: the discrete Bayes filter (Table 4.1), the binary static-state filter (Table 4.2), the particle filter (Table 4.3), and the low-variance sampler (Table 4.4). The derivations here follow its structure and extend it where post-2005 practice has moved on.

2. Gordon, N. J., Salmond, D. J., and Smith, A. F. M. (1993) Novel approach to nonlinear/non-Gaussian Bayesian state estimation. IEE Proceedings F (Radar and Signal Processing) 140(2), 107–113.doi:10.1049/ip-f-2.1993.0015 (opens in a new tab)

   The bootstrap filter — the first practical particle filter, and the paper that made resampling standard. Everything in this chapter's second half is a refinement of its five-line algorithm.

3. Fox, D. (2003) Adapting the Sample Size in Particle Filters Through KLD-Sampling. The International Journal of Robotics Research 22(12), 985–1003.doi:10.1177/0278364903022012001 (opens in a new tab)

   The source of the KLD bound and its Wilson–Hilferty derivation. Not in the 1999 draft this book uses as its baseline; it is 2005-edition material, rebuilt here from the original paper.

4. Li, T., Bolić, M., and Djurić, P. M. (2015) Resampling Methods for Particle Filtering: Classification, Implementation, and Strategies. IEEE Signal Processing Magazine 32(3), 70–86.doi:10.1109/MSP.2014.2330626 (opens in a new tab)

   The taxonomy that organizes multinomial, stratified, systematic and residual resampling into one family, with the variance comparisons Exercise 6 asks you to reproduce.

5. Chopin, N. and Papaspiliopoulos, O. (2020) An Introduction to Sequential Monte Carlo. Springer Series in Statistics.doi:10.1007/978-3-030-47845-2 (opens in a new tab)

   The rigorous modern treatment. Read it for the convergence results this chapter states informally, and for the proof that the self-normalized estimator's bias is O(1/M).

6. Elvira, V., Míguez, J., and Djurić, P. M. (2021) On the performance of particle filters with adaptive number of particles. Statistics and Computing 31.doi:10.1007/s11222-021-10056-0 (opens in a new tab)

   KLD-sampling's modern successor: adapt M from online predictive statistics rather than from bin occupancy, with error bounds that follow the adaptation. The right reference if you find KLD's bin size doing too much of the work.

7. Macenski, S., Moore, T., Lu, D. V., Merzlyakov, A., and Ferguson, M. (2023) From the desks of ROS maintainers: A survey of modern & capable mobile robotics algorithms in the robot operating system 2. Robotics and Autonomous Systems 168, 104493.doi:10.1016/j.robot.2023.104493 (opens in a new tab)

   Evidence for this chapter's claim that Table 4.3 still ships: AMCL — this particle filter with Chapter 9's and Chapter 10's models — remains the Nav2 default localizer. Written by the people who maintain it.

8. Chen, X. and Li, Y. (2025) An overview of differentiable particle filters for data-adaptive sequential Bayesian inference. Foundations of Data Science 7(4), 915–943.doi:10.3934/fods.2023014 (opens in a new tab)

   Where resampling goes when you need gradients through it: soft and optimal-transport resamplers that keep the filter differentiable. Chapter 25 picks this up.