Crisan (2001)

These notes are based on the article:

Crisan, Dan (2001): “Particle Filters–A Theoretical Perspective,” in Sequential Monte Carlo Methods in Practice, ed. by A. Doucet, N. de Freitas, and N. Gordon. New York: Springer-Verlag.

Introduction

This article provides a formal mathematical treatment of the convergence of particle filters. It presents several theorems which provide necessary and sufficient conditions for each of two types of convergence of the particle filter to the posterior distribution of the signal.

Notation

This chapter essentially deals with random measures on ${ℝ}^d$. Let $ℬ({ℝ}^d)$ denote the $\sigma$-algebra of Borel subsets of ${ℝ}^d$, let $B({ℝ}^d)$ denote the set of bounded measurable functions on ${ℝ}^d$, and let ${𝒞}_b({ℝ}^d)$ denote the set of bounded continuous functions on ${ℝ}^d$. We employ the sup norm on ${𝒞}_b({ℝ}^d)$ such that $$\Vert f\Vert \equiv \underset{x\in {ℝ}^d}{\sup }|f(x)|$$ for any $f\in {𝒞}_b({ℝ}^d)$.

Let $𝒫({ℝ}^d)$ denote the set of probability measures over $ℬ({ℝ}^d)$. For any such measure $\mu \in 𝒫({ℝ}^d)$ and any measurable function $f$, we denote the integral of $f$ with respect to $\mu$ as $$\mu f\equiv \int fd\mu .$$

We endow $𝒫({ℝ}^d)$ with the weak topology. Then for any sequence $\{{\mu }_n\}$ in $𝒫({ℝ}^d)$, we say that ${\mu }_n$ converges weakly to $\mu \in 𝒫({ℝ}^d)$ if $$\underset{n\to \mathrm{\infty }}{\lim }{\mu }_{n}f=\mu f,\text{for all}f\in {𝒞}_b({ℝ}^d).$$ In this case we write ${\lim }_{n\to \mathrm{\infty }}{\mu }_n=\mu$ or simply ${\mu }_n\to \mu$.

Markov chains

Let $(\Omega ,ℱ,P)$ be a probability space and let let $X=\{X_t,t\in \mathbb{N}\}$ be a stochastic process on this space. Let ${ℱ}_t^X$ denote the $\sigma$-algebra generated by the process. We say that $X$ is a Markov chain if for every $t$ and $A\in ℬ({ℝ}^{n_x})$ we have $$P(X_{t+1}\in A|{ℱ}_t^X)=P(X_{t+1}\in A|X_t).$$ Let $K_t:{ℝ}^{n_x}\times ℬ({ℝ}^{n_x})\to [0,1]$ denote the transition kernel of $X$, where $$K_t(x,A)=P(X_{t+1}\in A|X_t=x)$$ gives the probability of $X_{t+1}$ arriving in $A$ given that $X_t=x$.

The Filtering Problem

Let $X=\{X_t,t\in \mathbb{N}\}$ denote the signal, a Markov process on ${ℝ}^{n_x}$ with kernel $K_t(x,\mathrm{dy})$, and let $Y=\{Y_t,t\in \mathbb{N}\}$ denote the observation process, a stochastic process on ${ℝ}^{n_y}$ which evolves according to $$Y_t\equiv h(t,X_t)+W_t,t>0,$$ with $Y_0=0$. Here, $h:\mathbb{N}\times {ℝ}^{n_x}\to {ℝ}^{n_y}$ is a measurable function that is continuous in on ${ℝ}^{n_x}$ for all $t\in \mathbb{N}$ and $W_t:\Omega \to {ℝ}^{n_y}$ are independent random vectors. Let $g(t,\cdot )$ denote the density of $W_t$ with respect to Lebesgue measure and suppose that $g$ is bounded and continuous.

The filtering problem is to compute the conditional density of the signal $X_t$ given a sequence of observations $y_{0:t}=\{y_0,\dots ,y_t\}$ on the observation process $Y$ up to time $t$. We denote this distribution of interest as $${\pi }_t^{y_{0:t}}(A)\equiv P(X_t\in A|Y_{0:t}=y_{0:t})$$ for all $A\in ℬ({ℝ}^{n_x})$. We will also use the predicted conditional density given $y_{0:t-1}$, $$p_t^{y_{0:t-1}}(A)\equiv P(X_t\in A|Y_{0:t-1}=y_{0:t-1}).$$

