




Publications  On the Total Variation Distance of Labelled Markov Chains





Reference:
Taolue Chen and Stefan Kiefer. On the total variation distance of labelled Markov chains. In Proceedings of the Joint Meeting of the TwentyThird EACSL Annual Conference on Computer Science Logic (CSL) and the TwentyNinth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 33:1–33:10, Vienna, Austria, 2014.
Abstract:
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 polynomialtime 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 NPhard and hard for the squarerootsum problem. We also make a connection between the total variation distance and Bernoulli convolutions.
Suggested BibTeX entry:
@inproceedings{14CKLICS,
address = {Vienna, Austria},
author = {Taolue Chen and Stefan Kiefer},
booktitle = {Proceedings of the Joint Meeting of the TwentyThird EACSL Annual Conference on Computer Science Logic (CSL) and the TwentyNinth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)},
pages = {33:133:10},
title = {On the Total Variation Distance of Labelled {M}arkov Chains},
year = {2014}
}




