# Variational Markov chain mixtures with automatic component selection

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 70 references that are in the map.
- First posted on arXiv 7 Jun 2024.

## Builds on (most cited first, 6 of 6)

- [Randomly pivoted Cholesky: Practical approximation of a kernel matrix with few entry evaluations](https://mlsanity.com/paper/2207.06503/) (2022)
- [Learning Mixtures of Markov Chains and MDPs](https://mlsanity.com/paper/2211.09403/) (2022)
- [Model-based clustering based on sparse finite Gaussian mixtures](https://mlsanity.com/paper/1606.06828/) (2016)
- [Learning Mixtures of Markov Chains with Quality Guarantees](https://mlsanity.com/paper/2302.04680/) (2023)
- [Clustering Discrete-Valued Time Series](https://mlsanity.com/paper/1901.09249/) (2019)
- [Clustering sequence data with mixture Markov chains with covariates using multiple simplex constrained optimization routine (MSiCOR)](https://mlsanity.com/paper/1609.02249/) (2016)

## Abstract (arXiv)

Markov state modeling has gained popularity in various scientific fields since it reduces complex time-series data sets into transitions between a few states. Yet common Markov state modeling frameworks assume a single Markov chain describes the data, so they suffer from an inability to discern heterogeneities. As an alternative, this paper models time-series data using a mixture of Markov chains, and it automatically determines the number of mixture components using the variational expectation-maximization algorithm.Variational EM simultaneously identifies the number of Markov chains and the dynamics of each chain without expensive model comparisons or posterior sampling. As a theoretical contribution, this paper identifies the natural limits of Markov state mixture modeling by proving a lower bound on the classification error. It then presents numerical experiments where variational EM achieves performance consistent with the theoretically optimal error scaling. The experiments are based on synthetic and observational data sets including Last.fm music listening, ultramarathon running, and gene expression. In each of the three data sets, variational EM leads to the identification of meaningful heterogeneities.