# ULTRA-MC: A Unified Approach to Learning Mixtures of Markov Chains via Hitting Times

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 47 references that are in the map.
- First posted on arXiv 23 May 2024.

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

- [Learning Markov models via low-rank optimization](https://mlsanity.com/paper/1907.00113/) (2019)
- [Learning Mixtures of Markov Chains and MDPs](https://mlsanity.com/paper/2211.09403/) (2022)
- [Faster Algorithms for Computing the Stationary Distribution, Simulating Random Walks, and More](https://mlsanity.com/paper/1608.03270/) (2016)
- [Learning Mixtures of Markov Chains with Quality Guarantees](https://mlsanity.com/paper/2302.04680/) (2023)
- [Learning Networks from Random Walk-Based Node Similarities](https://mlsanity.com/paper/1801.07386/) (2018)

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

- [Measuring the Unmeasurable: Markov Chain Reliability for LLM Agents](https://mlsanity.com/paper/2604.24579/) (2026)
- [Near-Optimal Clustering in Mixture of Markov Chains](https://mlsanity.com/paper/2506.01324/) (2025)

## Abstract (arXiv)

This study introduces a novel approach for learning mixtures of Markov chains, a critical process applicable to various fields, including healthcare and the analysis of web users. Existing research has identified a clear divide in methodologies for learning mixtures of discrete and continuous-time Markov chains, while the latter presents additional complexities for recovery accuracy and efficiency. We introduce a unifying strategy for learning mixtures of discrete and continuous-time Markov chains, focusing on hitting times, which are well defined for both types. Specifically, we design a reconstruction algorithm that outputs a mixture which accurately reflects the estimated hitting times and demonstrates resilience to noise. We introduce an efficient gradient-descent approach, specifically tailored to manage the computational complexity and non-symmetric characteristics inherent in the calculation of hitting time derivatives. Our approach is also of significant interest when applied to a single Markov chain, thus extending the methodologies previously established by Hoskins et al. and Wittmann et al. We complement our theoretical work with experiments conducted on synthetic and real-world datasets, providing a comprehensive evaluation of our methodology.