On the complexity of backward smoothing algorithms

In the context of state-space models, backward smoothing algorithms rely on a backward sampling step, which by default has a O(N^2) complexity (where N is the number of particles). An alternative implementation relying on rejection sampling has been proposed in the literature, with stated O(N) complexity. We show that the running time of such algorithms may have an infinite expectation. We develop a general framework to establish the convergence and stability of a large class of backward smoothing algorithms that may be used as more reliable alternatives. We propose three novel algorithms within this class. The first one mixes rejection with multinomial sampling; its running time has finite expectation, and close-to-linear complexity (in a certain class of models). The second one relies on MCMC, and has deterministic O(N) complexity. The third one may be used even when the transition of the model is intractable. We perform numerical experiments to confirm the good properties of these novel algorithms.