  A new Bayesian modelling framework is introduced for piece-wise homogeneous
variable-memory Markov chains, along with a collection of effective algorithmic
tools for change-point detection and segmentation of discrete time series.
Building on the recently introduced Bayesian Context Trees (BCT) framework, the
distributions of different segments in a discrete time series are described as
variable-memory Markov chains. Inference for the presence and location of
change-points is then performed via Markov chain Monte Carlo sampling. The key
observation that facilitates effective sampling is that, using one of the BCT
algorithms, the prior predictive likelihood of the data can be computed
exactly, integrating out all the models and parameters in each segment. This
makes it possible to sample directly from the posterior distribution of the
number and location of the change-points, leading to accurate estimates and
providing a natural quantitative measure of uncertainty in the results.
Estimates of the actual model in each segment can also be obtained, at
essentially no additional computational cost. Results on both simulated and
real-world data indicate that the proposed methodology performs better than or
as well as state-of-the-art techniques.
