# On Computing the Total Variation Distance of Hidden Markov Models

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Apr 2018.

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

- [Data-driven abstractions via adaptive refinements and a Kantorovich metric [extended version]](https://mlsanity.com/paper/2303.17618/) (2023)
- [Approximating the total variation distance between spin systems](https://mlsanity.com/paper/2502.05437/) (2025)
- [A distance function for stochastic matrices](https://mlsanity.com/paper/2410.12689/) (2024)
- [Approximating the Total Variation Distance between Gaussians](https://mlsanity.com/paper/2503.11099/) (2025)
- [A Cantor-Kantorovich Metric Between Markov Decision Processes with Application to Transfer Learning](https://mlsanity.com/paper/2407.08324/) (2024)
- [On approximating the f-divergence between two Ising models](https://mlsanity.com/paper/2509.05016/) (2025)
- [Comparing Labeled Markov Chains: A Cantor-Kantorovich Approach](https://mlsanity.com/paper/2511.18103/) (2025)
- [On Computing Total Variation Distance Between Mixtures of Product Distributions](https://mlsanity.com/paper/2605.03839/) (2026)

## Abstract (arXiv)

We prove results on the decidability and complexity of computing the total variation distance (equivalently, the L1-distance) of hidden Markov models (equivalently, labelled Markov chains). This distance measures the difference between the distributions on words that two hidden Markov models induce. The main results are: (1) it is undecidable whether the distance is greater than a given threshold; (2) approximation is #P-hard and in PSPACE.