Particle Filter

A particle filter is a simulation-based method for estimating the changing, unobserved state of a system from a sequence of noisy observations. It represents a posterior probability distribution by a finite set of weighted samples called particles. As each observation arrives, the method propagates the particles through a state-transition model, adjusts their weights according to the observation model, and may resample them so that computational effort remains concentrated in plausible regions of the state space. Particle filters are also called sequential Monte Carlo (SMC) methods.

Particle filtering is a form of recursive Bayesian inference. Its sampling representation can handle nonlinear dynamics, non-Gaussian noise, discrete-continuous mixtures, and posterior distributions with several modes. This flexibility comes at a cost: the result has Monte Carlo error, performance depends strongly on the proposal distribution, and the number of particles needed can become very large as state dimension or observation informativeness increases.^[2][3] The Kalman filter, by contrast, gives an exact finite-dimensional recursion for linear systems with Gaussian noise.

Gordon, Salmond, and Smith introduced the bootstrap filter in 1993 as a recursive estimator whose state density is represented by random samples rather than a fixed grid or a Gaussian approximation.^[1] Closely related ideas developed under names such as Monte Carlo filter, sampling-importance-resampling filter, condensation, and survival of the fittest. Work in statistics and signal processing during the 1990s brought these constructions into the general SMC framework.^[3][4][5]

Bayesian filtering problem

A particle filter normally starts from a discrete-time state-space model. Let $X_t$ be a hidden state and $Y_t$ the observation at time $t$. A Markov model specifies an initial distribution, a transition density, and an observation density:

$$X_0 \sim \mu_0, \qquad X_t\mid X_{t-1}=x_{t-1}\sim f_t(\cdot\mid x_{t-1}), \qquad Y_t\mid X_t=x_t\sim g_t(\cdot\mid x_t).$$

The transition density $f_t$ describes how the state evolves, while $g_t(y_t\mid x_t)$ is the likelihood of the new observation at a proposed state. The conditional-independence assumptions are those of a continuous-state hidden Markov model: the current state depends on the past through $X_{t-1}$, and the current observation depends on the state through $X_t$.^[2][3]

Filtering seeks the distribution $p(x_t\mid y_{1:t})$ using observations only through the present time. The exact recursion has a prediction step,

$$p(x_t\mid y_{1:t-1})=\int f_t(x_t\mid x_{t-1})p(x_{t-1}\mid y_{1:t-1})\,dx_{t-1},$$

followed by a correction using Bayes' theorem:

