  Phylogenetics, the inference of evolutionary trees from molecular sequence
data such as DNA, is an enterprise that yields valuable evolutionary
understanding of many biological systems. Bayesian phylogenetic algorithms,
which approximate a posterior distribution on trees, have become a popular if
computationally expensive means of doing phylogenetics. Modern data collection
technologies are quickly adding new sequences to already substantial databases.
With all current techniques for Bayesian phylogenetics, computation must start
anew each time a sequence becomes available, making it costly to maintain an
up-to-date estimate of a phylogenetic posterior. These considerations highlight
the need for an \emph{online} Bayesian phylogenetic method which can update an
existing posterior with new sequences.
  Here we provide theoretical results on the consistency and stability of
methods for online Bayesian phylogenetic inference based on Sequential Monte
Carlo (SMC) and Markov chain Monte Carlo (MCMC). We first show a consistency
result, demonstrating that the method samples from the correct distribution in
the limit of a large number of particles. Next we derive the first reported set
of bounds on how phylogenetic likelihood surfaces change when new sequences are
added. These bounds enable us to characterize the theoretical performance of
sampling algorithms by bounding the effective sample size (ESS) with a given
number of particles from below. We show that the ESS is guaranteed to grow
linearly as the number of particles in an SMC sampler grows. Surprisingly, this
result holds even though the dimensions of the phylogenetic model grow with
each new added sequence.
