On the Forgetting of Particle Filters

We study the forgetting properties of the particle filter when its state - the collection of particles - is regarded as a Markov chain. Under a strong mixing assumption on the particle filter's underlying Feynman-Kac model, we find that the particle filter is exponentially mixing, and forgets its initial state in $O(\log N )$ 'time', where $N$ is the number of particles and time refers to the number of particle filter algorithm steps, each comprising a selection (or resampling) and mutation (or prediction) operation. We present an example which shows that this rate is optimal. In contrast to our result, available results to-date are extremely conservative, suggesting $O(α^N)$ time steps are needed, for some $α>1$, for the particle filter to forget its initialisation. We also study the conditional particle filter (CPF) and extend our forgetting result to this context. We establish a similar conclusion, namely, CPF is exponentially mixing and forgets its initial state in $O(\log N )$ time. To support this analysis, we establish new time-uniform $L^p$ error estimates for CPF, which can be of independent interest. We also establish new propagation of chaos type results using our proof techniques, discuss implications to couplings of particle filters and an application to processing out-of-sequence measurements.

An invitation to adaptive Markov chain Monte Carlo convergence theory

Adaptive Markov chain Monte Carlo (MCMC) algorithms, which automatically tune their parameters based on past samples, have proved extremely useful in practice. The self-tuning mechanism makes them `non-Markovian', which means that their validity cannot be ensured by standard Markov chains theory. Several different techniques have been suggested to analyse their theoretical properties, many of which are technically involved. The technical nature of the theory may make the methods unnecessarily unappealing. We discuss one technique -- based on a martingale decomposition -- with uniformly ergodic Markov transitions. We provide an accessible and self-contained treatment in this setting, and give detailed proofs of the results discussed in the paper, which only require basic understanding of martingale theory and general state space Markov chain concepts. We illustrate how our conditions can accomodate different types of adaptation schemes, and can give useful insight to the requirements which ensure their validity.

Mixing time of the conditional backward sampling particle filter

The conditional backward sampling particle filter (CBPF) is a powerful Markov chain Monte Carlo algorithm for general state space hidden Markov model smoothing. We show that, under a general (strong mixing) condition, its mixing time is upper bounded by $O(\log T)$ where $T$ is the time horizon. The result holds for a fixed number of particles $N$ which is sufficiently large (depending on the strong mixing constants), and therefore guarantees an overall computational complexity of $O(T\log T)$ f or general hidden Markov model smoothing. We provide an example which shows that the mixing time $O(\log T)$ is optimal. Our proof relies on analysis of a novel coupling of two CBPFs, which involves a maximal coupling of two particle systems at each time instant. The coupling is implementable, and can be used to construct unbiased, finite variance estimates of functionals which have arbitrary dependence on the latent state path, with expected $O(T \log T)$ cost. We also investigate related couplings, some of which have improved empirical behaviour.

JYX - Non-linear state-space methods for Bayesian time series modelling