  This paper presents a novel algorithm, the particle-based, rapid incremental
smoother (PaRIS), for efficient online approximation of smoothed expectations
of additive state functionals in general hidden Markov models. The algorithm,
which has a linear computational complexity under weak assumptions and very
limited memory requirements, is furnished with a number of convergence results,
including a central limit theorem. An interesting feature of PaRIS, which
samples on-the-fly from the retrospective dynamics induced by the particle
filter, is that it requires two or more backward draws per particle in order to
cope with degeneracy of the sampled trajectories and to stay numerically stable
in the long run with an asymptotic variance that grows only linearly with time.
