Bayesian Filtering and Belief States › Particle Filters

The particle filter represents the belief nonparametrically, as a weighted set of samples $\{(x^{(i)}, w^{(i)})\}_{i=1}^N$ approximating $b_t$. Prediction becomes simulation: draw each particle through the transition model. Correction becomes reweighting: each particle's weight scales by its likelihood $p(o_t \mid x_t^{(i)})$. Under standard sequential Monte Carlo regularity conditions, including a proposal whose support covers the target and controlled importance weights, the empirical distribution converges to the true belief as $N \to \infty$ without assuming a parametric belief shape. Multimodality, skewness, and heavy tails can therefore be represented by placing samples where they belong. This asymptotic result is not unconditional: finite particle budgets, poor proposals, unbounded weights, and high state dimension can still make the approximation fail badly.

The practical algorithm, often called the bootstrap or SIR filter (Gordon, Salmond, and Smith, 1993), adds one decisive step:

1. Propagate: sample $x_t^{(i)} \sim p(x_t \mid x_{t-1}^{(i)}, a_{t-1})$ for each particle.
2. Reweight: set $w_t^{(i)} \propto w_{t-1}^{(i)}\, p(o_t \mid x_t^{(i)})$, then normalize.
3. Resample when needed: draw $N$ particles from the current weighted set, resetting weights to uniform.

Resampling addresses weight degeneracy. Repeated likelihood updates can leave nearly all weight on a few particles; the rate depends on the proposal, observation informativeness, state dimension, and dynamics. The effective sample size is estimated as

and collapses toward one as weights concentrate. Resampling removes low-weight particles and duplicates high-weight ones, resetting the weights without restoring hypotheses that have disappeared. Repeated cloning can therefore erode state-space diversity. The particle-filter implementation built in the Code Implementation section ahead resamples when $N_{\text{eff}} < N/2$. Jitter, regularization, and observation-informed proposals can reduce this sample impoverishment.

Particle filters are useful when a finite sample set can represent structure that a Gaussian cannot, including multimodality, nonlinear sensing, and non-Gaussian noise. Their weakness is dimensional: maintaining useful coverage becomes rapidly more expensive as dimension grows, with the practical rate depending on posterior structure and proposal quality. Rao-Blackwellization exploits conditional linear structure by sampling only a smaller nonlinear or discrete component while filtering the remaining variables analytically. More generally, marginalizing a tractable subproblem instead of sampling it reduces Monte Carlo variance.