On the total variation distance of labelled Markov chains

Conference paper

Chen, T. and Kiefer, S. 2014. On the total variation distance of labelled Markov chains. Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) - CSL-LICS 2014. Vienna, Austria 14 - 18 Jul 2014 Association for computing machinery. https://doi.org/10.1145/2603088.2603099
TypeConference paper
TitleOn the total variation distance of labelled Markov chains
AuthorsChen, T. and Kiefer, S.
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 polynomial-time 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 NP-hard and hard for the square-root-sum problem. We also make a connection between the total variation distance and Bernoulli convolutions.

ConferenceJoint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) - CSL-LICS 2014
ISBN
Hardcover9781450328869
PublisherAssociation for computing machinery
Publication dates
Print14 Jul 2014
Publication process dates
Deposited03 Jun 2015
Output statusPublished
Additional information

Article No. 33

Digital Object Identifier (DOI)https://doi.org/10.1145/2603088.2603099
LanguageEnglish
Book titleProceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) - CSL-LICS '14
Permalink -

https://repository.mdx.ac.uk/item/85893

Log in to edit

Restricted files

Publisher's version

  • 14
    total views
  • 0
    total downloads
  • 1
    views this month
  • 0
    downloads this month

Export as