




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. Technical report, arXiv.org, 2014. Available at http://arxiv.org/abs/1405.2852.
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:
@techreport{14CKLICSTR,
author = {Taolue Chen and Stefan Kiefer},
institution = {arXiv.org},
note = {Available at http://arxiv.org/abs/1405.2852},
title = {On the Total Variation Distance of Labelled {M}arkov Chains},
year = {2014}
}