Convergence of random measures

The particle filter essentially constructs a sequence of random measures, or measure-valued random variables, which approximate the true conditional distribution ${\pi }_t^{y_{0:t}}$. This sequence is designed to converge to the true distribution, but we must be more specific about what we mean by convergence here. Crisan outlines two modes of convergence in the chapter, but I will only cover the second mode here: almost sure convergence in the weak topology.

Definition. Let $\{{\mu }^n\}$ be a sequence of random probability measures, ${\mu }^n:\Omega \to 𝒫({ℝ}^d)$ and let $\mu \in 𝒫({ℝ}^d)$ be a deterministic probability measure. We say that the sequence $\{{\mu }^n\}$ converges weakly almost surely to $\mu$ if there exists some set $E$ with measure zero such that for each $\omega \in \tilde{E}$, we have $$\underset{n\to \mathrm{\infty }}{\lim }{\mu }^n(\omega )f=\mu f,\text{for all}f\in {𝒞}_b({ℝ}^d).$$ We write this as ${\mu }^n\to \mu$ $P$-a.s..

Particle Filters

The class of particle filters described below involves a collection of $n$ particles which evolve according to a specified Markov transition kernel each period and are resampled with replacement according to their importance weights. At each point in time $t$, the resulting empirical measure ${\pi }_t^n$ is shown to converge to the true conditional distribution ${\pi }_t^{y_{0:t}}$ as the number of particles approaches infinity.

Crisan discusses a much more general class of algorithms than the one I describe below, but generally speaking most particle filters use an algorithm similar to the following.

Initialization. The particle filter is initialized with an empirical measure ${\pi }_0^n$ which is built from a random sample of size $n$ from ${\pi }_0$: $${\pi }_0^n=\frac{1}{n}\sum _{i=1}^n{\delta }_{x_0^{(i)}}$$ where $x_0^{(i)}\sim {\pi }_0$ and ${\delta }_x$ denotes the Dirac delta mass located at $x$.

Note that ${\pi }_0^n$ is a random measure because the particles were drawn randomly from ${\pi }_0$. The resulting measure is conditional upon the particular sequence of random deviates used to construct these draws. It is useful to think of $\omega$ in this case as a vector of Uniform(0,1) deviates that could be used to generate draws from the distribution of ${\pi }_0$. In subsequent steps, it will also be necessary to generate random draws to transition the particles.

Iteration. This step constructs ${\pi }_t^n$ given ${\pi }_{t-1}^n$. We are given $${\pi }_{t-1}^n=\frac{1}{n}\sum _{i=1}^n{\delta }_{x_{t-1}^{(i)}}.$$ We pass each $x_{t-1}^{(i)}$ through the transition kernel to generate particles ${\overline{x}}_t^{(i)}$ such that $${\overline{x}}_t^{(i)}\sim K_{t-1}(x_{t-1}^{(i)},\cdot ).$$ These particles move independently of each other. We can now build an approximation to the predicted conditional distribution $p_t$: $$p_t^n=\frac{1}{n}\sum _{i=1}^n{\delta }_{{\overline{x}}_t^{(i)}}.$$

Next, for each particle ${\overline{x}}_t^{(i)}$ we compute the importance weight $$w_t^{(i)}=\frac{g(x_t^{(i)})}{\sum _{j=1}^{n}g(x_t^{(j)})}.$$ Now, we resample $n$ particles with replacement in proportion to the importance weights to obtain a sample $\{x_t^{(1)},\dots ,x_t^{(n)}\}$ in order to construct the desired approximation $${\pi }_t^n=\frac{1}{n}\sum _{i=1}^n{\delta }_{x_t^{(i)}}.$$

Convergence Theorems

Crisan shows that if the random measures ${\pi }_t^n$ are constructed according to the algorithm described above, then for all $t$, we have ${\pi }_t^n\to {\pi }_t^{y_{0:t}}$ $P$-a.s.. Again, Crisan’s results are much more general, but this simple example illustrates the general idea of the results.

Notes

The results presented in this chapter concern only convergence. Rates of convergence are not discussed, but are discussed in Crisan, Del Moral, and Lyons (1999).