Particle Filters: Non-Gaussian and Multimodal Beliefs
The particle filter is the only estimator that handles genuinely multimodal beliefs — and the kidnapped-robot problem is not a thought experiment, it happens when a person pushes the robot.
🎯 By the end you'll understand
How sequential importance resampling (SIR) propagates a belief through a nonlinear, non-Gaussian filter. Why importance weights work and how resampling collapses them back to uniform. The three practical resampling strategies — naive multinomial, systematic, and residual — and when each matters. How particle deprivation kills a converged filter and how recovery augmentation (random-particle injection) defends against it. When to use a particle filter versus an EKF or UKF, and the hard ceiling imposed by the curse of dimensionality. And the kidnapped-robot failure mode: after resampling collapses to one wrong mode, the filter cannot self-recover without injecting fresh particles.
KEY INSIGHTA particle filter is Bayes on a swarm of hypotheses
Every other filter in this stage picks a shape for the belief and fits parameters to it. The particle filter makes no shape assumption — it carries the belief itself, distributed across thousands of weighted samples.
The Kalman filter, the EKF, and the UKF all share one deep assumption: the posterior belief over the robot state is reasonably well described by a Gaussian. That assumption buys tractability — a mean and covariance are all you need to store — but it collapses the moment the belief becomes multimodal. Consider a robot placed in a symmetric corridor: it knows it is in one of two identical-looking sections, but cannot yet tell which. Its belief is bimodal. A Gaussian fit to that belief would place the mean halfway between the two modes — a place where the robot definitely is not. Only a filter that can carry two separate probability masses simultaneously can represent that belief correctly. The particle filter does exactly that, by replacing the parametric distribution with a set of weighted samples drawn from the state space.
The particle filter trades Gaussian tractability for representational generality. It can represent any posterior — bimodal, heavy-tailed, banana-shaped, discontinuous. The price is that it requires enough particles to cover the state space adequately, and that price compounds badly as the state dimension grows. Use the particle filter when the posterior genuinely cannot be approximated as a Gaussian, not as a default because it sounds more powerful.
HOW IT WORKSSequential importance resampling: the SIR algorithm
The particle filter maintains a belief bel(xt) as a set of M particles: {xt[1], …, xt[M]}, each a concrete hypothesis about the robot's state. At every timestep the filter performs three operations: predict, weight, resample.
Predict — propagate each particle through the motion model
For each particle xt-1[m], draw a new particle from the motion model: xt[m] ~ p(xt | ut, xt-1[m]). In practice this means: apply the odometry command ut to the particle and add noise sampled from the known odometry error model. For a differential-drive robot, the noise model is the standard two-wheel odometry model with parameters α1…α4 governing how rotation-noise and translation-noise scale with the commanded motion. Critically, this is a sample from the motion model — you do not need it to be Gaussian. Any distribution you can sample from works here.
Weight — score each particle against the measurement
After prediction, each particle is at a hypothetical position. Given the current sensor measurement zt, assign each particle an importance weight w[m] = p(zt | xt[m]). This is the observation likelihood: how probable is the measurement we actually received, if the robot were at this particle's location? For a LIDAR sensor with a known map, this means ray-casting from the particle's position and comparing predicted ranges to actual ranges. Particles near the true position generate predicted ranges close to the observed ranges and receive high weights. Particles in the wrong place generate inconsistent predictions and receive low weights.
After weighting, normalize: w̃[m] = w[m] / Σj w[j]. Now the weights sum to one and form a discrete probability distribution over the particles.
Resample — draw a new population proportional to weights
Draw M new particles from the current weighted set, each particle x[m] selected with probability proportional to w̃[m]. This step concentrates particles in high-probability regions: good particles get duplicated, poor particles get discarded. After resampling, all M new particles are treated as equally weighted (uniform weights). The filter then iterates: predict with the next odometry command, weight with the next measurement, resample. This is sequential importance resampling (SIR), and it is the foundation of every practical particle filter in robotics.
The name comes from Monte Carlo importance sampling theory. We want to compute expectations under a target distribution p(x) but we can only sample from a proposal distribution q(x). The correction factor — the ratio p/q — is the importance weight. In the particle filter, the proposal is the motion model (we draw particles by predicting forward), and the target is the posterior including the measurement. The measurement likelihood p(z | x) is the importance weight. After resampling, the resampled particles approximate draws from the posterior directly, so future propagation can again use the motion model as the proposal. The entire SIR cycle is one application of sequential importance sampling with resampling.
CORE CONCEPTImportance weights: what they mean and when they collapse
The importance weight w[m] encodes how well particle m explains the current measurement. A particle at the correct robot pose with a realistic map will generate ray-cast predictions that closely match the LIDAR scan; its likelihood is high. A particle 2 m away in an open corridor will cast rays that miss the walls the sensor actually sees; its likelihood is near zero.
Two numbers summarize the health of the weight distribution at any moment:
| Metric | Formula | Healthy value | What collapse looks like |
|---|---|---|---|
| Effective sample size (Neff) | 1 / Σ(w̃[m])² | ≥ M/2 (use at least half the particles) | Neff ≈ 1: one particle has weight ≈ 1, rest ≈ 0 |
| Weight variance | Var(w̃) | Low — weights roughly uniform after resampling | Spike: one weight dominates, rest degenerate |
Weight collapse — Neff approaching 1 — means the filter has effectively discarded all but one particle. If that surviving particle is at the correct pose, localization succeeds. If it is at the wrong pose, the filter has no mechanism to recover: every subsequent resample step will just duplicate that wrong particle, and the uncertainty representation collapses to a single incorrect hypothesis maintained with total confidence.
Unlike Kalman filter divergence, which manifests as a growing covariance that a NEES test can catch, particle filter weight collapse produces an answer that looks confident but is wrong. The estimated pose has low spread (all particles are near one location) but that location may be entirely incorrect. Monitor Neff at runtime and trigger recovery when it drops below a threshold — typically M/5 to M/2 depending on how dynamic the environment is.
CORE CONCEPTResampling strategies: multinomial, systematic, and residual
Resampling is sampling M particles from a discrete distribution defined by the weights. The naive approach — multinomial resampling — draws each new particle independently by sampling from the weight CDF. It is unbiased but introduces variance: some good particles may be drawn many times by chance, others not at all. Three strategies are commonly used:
| Strategy | Mechanism | Variance | Cost | Best for |
|---|---|---|---|---|
| Multinomial | Draw each of M particles independently from weight CDF | High (variance scales linearly with M — each draw is independent) | O(M log M) | Simple implementations; rarely best choice |
| Systematic | One random offset u ~ Uniform[0, 1/M]; M evenly-spaced pointers | Low (variance does not scale with M — one random draw governs all) | O(M) | Standard choice for mobile robot localization |
| Residual | Floor(M·w̃[m]) guaranteed draws, then resample remainder | Very low | O(M) | Very unequal weight distributions |
Systematic resampling is the practical default. The single random offset u is drawn once, then M pointers are placed at u/M, u/M + 1/M, u/M + 2/M, … The set of particles selected corresponds to walking the cumulative weight function with these evenly-spaced pointers. This eliminates the high-variance behavior of multinomial sampling: particles with weight close to 1/M are almost certain to receive exactly one copy, while particles with near-zero weight are almost certain to be discarded. The reduction in resampling variance directly translates to better filter stability with fewer particles.
Resampling introduces its own variance: it throws away the continuous particle cloud and replaces it with duplicates, losing information about the tails of the distribution. A common fix is adaptive resampling: only resample when Neff drops below a threshold (e.g., M/2). When the belief is already well concentrated and all weights are nearly equal, skip resampling for that step. This prevents the filter from collapsing its diversity unnecessarily during phases of accurate localization.
SEE ITParticle filter visualizer — convergence, collapse, and recovery
This 2D arena places FollowBot (the triangle) in a room with three circular landmarks. Adjust particle count and watch the filter converge. Then teleport the robot (kidnap it) to see the filter fail to recover — and toggle adaptive augmentation to see rescue by random-particle injection. The worst decision: using a small particle count and disabling augmentation after convergence.
The key lesson from this widget: a converged particle filter that has experienced particle deprivation (or a kidnapping) is indistinguishable from a correctly-converged filter from the outside — both return a confident pose estimate. Only monitoring Neff and the weight entropy gives you early warning before the behavior degrades.
WEAKNESSParticle deprivation and recovery augmentation
Particle deprivation is the failure mode that strikes precisely when the filter seems to be working well. After convergence, nearly all M particles cluster tightly around the correct pose. This is desirable — but it eliminates diversity. If the robot is subsequently kidnapped (physically moved to a new location without any motion command being issued — e.g., a person picks it up and moves it), the entire particle cloud is in the wrong place. The predict step will spread the cloud a little (by the motion noise model), but if no motion command was issued, it spreads it not at all. The weight step will then assign near-zero weight to every particle — because every particle is far from the actual observation likelihood peak — and the resampling step will simply duplicate the least-wrong wrong particle over and over.
In practice, kidnapping happens every time someone picks up the robot, every time the robot software is relaunched without moving the robot from where it last was, and every time a large localization error accumulates silently and then a corridor turn makes it suddenly visible. The particle filter's failure mode is catastrophic here because after weight collapse, there is literally no signal left to recover from — all particles are wrong, the resampling step selects the least-wrong wrong particle, and the filter locks into an incorrect belief with apparent confidence.
Recovery augmentation is the standard defense. At each filter cycle, with probability αslow or when Neff drops below a threshold, inject a fraction of new particles drawn uniformly from the entire state space (or from a prior over valid robot poses). These random particles serve as scouts: most will immediately receive near-zero weights and be discarded in the next resampling step, but if any of them land near the true pose, they will receive high weights and be preferentially duplicated. The filter can then gradually shift its probability mass to the new location over successive cycles.
The tuning tension is real: a high augmentation rate (α = 0.2) keeps the filter robust to kidnapping but permanently maintains a diffuse cloud that increases the pose estimate variance during normal operation. A low rate (α = 0.01) barely perturbs the convergence behavior but may take many cycles to recover from severe kidnapping. The practical recommendation for indoor mobile robots is α ~ 0.03–0.08 with adaptive triggering: run at low α normally, spike to 0.2–0.4 when Neff drops below M/10.
COMPARISONParticle filter vs. EKF vs. UKF: when to reach for each
Having covered the EKF (Lesson 4-5), UKF (Lesson 4-6), and now the particle filter, you need a clear decision framework. The choice is not primarily about implementation complexity — it is about the shape of the posterior and the dimension of the state space.
| Criterion | EKF | UKF | Particle Filter |
|---|---|---|---|
| Posterior shape assumption | Gaussian (required) | Gaussian (required) | None — arbitrary |
| Handles multimodal beliefs | No | No | Yes — by design |
| Nonlinear motion model | Jacobian required | No Jacobian needed | Just sample from it |
| Nonlinear observation model | Jacobian required | No Jacobian needed | Just evaluate likelihood |
| State dimension | Any (covariance O(n²)) | Low to medium (sigma pts = 2n+1) | Low only — curse of dimensionality |
| Computational cost | O(n³) per update | O(n³) per update | O(M · cost_per_particle) |
| Memory | O(n²) — covariance | O(n²) — covariance | O(M · n) — particle set |
| Kidnapping recovery | Cannot recover (no diversity) | Cannot recover (no diversity) | Yes — with augmentation |
| Global localization | Requires initialization | Requires initialization | Can initialize uniformly |
The curse of dimensionality is the hard ceiling on particle filters. To cover an n-dimensional state space with K samples per dimension requires Kn total particles. A 3D pose space (x, y, θ) with 10 samples per dimension needs only 10³ = 1,000 particles — tractable. A 6D state (x, y, θ, v, ω, a) needs 10⁶ = 1,000,000 — not tractable in real time. The EKF and UKF scale as O(n³) — still polynomial, not exponential. In practice, particle filters are used for 2D–4D state spaces. For FollowBot's 5D EKF state vector [x, y, θ, v, ω], the EKF is the right choice for normal localization. The particle filter is used specifically when the robot needs to localize globally (from an unknown initial position) or recover from kidnapping, after which the EKF takes over.
A common production architecture for indoor robots uses the particle filter (Monte Carlo Localization) for global localization and kidnapping recovery, and then hands off to the EKF for normal tracking once the particle filter has converged to a unimodal belief. The handoff criterion is: when the particle cloud's effective sample size exceeds 80% of M and the spread (the standard deviation of particle positions) drops below a threshold (e.g., 0.15 m), extract the weighted mean and covariance and initialize the EKF. This gives you global recovery capability with EKF efficiency during normal operation. Nav2's AMCL node implements a variant of this architecture.
FOLLOWBOTParticle filter in FollowBot's localization stack
FollowBot's Stage 4 milestone specifies: full EKF operational with state vector [x, y, θ, v, ω], fusing wheel odometry, IMU, and LIDAR scan-matching; filter consistency validated with NEES; position error below 0.1 m RMS in a known map. That milestone is achievable with the EKF alone — under the assumption that the robot is always initialized correctly and never kidnapped. In field deployment, that assumption fails regularly.
The recommended architecture for FollowBot adds a thin Monte Carlo Localization (MCL) shell around the EKF:
import rclpy from rclpy.node import Node import numpy as np from geometry_msgs.msg import PoseWithCovarianceStamped # Simplified MCL recovery node. # Full implementation uses robot_localization + AMCL from Nav2. class MCLRecovery(Node): def __init__(self): super().__init__('mcl_recovery') self.M = 500 # particle count self.alpha_aug = 0.05 # augmentation rate self.neff_thresh = self.M / 5 # trigger recovery below this # particles: [x, y, theta, weight] self.particles = self._init_uniform() self.weights = np.ones(self.M) / self.M self.create_subscription( PoseWithCovarianceStamped, '/ekf_pose', self._ekf_cb, 10 ) self.pub = self.create_publisher( PoseWithCovarianceStamped, '/mcl_pose', 10 ) def _init_uniform(self): # draw M particles uniformly from map bounds rng = np.random.default_rng(42) # deterministic seed x = rng.uniform(0.0, 8.0, self.M) y = rng.uniform(0.0, 6.0, self.M) th = rng.uniform(-np.pi, np.pi, self.M) return np.stack([x, y, th], axis=1) def _neff(self, w): return 1.0 / np.sum(w ** 2) # effective sample size def _systematic_resample(self, w): # O(M) systematic resampling cdf = np.cumsum(w) u = np.random.uniform(0, 1.0/self.M) pointers = u + np.arange(self.M) / self.M indices = np.searchsorted(cdf, pointers) return indices def _ekf_cb(self, msg): # Monitor EKF covariance trace as proxy for confidence cov_trace = (msg.pose.covariance[0] + msg.pose.covariance[7] + msg.pose.covariance[35]) neff = self._neff(self.weights) if neff < self.neff_thresh or cov_trace > 1.0: # Low confidence: inject random particles n_aug = int(self.alpha_aug * self.M) aug = self._init_uniform()[:n_aug] aug_idx = np.random.choice(self.M, n_aug, replace=False) self.particles[aug_idx] = aug self.get_logger().warn( f'MCL recovery: Neff={neff:.0f}, injecting {n_aug} random particles' )
In Nav2's AMCL (Adaptive Monte Carlo Localization), this architecture is already built in. The relevant parameters for FollowBot's amcl.yaml:
amcl: ros__parameters: min_particles: 500 # minimum M (adaptive MCL lower bound) max_particles: 3000 # maximum M during global localization alpha1: 0.2 # rot noise from rot alpha2: 0.2 # rot noise from trans alpha3: 0.2 # trans noise from trans alpha4: 0.2 # trans noise from rot recovery_alpha_slow: 0.001 # slow filter for weight avg recovery_alpha_fast: 0.1 # fast filter — triggers injection resample_interval: 1 # resample every N updates robot_model_type: "nav2_amcl::DifferentialMotionModel" laser_model_type: "likelihood_field" laser_max_range: 12.0 # RPLIDAR A2 max range laser_min_range: 0.1 max_beams: 60 # subsample scan (360 → 60 beams) z_hit: 0.5 # weight of Gaussian hit model z_rand: 0.5 # weight of uniform random model sigma_hit: 0.2 # std of Gaussian hit (meters)
The recovery_alpha_slow and recovery_alpha_fast parameters implement Thrun's KLD-sampling with recovery augmentation. When the fast average of observation likelihoods drops significantly below the slow average, the filter injects random particles proportional to (1 - w_fast/w_slow). This is the standard production defense against the kidnapped-robot problem in AMCL.
With the full EKF operational and AMCL running as a localization layer: (1) Position error below 0.1 m RMS in a known map — verified by comparing AMCL pose estimates to ground-truth marks on the floor. (2) Filter consistency validated with NEES test on recorded data (Lesson 4-4 procedure). (3) Sensor dropout behavior characterized: when the LIDAR loses all valid returns (person blocks scan), the EKF propagates on odometry alone for up to 2 seconds before covariance exceeds threshold and a warning is issued. (4) Kidnapping recovery: AMCL converges to the correct pose within 30 seconds of being placed at a random new location, with >90% reliability across 10 trials at M=2000 particles.
WEAKNESSWhere particle filters bite
The most dangerous misunderstanding about particle filters: people see the cloud converge to a tight cluster and conclude the filter is healthy. Convergence to a wrong mode is indistinguishable from convergence to the correct mode by looking at the particle spread alone. After the kidnapping, the filter converges confidently — to the wrong location. The robot then drives into walls with complete certainty. The fix is to never solely monitor particle spread; always also monitor observation likelihood averaged over the particle set. If the average likelihood is low even though the particles are tightly clustered, the cloud has converged to a location that does not match the sensor data.
With M = 50 particles in a 2D room of 8 m × 6 m = 48 m², each particle represents approximately 1 m² of floor area. That means the filter may miss the true robot location entirely if it is more than about 0.5 m from the nearest particle at initialization. The filter will not tell you this: it will converge to the nearest particle's location, with apparently low uncertainty. The silence is the problem. Always run enough particles to ensure the initial distribution covers the space adequately: a minimum of one particle per 0.5 m × 0.5 m × 15° cell is a reasonable heuristic for 2D localization — which gives roughly 2,000 particles for a typical 10 m × 10 m room.
It is common to see particle filter implementations used for state vectors of dimension 5, 6, or even 10 in research papers. This almost always works in simulation, where the sensor model is exact and the motion model has low noise. In real hardware, the noise is higher, the state space needs more coverage, and M must grow exponentially to maintain coverage. A 6D state space that required M = 1,000 particles in simulation may need M = 100,000 in the field to maintain the same localization quality. At that scale, the EKF — scaling polynomially with state dimension — almost always wins on both accuracy and speed. The particle filter's home is 2D–3D state spaces: (x, y, θ) for mobile robot localization, or (x, y, θ, d) where d is a discrete room label.
KEY INSIGHTHow this connects
- 4.2 · The Bayes Filter and the Predict-Update Cycle — The particle filter is a sample-based implementation of the Bayes filter derived there. Every SIR step maps directly onto the Bayes filter's predict and update equations; the particle filter simply avoids computing the integral analytically by using Monte Carlo samples instead.
- 4.5 · The Extended Kalman Filter: Nonlinear Systems and Jacobian Linearization — The EKF is the practical complement to the particle filter: fast, memory-efficient, and excellent when the posterior is unimodal Gaussian. The design pattern of using MCL for global localization and then handing off to EKF for steady-state tracking combines both filters' strengths.
- Next: 4.8 · IMU Preintegration and High-Rate Sensor Fusion — With localization established via AMCL + EKF, the next question is how to fuse the 200 Hz IMU with the 10 Hz LIDAR without blocking the localization loop. IMU preintegration solves this by accumulating high-rate measurements between LIDAR updates.
The particle filter closes the loop on Stage 4's core question: what shape can a belief take, and which filter is right for that shape? Linear Gaussian → Kalman filter. Nonlinear Gaussian → EKF or UKF. Multimodal or non-Gaussian → particle filter. This taxonomy will reappear in Stage 5 when SLAM fuses localization with mapping, and the choice of landmark representation (Gaussian EKF-SLAM vs. Rao-Blackwellized particle filter for FastSLAM) is driven by exactly this tradeoff.
GLOSSARYKey terms
- Sequential importance resampling (SIR)
- The standard particle filter algorithm: predict particles through the motion model, weight each particle by the observation likelihood, resample proportionally to weights. Repeating these three steps implements approximate Bayesian filtering without any Gaussian assumption.
- Importance weight
- The ratio of the target distribution to the proposal distribution, used to correct for sampling from a different distribution than the one of interest. In SIR, the weight is the observation likelihood p(z | x): how probable is the observed measurement given that the robot is at this particle's location.
- Effective sample size (Neff)
- A summary statistic of weight degeneracy: Neff = 1 / Σ(w̃m)². Ranges from 1 (all weight on one particle) to M (uniform weights). Low Neff signals that resampling is needed, or that the filter is suffering from particle deprivation.
- Systematic resampling
- A resampling strategy using a single random offset u ~ Uniform[0, 1/M] and M evenly-spaced pointers through the cumulative weight function. Reduces resampling variance from O(M) (multinomial) to O(1), and runs in O(M) time. The standard choice for mobile robot localization.
- Particle deprivation
- The condition in which all M particles are clustered near one (possibly incorrect) location, leaving no particles to represent alternative hypotheses. Occurs after convergence when diversity is lost. Recovery requires injecting new particles drawn from a broad prior, not from the current particle set.
- Recovery augmentation
- Injecting a fraction α of particles drawn uniformly from the state space at each filter cycle (or triggered by Neff dropping below a threshold). The standard defense against the kidnapped-robot problem. Implemented in Nav2's AMCL as recovery_alpha_fast/slow.
- Monte Carlo Localization (MCL)
- The application of the particle filter to the mobile robot localization problem: the state is the robot's 2D pose (x, y, θ), the map is known, and the filter maintains a particle distribution over the set of possible poses. Used for global localization and kidnapping recovery.
- Curse of dimensionality
- The exponential growth of the particle count needed to cover a state space as the state dimension increases. A particle filter that works with M = 1,000 for a 3D pose space would need M ~ 10⁶ for a 6D state space to maintain comparable coverage. This limits practical particle filter use to low-dimensional state spaces.
ACTIVE RECALLCheck your understanding
Answer in your own words first, then reveal.
1Why does the particle filter handle multimodal beliefs when the EKF cannot, even though both implement the Bayes filter?›
Both the EKF and particle filter are implementations of Bayes filtering, but they differ in how they represent the posterior belief. The EKF constrains the posterior to be Gaussian — a single mean and covariance. A Gaussian cannot represent two separated probability masses simultaneously; the best it can do is place the mean between them, which is a location where the robot definitely is not. The particle filter makes no distributional assumption: it carries the belief as a weighted set of M samples from the state space. Multiple high-weight clusters in different locations represent a genuinely multimodal belief. After a few more measurement updates that are consistent with one mode and inconsistent with the other, the filter naturally concentrates its particles on the correct mode through the weight-and-resample mechanism, without any special multimodal bookkeeping.
2A converged particle filter is kidnapped (the robot is physically moved). Describe, step by step, why the filter cannot self-recover without augmentation.›
After convergence, all M particles are clustered near the (former) correct pose. When the robot is kidnapped to a new location, no motion command is issued, so the predict step does not move the particles — they remain at the old location. At the weight step, the observation likelihood is evaluated for each particle: every particle is far from the true new pose, so every particle gets near-zero weight. The weights are then normalized — dividing near-zero numbers by their (very small) sum — which produces numerically noisy uniform-ish weights, but concentrated on whichever particle happened to have the highest likelihood in the wrong cluster. The resample step then duplicates these wrong particles. In subsequent cycles, the predict step spreads the cloud slightly via motion noise, but since all particles are in the wrong neighborhood, the weights remain low and the filter just shuffles wrong particles around. There is no mechanism to generate particles near the true new location; the filter is trapped. Augmentation (injecting random particles from the full state space) creates that mechanism: the injected particles are sparse and most receive low weights, but any that land near the true pose receive high weights and get duplicated, gradually shifting the population to the correct location.
3What does Neff = 1 mean, and why is it dangerous even if it arises right after the filter correctly converges?›
Neff = 1 / Σ(w̃m)² = 1 means one particle has importance weight ≈ 1 and all others have weight ≈ 0. The filter's entire belief is concentrated on one sample. If that sample happens to be at the correct pose, the point estimate is accurate — but the filter has lost all diversity. The danger: the next resample step will duplicate this one particle M times, producing M identical particles. The predict step will spread them by the motion noise model, but the spread is tiny (only one step of motion noise). If any unexpected event then causes the observation likelihood at that location to drop — a new obstacle, a person walking between the robot and the landmark, or an actual kidnapping — there are no alternative particles to up-weight. The filter will stubbornly remain at the previous mode with apparent confidence. Neff should be monitored as a health metric; its drop below M/2 is a warning to trigger resampling (if using adaptive resampling) or augmentation.
4Why is systematic resampling preferred over multinomial resampling in practice, and what does "O(1) variance" mean in this context?›
Multinomial resampling draws each of M new particles independently from the weight distribution. Because each draw is independent, a particle with weight 0.3 might be drawn 0, 1, 2, or 3 times in a set of 10 draws — there is randomness in how many copies each particle gets, beyond what the weights prescribe. This sampling variance is O(M) — it scales with the number of particles. Systematic resampling uses a single random offset u ~ Uniform[0, 1/M] and places M equally-spaced pointers at u, u + 1/M, u + 2/M, … across the cumulative weight function. Every particle with weight close to 1/M is nearly guaranteed to receive exactly one copy; the only randomness is in the single offset u, which is O(1) — it does not grow with M. In practice this means the particle population after systematic resampling is much more representative of the target distribution than after multinomial resampling with the same M. The filter achieves better localization accuracy with fewer particles, or equivalently, can run in real time with a smaller M while maintaining the same quality.