Mixing time of the conditional backward sampling particle filter

Music City Center 

The conditional backward sampling particle filter (CBPF) is a powerful Markov chain Monte Carlo sampler for general state space hidden Markov model smoothing. It was proposed as an improvement over the conditional particle filter (CPF), which is known to have an O(T^2) computational time complexity under a general 'strong' mixing assumption, where T is the time horizon. While there is empirical evidence of the superiority of the CBPF over the CPF in practice, this has never been theoretically quantified. We show that the CBPF has O(TlogT) time complexity under strong mixing. In particular, the CBPF's mixing time is upper bounded by O(logT), for any sufficiently large number of particles N that depends only on the mixing assumptions and not T. We also show that an O(logT) mixing time is optimal. The proof involves the analysis of a novel coupling of two CBPFs, which employs a maximal coupling of two particle systems at each time instant. The coupling is implementable, and thus can also be used to construct unbiased, finite variance, estimates of functionals which have arbitrary dependence on the latent state's path, with a total expected cost of O(TlogT). We also investigate other couplings, and we show some of these alternatives can have improved empirical behaviour.

Conditional Particle Filter

Gibbs Sampling

State-space model

Mixing time

Unbiased estimation

Smoothing