# On the Total Variation Distance of Labelled Markov Chains

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 May 2014.

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

- [Approximating the total variation distance between spin systems](https://mlsanity.com/paper/2502.05437/) (2025)
- [A Cantor-Kantorovich Metric Between Markov Decision Processes with Application to Transfer Learning](https://mlsanity.com/paper/2407.08324/) (2024)
- [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)

Labelled Markov chains (LMCs) are widely used in probabilistic verification, speech recognition, computational biology, and many other fields. Checking two LMCs for equivalence is a classical problem subject to extensive studies, while the total variation distance provides a natural measure for the "inequivalence" of two LMCs: it is the maximum difference between probabilities that the LMCs assign to the same event. In this paper we develop a theory of the total variation distance between two LMCs, with emphasis on the algorithmic aspects: (1) we provide a polynomial-time algorithm for determining whether two LMCs have distance 1, i.e., whether they can almost always be distinguished; (2) we provide an algorithm for approximating the distance with arbitrary precision; and (3) we show that the threshold problem, i.e., whether the distance exceeds a given threshold, is NP-hard and hard for the square-root-sum problem. We also make a connection between the total variation distance and Bernoulli convolutions.