# Bayesian Context Trees: Modelling and exact inference for discrete time series

arXiv: https://arxiv.org/abs/2007.14900 · HTML: https://mlsanity.com/paper/2007.14900/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Jul 2020.

## Built on by (most cited first, 13 of 13)

- [Probability Distribution on Full Rooted Trees](https://mlsanity.com/paper/2109.12825/) (2021)
- [An Information-Theoretic Approach to Understanding Transformers' In-Context Learning of Variable-Order Markov Chains](https://mlsanity.com/paper/2410.05493/) (2024)
- [The Bayesian Context Trees State Space Model for time series modelling and forecasting](https://mlsanity.com/paper/2308.00913/) (2023)
- [Soft Bayesian Context Tree Models for Real-Valued Time Series](https://mlsanity.com/paper/2601.11079/) (2026)
- [Context-tree weighting for real-valued time series: Bayesian inference with hierarchical mixture models](https://mlsanity.com/paper/2106.03023/) (2021)
- [Change-point Detection and Segmentation of Discrete Data using Bayesian Context Trees](https://mlsanity.com/paper/2203.04341/) (2022)
- [Stringological sequence prediction I: efficient algorithms for predicting highly repetitive sequences](https://mlsanity.com/paper/2603.26852/) (2026)
- [Detecting Renewal States in Chains of Variable Length via Intrinsic Bayes Factors](https://mlsanity.com/paper/2110.07430/) (2021)
- [Probability Distribution on Rooted Trees](https://mlsanity.com/paper/2201.09460/) (2022)
- [Fitting Sparse Markov Models to Categorical Time Series Using Convex Clustering](https://mlsanity.com/paper/2202.05485/) (2022)
- [Approximate learning of parsimonious Bayesian context trees](https://mlsanity.com/paper/2407.19236/) (2024)
- [Variable Splitting Binary Tree Models Based on Bayesian Context Tree Models for Time Series Segmentation](https://mlsanity.com/paper/2601.16112/) (2026)
- [Stringological sequence prediction II: Right-to-left automaticity and related complexity measures](https://mlsanity.com/paper/2607.17369/) (2026)

## Abstract (arXiv)

We develop a new Bayesian modelling framework for the class of higher-order, variable-memory Markov chains, and introduce an associated collection of methodological tools for exact inference with discrete time series. We show that a version of the context tree weighting algorithm can compute the prior predictive likelihood exactly (averaged over both models and parameters), and two related algorithms are introduced, which identify the a posteriori most likely models and compute their exact posterior probabilities. All three algorithms are deterministic and have linear-time complexity. A family of variable-dimension Markov chain Monte Carlo samplers is also provided, facilitating further exploration of the posterior. The performance of the proposed methods in model selection, Markov order estimation and prediction is illustrated through simulation experiments and real-world applications with data from finance, genetics, neuroscience, and animal communication. The associated algorithms are implemented in the R package BCT.