On the total variation distance of labelled Markov chains

DOI10.1145/2603088.2603099MaRDI QIDQ4635617zbMATH OpenOpenAlexFDO

Authors Taolue Chen, Stefan Kiefer

Publication date 23 April 2018

Published in Proceedings 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) (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1405.2852

zbMATH Keywords

labelled Markov chainstotal variation distance

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Analysis of algorithms (68W40)

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.

Recommendations

• On computing the total variation distance of hidden Markov models
• On the total variation distance of semi-Markov chains
• Deciding probabilistic bisimilarity distance one for labelled Markov chains
• Linear distances between Markov chains
• EQUIVALENCE OF LABELED MARKOV CHAINS

Cited in

(22)

• The average cost of Markov chains subject to total variation distance uncertainty
• On the metric-based approximate minimization of Markov chains
• A probabilistic calculus of cyber-physical systems
• Complete axiomatization for the total variation distance of Markov chains
• A tale of two diagnoses in probabilistic systems
• On resistance distance of Markov chain and its sum rules
• On the total variation distance of semi-Markov chains
• On the relationship between bisimulation and trace equivalence in an approximate probabilistic context
• EQUIVALENCE OF LABELED MARKOV CHAINS
• Converging from branching to linear metrics on Markov chains
• Linear distances between Markov chains
• On computing the total variation distance of hidden Markov models
• scientific article; zbMATH DE number 7625198 (Why is no real title available?)
• The big-O problem for labelled Markov chains and weighted automata
• The big-O problem
• Asymmetric Distances for Approximate Differential Privacy
• Metrics for labelled Markov processes
• Deciding probabilistic bisimilarity distance one for labelled Markov chains
• Explainability of probabilistic bisimilarity distances for labelled Markov chains
• Probabilistic verification of diagnosability for a certain class of timed stochastic systems
• Comparing labelled Markov decision processes
• Accurate approximate diagnosis of (controllable) stochastic systems

This page was built for publication: On the total variation distance of labelled Markov chains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4635617)