---
tag: W8R4A5D4N8
kind: definition
name: Particle filter
msc: [62M20, 65C35, 60G35]
defines: BZK7HQDMT0
uses: [HJVM390354, 0NM6E9VW04, 0990W5PN13, 0G48PYM96Q]
sources:
  - url: https://en.wikipedia.org/wiki/Particle_filter
---

## Definition

Consider a state-space model: a [[Markov chain|0G48PYM96Q]] $(X_t)_{t \ge 0}$ with initial density $\mu$ and transition density $f(x_t \mid x_{t-1})$.
The observations $Y_t$ are conditionally independent given the states, with density $g(y_t \mid x_t)$.
Fix a number $N \ge 1$ of particles and observed values $y_1, y_2, \dots$.
The *bootstrap particle filter* (sequential importance resampling) runs as follows.

1. Draw $x_0^{(1)}, \dots, x_0^{(N)}$ independently from $\mu$.
2. At time $t \ge 1$, draw $\tilde x_t^{(i)}$ from $f(\cdot \mid x_{t-1}^{(i)})$ for each $i$.
3. Compute the weights $w_t^{(i)} = g(y_t \mid \tilde x_t^{(i)}) / \sum_{k=1}^{N} g(y_t \mid \tilde x_t^{(k)})$.
4. Draw $x_t^{(1)}, \dots, x_t^{(N)}$ from the weighted points, choosing $\tilde x_t^{(i)}$ with probability $w_t^{(i)}$.

The filtering distribution of $X_t$ given $y_1, \dots, y_t$ is approximated by the weighted empirical measure $\sum_{i=1}^{N} w_t^{(i)} \delta_{\tilde x_t^{(i)}}$.

## Remarks

Steps 2 and 3 are a Monte Carlo version of the prediction step and of the update by [[Bayes' theorem|0NM6E9VW04]] in the exact filtering recursion.
General particle filters draw $\tilde x_t^{(i)}$ from another proposal density $q$ and multiply the weight by $f / q$.
As $N \to \infty$, integrals against the particle approximation converge to the exact filtering integrals under mild conditions.

Example: let $X_t = X_{t-1} + U_t$ and $Y_t = X_t + V_t$ with independent standard normal $U_t, V_t$.
Then $g(y \mid x)$ is proportional to $e^{-(y - x)^2 / 2}$, so particles close to $y_t$ get the largest weights in step 3.
For this linear Gaussian model the exact filter is the Kalman filter, and the particle filter approximates it.

Non-example: if step 4 is left out, the method is sequential importance sampling.
Then after a few steps almost all the weight sits on one particle, which is why the resampling step is part of the definition.