mlsanityData to 7 Oct 2026

On Computing the Total Variation Distance of Hidden Markov Models

arXiv 1804.06170 ↗First posted 17 Apr 2018cs.FL cs.LOcited by 8

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 1; 2024: 2; 2025: 4; 2026: 1.

8 papers.

  1. 2023Data-driven abstractions via adaptive refinements and a Kantorovich metric [extended version]cited by 3
  2. 2025Approximating the total variation distance between spin systemscited by 2
  3. 2024A distance function for stochastic matricescited by 1
  4. 2025Approximating the Total Variation Distance between Gaussianscited by 1
  5. 2024A Cantor-Kantorovich Metric Between Markov Decision Processes with Application to Transfer Learningcited by 0
  6. 2025On approximating the f-divergence between two Ising modelscited by 0
  7. 2025Comparing Labeled Markov Chains: A Cantor-Kantorovich Approachcited by 0
  8. 2026On Computing Total Variation Distance Between Mixtures of Product Distributionscited by 0