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}
}