# Comparing Labeled Markov Chains: A Cantor-Kantorovich Approach

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 28 references that are in the map.
- First posted on arXiv 22 Nov 2025.

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

- [Automated Verification and Synthesis of Stochastic Hybrid Systems: A Survey](https://mlsanity.com/paper/2101.07491/) (2021)
- [On Approximating Total Variation Distance](https://mlsanity.com/paper/2206.07209/) (2022)
- [On Computing the Total Variation Distance of Hidden Markov Models](https://mlsanity.com/paper/1804.06170/) (2018)
- [On the Total Variation Distance of Labelled Markov Chains](https://mlsanity.com/paper/1405.2852/) (2014)
- [On the Relationship between Bisimulation and Trace Equivalence in an Approximate Probabilistic Context (Extended Version)](https://mlsanity.com/paper/1701.04547/) (2017)
- [Robust Probabilistic Bisimilarity for Labelled Markov Chains](https://mlsanity.com/paper/2505.15290/) (2025)
- [Data-driven memory-dependent abstractions of dynamical systems via a Cantor-Kantorovich metric](https://mlsanity.com/paper/2405.08353/) (2024)

## Abstract (arXiv)

Labeled Markov Chains (or LMCs for short) are useful mathematical objects to model complex probabilistic languages. A central challenge is to compare two LMCs, for example to assess the accuracy of an abstraction or to quantify the effect of model perturbations. In this work, we study the recently introduced Cantor-Kantorovich (or CK) distance. In particular we show that the latter can be framed as a discounted sum of finite-horizon Total Variation distances, making it an instance of discounted linear distance, but arising from the natural Cantor topology. Building on the latter observation, we analyze the properties of the CK distance along three dimensions: computational complexity, continuity properties and approximation. More precisely, we show that the exact computation of the CK distance is #P-hard. We also provide an upper bound on the CK distance as a function of the approximation relation between the two LMCs, and show that a bounded CK distance implies a bounded error between probabilities of finite-horizon traces. Finally, we provide a computable approximation scheme, and show that the latter is also #P-hard. Altogether, our results provide a rigorous theoretical foundation for the CK distance and clarify its relationship with existing distances.