Title: Asymptotic genealogies of interacting particle systems with an application to sequential Monte Carlo,
Abstract: We study weighted particle systems in which new generations are resampled
from current particles with probabilities proportional to their weights. This
covers a broad class of sequential Monte Carlo (SMC) methods, widely-used in
applied statistics and cognate disciplines. We consider the genealogical tree
embedded into such particle systems, and identify conditions, as well as an
appropriate time-scaling, under which they converge to the Kingman n-coalescent
in the infinite system size limit in the sense of finite-dimensional
distributions. Thus, the tractable n-coalescent can be used to predict the
shape and size of SMC genealogies, as we illustrate by characterising the
limiting mean and variance of the tree height. SMC genealogies are known to be
connected to algorithm performance, so that our results are likely to have
applications in the design of new methods as well. Our conditions for
convergence are strong, but we show by simulation that they do not appear to be
necessary.