$$p(x_t\mid y_{1:t})= \frac{g_t(y_t\mid x_t)p(x_t\mid y_{1:t-1})} {\int g_t(y_t\mid x'_t)p(x'_t\mid y_{1:t-1})\,dx'_t}.$$

These integrals are tractable for a few special model classes. In a general nonlinear or non-Gaussian model, the predicted and corrected distributions need not belong to a family that can be summarized by a fixed set of parameters. A particle filter replaces the integrals with a random empirical approximation.^[2][3]

At time $t$, a weighted particle set approximates the filtering distribution as

$$\widehat p_t(dx)=\sum_{i=1}^{N}W_t^{(i)}\delta_{X_t^{(i)}}(dx), \qquad \sum_{i=1}^{N}W_t^{(i)}=1,$$

where $\delta_x$ is a point mass at $x$. An expectation of a function $h$ is then estimated by

$$\mathbb{E}[h(X_t)\mid y_{1:t}]\approx\sum_{i=1}^{N}W_t^{(i)}h(X_t^{(i)}).$$

The particle cloud can describe a skewed or multimodal posterior without fitting a Gaussian mixture explicitly. It remains a finite random approximation, so two runs with different random seeds generally produce different estimates.

Sequential importance sampling

The basic construction applies importance sampling repeatedly as the target distribution changes. Suppose a proposal for a new state has density

$$q_t(x_t\mid x_{0:t-1},y_{1:t}).$$

For each existing trajectory, the filter samples

$$X_t^{(i)}\sim q_t(\cdot\mid X_{0:t-1}^{(i)},y_{1:t})$$

and updates its unnormalized weight by

$$\widetilde w_t^{(i)}= w_{t-1}^{(i)} \frac{g_t(y_t\mid X_t^{(i)})f_t(X_t^{(i)}\mid X_{t-1}^{(i)})} {q_t(X_t^{(i)}\mid X_{0:t-1}^{(i)},y_{1:t})}.$$

Normalization gives

$$W_t^{(i)}=\frac{\widetilde w_t^{(i)}}{\sum_{j=1}^{N}\widetilde w_t^{(j)}}.$$

The ratio corrects the difference between the distribution used to propose particles and the state-space model's target distribution. The proposal must place probability wherever the target has relevant mass. Otherwise an important part of the posterior can be absent from the particle set and reweighting cannot recover it.^[2][3][5]

The bootstrap proposal uses the transition density itself:

$$q_t(x_t\mid x_{0:t-1},y_{1:t})=f_t(x_t\mid x_{t-1}).$$

The incremental ratio then reduces to the observation likelihood $g_t(y_t\mid X_t^{(i)})$. This choice makes the filter simple because it only needs to simulate the transition and evaluate the likelihood. It can perform poorly when a new observation is much more informative than the transition model. Most propagated particles may then land where the likelihood is nearly zero.^[1][2]

A proposal conditioned on both the preceding state and current observation can place particles closer to the new posterior. The locally optimal proposal $p(x_t\mid x_{t-1},y_t)$ minimizes the conditional variance of the incremental weights at that step, but exact sampling from it and evaluation of its normalizing factor are usually unavailable. Practical filters use analytic approximations, local Gaussian filters, mixtures, or application-specific proposal mechanisms.^[2][3]

Resampling and degeneracy

Sequential importance sampling suffers from weight degeneracy. Products of incremental importance ratios become increasingly uneven, and after enough updates only a few trajectories contribute appreciably to estimates. Computing transitions and likelihoods for particles with negligible weight then wastes most of the particle budget.^[2][3]

A common diagnostic is the estimated effective sample size (ESS):

$$\widehat N_{\mathrm{eff}}=\frac{1}{\sum_{i=1}^{N}(W_t^{(i)})^2}.$$

It ranges from $1$, when one normalized weight is one, to $N$, when all weights equal $1/N$. The term does not mean that a weighted particle set literally contains that many independent posterior draws. It is a variance-based proxy inherited from importance sampling and is normally used as a resampling trigger.^[3][6] A threshold of $N/2$ is common, but the appropriate value depends on the model, proposal, cost of resampling, and quantity being estimated.

Resampling draws ancestor indices according to the normalized weights, copies the selected particles, and resets their weights to $1/N$. High-weight particles may receive several descendants, while low-weight particles disappear. This removes extreme weight inequality but adds random selection error. It also creates duplicate particles and reduces ancestral diversity. Repeated resampling can cause many current particles to descend from the same early trajectory, a problem known as genealogical or path degeneracy.^[3][4]

Weight degeneracy and sample impoverishment are therefore different. Resampling treats the first by discarding low-weight particles. It can worsen the second when transition noise is small or the particle count is low, because many identical copies then remain close together. Jittering, regularization, MCMC rejuvenation, better proposals, or additional particles can restore diversity, but each changes computational cost and may introduce tuning or bias.

Several resampling schemes are widely used:^[7]

Scroll sideways for more →

Residual and stratified resampling admit general variance comparisons that favor them over multinomial resampling. Systematic resampling often works well in applications, but Douc, Cappé, and Moulines gave a counterexample to a universal variance ordering for it.^[7] That distinction matters when a method is chosen for theoretical guarantees rather than implementation convenience.

Basic filtering cycle

A particle filter can be organized as the following online cycle. Equivalent implementations may resample before propagation rather than after weighting, but they target the same recursion when their weights are adjusted consistently.^[2][3]

1. Draw initial particles from $\mu_0$ or another proposal, and compute initial importance weights if required.
2. For each particle, sample a new state from $q_t(\cdot\mid X_{0:t-1}^{(i)},y_{1:t})$.
3. Multiply the previous weight by the transition-likelihood-to-proposal ratio.
4. Normalize the weights and calculate any requested state estimates, probabilities, or predictive quantities.
5. Evaluate a degeneracy criterion such as ESS. If it crosses the chosen threshold, resample the particle set and reset the weights.
6. Retain the current particles and any ancestry needed for the next update.

For current-state filtering, the implementation need not store complete trajectories. It can retain $N$ current states and, where needed, ancestor indices or sufficient statistics. Smoothing, which conditions earlier states on later observations, needs additional ancestry or backward-sampling machinery and is more exposed to genealogical collapse.^[3]

Common variants

Particle-filter variants change the proposal, selection step, state decomposition, or particle count. The names overlap across fields, so a stated algorithm should specify its proposal and resampling schedule rather than rely on a label alone.

Scroll sideways for more →

Particle methods also extend beyond online state filtering. Particle MCMC uses a particle filter inside a Markov chain construction for joint state and parameter inference. Under its stated conditions, the outer method targets the intended posterior even though it uses a finite-particle likelihood estimate or conditional particle update.^[12] General SMC samplers apply selection and mutation to sequences of static target distributions. These methods share machinery with a particle filter but solve a broader class of inference problems.

Statistical properties

Particle approximations have a developed asymptotic theory. At a fixed time and under regularity conditions, empirical estimates converge to the corresponding target expectations as the particle count $N$ increases. Central limit theorems give an $N^{-1/2}$ Monte Carlo scale for estimation error, with an asymptotic variance that depends on the model, proposal, resampling scheme, time, and test function.^[4][11] Quadrupling $N$ may therefore halve the standard-error scale in an asymptotic regime, but it does not guarantee a fixed error reduction in a poorly matched or collapsed finite-particle filter.

Fixed-time convergence is not the same as stable performance over an arbitrarily long sequence. Stability bounds require assumptions about mixing, bounded likelihoods, or related properties. Path-space estimates can deteriorate with time because repeated selection coalesces the particle genealogy. Static parameters are especially awkward: if a parameter is copied unchanged during resampling, its diversity can vanish; if artificial dynamics are added, those dynamics alter the model unless corrected.^[3][4]

Dimension creates a more severe problem. When an observation combines information from many state components, likelihood ratios can vary so much that one particle receives almost all posterior weight. Snyder and colleagues analyzed representative high-dimensional models in which the particle count required to avoid this collapse grows exponentially with a measure of effective dimension.^[18] This is a major instance of the curse of dimensionality, not a statement that every structured high-dimensional particle method must fail. Localized filters can exploit spatial structure. Rebeschini and van Handel proved dimension-free local error bounds for a block particle filter under decay-of-correlation and other assumptions.^[19]

Engineering tradeoffs

For a basic filter, work per update is roughly proportional to the number of particles times the costs of proposal sampling, state propagation, and likelihood evaluation. The simple count $O(N)$ hides application costs: evaluating a camera or range-sensor likelihood, updating a map, or running a conditional Kalman filter may dominate resampling. Memory for current-state filtering grows with the particle count and state size; storing every trajectory also grows with the time horizon.^[2][3]

Proposal quality trades computation per particle against the number of useful particles. A cheap transition-prior proposal can require a much larger $N$ than an observation-informed proposal. An elaborate proposal is worthwhile only if its reduction in weight variance compensates for its construction cost and latency. The same calculation applies to MCMC rejuvenation and analytic marginalization.^[3]

Numerical implementation affects reliability. Products of small likelihoods should be accumulated as log weights. Before exponentiation, subtracting the maximum log weight avoids many underflow failures. An implementation also needs a policy for the case in which every computed likelihood is numerically zero.^[2][3] ESS alone is not a complete diagnostic: maximum weight, the number of distinct ancestors, spatial particle spread, and repeated estimates across independent runs reveal different failure modes.

Propagation and likelihood evaluation are often parallel across particles. Normalization and resampling require communication across the population, and systematic or prefix-sum implementations can limit parallel scaling. Deterministic random-number management also matters in distributed systems because changing execution order can otherwise change the result. Real-time systems balance particle count against update deadlines, sensor rate, and worst-case rather than average computation.^[4]

No particle count compensates for a wrong model. Increasing $N$ makes the algorithm approximate the posterior implied by its transition and observation densities more closely. It does not remove sensor bias, an incorrect noise scale, unmodeled dynamics, or a likelihood that assigns negligible probability to the true observation.

Comparison with other sampling and filtering methods

Scroll sideways for more →

Rejection sampling and particle resampling are sometimes confused because both discard proposals. In rejection sampling, a proposed value is accepted with a probability chosen to produce the target distribution, normally requiring a bound $p(x)\leq Mq(x)$. In particle resampling, every output is a copy of an existing weighted particle and the number of copies is random. Resampling does not independently transform each proposal into an exact draw from the filtering distribution.^[20]

The Kalman and particle approaches can also be combined. A Rao-Blackwellized filter may use particles for nonlinear or discrete variables and a conditional Kalman filter for linear-Gaussian variables. Extended or unscented updates can supply proposals while the final particle weights correct, as far as the importance ratio permits, for the proposal approximation.^[2][9]

Robotics and SLAM

Particle filters are used in robotics because motion and sensor uncertainty often produce nonlinear and multimodal pose distributions. In Monte Carlo localization, each particle represents a possible robot pose. A motion update propagates poses from odometry or control inputs, and a map-based sensor likelihood weights them using range, sonar, or vision measurements. Unlike a single-Gaussian pose estimate, the particle set can retain several location hypotheses during global localization.^[13][14]

A localization filter still needs proposal support near the true pose. If every particle follows only a local motion model, an unexpected displacement can leave no particle in the correct region. Practical recovery schemes inject globally proposed particles or mix sensor-based and motion-based proposals. Highly informative sensors create another tension: a sharp scan likelihood can localize accurately when particles cover its support, but it can also cause immediate weight collapse when a bootstrap proposal misses that support.^[13][14]

Robotic sensor fusion may combine wheel odometry or an inertial measurement unit with cameras, sonar, or LiDAR. The particle state need not contain every uncertain quantity. Analytically tractable substructures can be marginalized, and map or landmark estimates can be stored conditionally on a sampled pose trajectory.^[9][13]

Particle filtering also supplied early scalable solutions to simultaneous localization and mapping. FastSLAM factors the posterior over a robot path $x_{1:t}$ and landmarks $m_{1:M}$ as

$$p(x_{1:t},m_{1:M}\mid z_{1:t},u_{1:t})= p(x_{1:t}\mid z_{1:t},u_{1:t}) \prod_{j=1}^{M}p(m_j\mid x_{1:t},z_{1:t}),$$

under its conditional-independence assumptions. Particles represent robot paths, while each particle carries separate landmark estimators. The original FastSLAM implementation used tree structures to obtain logarithmic landmark access and demonstrated maps with many more landmarks than contemporary full-covariance extended-Kalman SLAM systems.^[16]

Rao-Blackwellized grid mapping uses a related decomposition in which each pose-trajectory particle carries an occupancy-grid map. Grisetti, Stachniss, and Burgard improved the proposal with the latest observation and used adaptive resampling to reduce particle depletion.^[17] These methods show both sides of the particle-filter tradeoff: factorization can make a large mapping problem manageable, while each particle may carry expensive conditional state and a wrong early trajectory can eliminate the corresponding map hypothesis.

Limitations

Particle filters are not distribution-free solvers. Their main limitations follow from finite support and repeated selection.^[2][3]

• If the proposal does not reach a high-posterior region, weighting cannot create particles there.
• Informative observations or high-dimensional likelihoods can collapse the weights in one update.^[18]
• Resampling removes low-weight hypotheses and can permanently discard a mode that later observations would have revived.
• Repeated copying reduces state and path diversity, which harms smoothing and parameter learning.^[3][10]
• Estimates contain sampling error and can change materially between runs when $N$ is too small.
• Observation-informed proposals, rejuvenation moves, and structured marginalization reduce some failures but add model-specific computation and tuning.

A suitable particle filter is therefore defined by more than its particle count. Proposal support, weight calculation, resampling scheme and schedule, state factorization, numerical treatment, and diagnostics all determine whether its approximation is usable. Comparison with an analytic filter, a high-particle reference run, simulated ground truth, or repeated independent runs is often necessary before relying on a finite-particle estimate.

References

1. ^N. J. Gordon, D. J. Salmond, and A. F. M. Smith. "Novel approach to nonlinear/non-Gaussian Bayesian state estimation." *IEE Proceedings F: Radar and Signal Processing*, 140(2), 107-113, 1993. doi.org/...ip-f-2.1993.0015
2. ^M. S. Arulampalam, S. Maskell, N. Gordon, and T. Clapp. "A tutorial on particle filters for online nonlinear/non-Gaussian Bayesian tracking." *IEEE Transactions on Signal Processing*, 50(2), 174-188, 2002. doi.org/...78.978374
3. ^A. Doucet and A. M. Johansen. "A tutorial on particle filtering and smoothing: Fifteen years later." In *The Oxford Handbook of Nonlinear Filtering*, 656-705, 2011, corrected manuscript 2012. stats.ox.ac.uk/...doucet_johansen_tutorialPF2011.pdf
4. ^A. Doucet, N. de Freitas, and N. Gordon, editors. *Sequential Monte Carlo Methods in Practice*. Springer, 2001. doi.org/...978-1-4757-3437-9
5. ^J. S. Liu and R. Chen. "Sequential Monte Carlo methods for dynamic systems." *Journal of the American Statistical Association*, 93(443), 1032-1044, 1998. doi.org/...01621459.1998.10473765
6. ^A. Kong, J. S. Liu, and W. H. Wong. "Sequential imputations and Bayesian missing data problems." *Journal of the American Statistical Association*, 89(425), 278-288, 1994. doi.org/...2291224
7. ^R. Douc, O. Cappé, and E. Moulines. "Comparison of resampling schemes for particle filtering." *Proceedings of the 4th International Symposium on Image and Signal Processing and Analysis*, 64-69, 2005. doi.org/...ISPA.2005.195385
8. ^M. K. Pitt and N. Shephard. "Filtering via simulation: Auxiliary particle filters." *Journal of the American Statistical Association*, 94(446), 590-599, 1999. doi.org/...01621459.1999.10474153
9. ^A. Doucet, N. de Freitas, K. Murphy, and S. Russell. "Rao-Blackwellised particle filtering for dynamic Bayesian networks." *Proceedings of UAI 2000*, 176-183, 2000. research.google/...g-for-dynamic-bayesian-networks
10. ^W. R. Gilks and C. Berzuini. "Following a moving target: Monte Carlo inference for dynamic Bayesian models." *Journal of the Royal Statistical Society: Series B*, 63(1), 127-146, 2001. doi.org/...1467-9868.00280
11. ^N. Chopin. "Central limit theorem for sequential Monte Carlo methods and its application to Bayesian inference." *The Annals of Statistics*, 32(6), 2385-2411, 2004. doi.org/...009053604000000698
12. ^C. Andrieu, A. Doucet, and R. Holenstein. "Particle Markov chain Monte Carlo methods." *Journal of the Royal Statistical Society: Series B*, 72(3), 269-342, 2010. doi.org/...j.1467-9868.2009.00736.x
13. ^S. Thrun, W. Burgard, and D. Fox. *Probabilistic Robotics*. MIT Press, 2005. mitpress.mit.edu/...probabilistic-robotics
14. ^D. Fox, W. Burgard, F. Dellaert, and S. Thrun. "Monte Carlo localization: Efficient position estimation for mobile robots." *Proceedings of AAAI-99*, 343-349, 1999. aaai.org/...AAAI99-050.pdf
15. ^D. Fox. "KLD-Sampling: Adaptive particle filters." *Advances in Neural Information Processing Systems 14*, 713-720, 2001. papers.nips.cc/...5b205503560c4e8e6d1ea78-Abstract
16. ^M. Montemerlo, S. Thrun, D. Koller, and B. Wegbreit. "FastSLAM: A factored solution to the simultaneous localization and mapping problem." *Proceedings of AAAI-02*, 593-598, 2002. robots.stanford.edu/...montemerlo.fastslam-tr
17. ^G. Grisetti, C. Stachniss, and W. Burgard. "Improved techniques for grid mapping with Rao-Blackwellized particle filters." *IEEE Transactions on Robotics*, 23(1), 34-46, 2007. doi.org/...TRO.2006.889486
18. ^C. Snyder, T. Bengtsson, P. Bickel, and J. Anderson. "Obstacles to high-dimensional particle filtering." *Monthly Weather Review*, 136(12), 4629-4640, 2008. doi.org/...2008MWR2529.1
19. ^P. Rebeschini and R. van Handel. "Can local particle filters beat the curse of dimensionality?" *The Annals of Applied Probability*, 25(5), 2809-2866, 2015. doi.org/...14-AAP1061
20. ^C. P. Robert and G. Casella. *Monte Carlo Statistical Methods*, second edition. Springer, 2004. doi.org/...978-1-4757-4145-2