I7 Logo
Chair for Foundations of Software Reliability and Theoretical Computer Science
Informatik Logo TUM Logo
Publications - On Computing the Total Variation Distance of Hidden Markov Models

Reference:

Stefan Kiefer. On computing the total variation distance of hidden Markov models. In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP), Leibniz International Proceedings in Informatics (LIPIcs), pages 130:1–130:13, 2018.

Abstract:

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.

Suggested BibTeX entry:

@inproceedings{18K-ICALP,
    author = {Stefan Kiefer},
    booktitle = {Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP)},
    pages = {130:1--130:13},
    series = {Leibniz International Proceedings in Informatics (LIPIcs)},
    title = {On Computing the Total Variation Distance of Hidden {M}arkov Models},
    year = {2018}
}

See dx.doi.org ...
Slides 
Tech report version