Distinguishing hidden Markov chains

DOI10.1145/2933575.2933608zbMATH Open1401.68086arXiv1507.02314OpenAlexW2963414055MaRDI QIDQ4635862FDOQ4635862

Author name not available (Why is that?)

Publication date: 23 April 2018

Published in: Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Abstract: Hidden Markov Chains (HMCs) are commonly used mathematical models of probabilistic systems. They are employed in various fields such as speech recognition, signal processing, and biological sequence analysis. We consider the problem of distinguishing two given HMCs based on an observation sequence that one of the HMCs generates. More precisely, given two HMCs and an observation sequence, a distinguishing algorithm is expected to identify the HMC that generates the observation sequence. Two HMCs are called distinguishable if for every $varepsilon>0$ there is a distinguishing algorithm whose error probability is less than $varepsilon$. We show that one can decide in polynomial time whether two HMCs are distinguishable. Further, we present and analyze two distinguishing algorithms for distinguishable HMCs. The first algorithm makes a decision after processing a fixed number of observations, and it exhibits two-sided error. The second algorithm processes an unbounded number of observations, but the algorithm has only one-sided error. The error probability, for both algorithms, decays exponentially with the number of processed observations. We also provide an algorithm for distinguishing multiple HMCs. Finally, we discuss an application in stochastic runtime verification.

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

Recommendations

• Formal Techniques for Networked and Distributed Systems - FORTE 2005
• On computing the total variation distance of hidden Markov models
• scientific article; zbMATH DE number 2081009
• Bayesian classification of hidden Markov models
• Distributions associated with general runs and patterns in hidden Markov models

zbMATH Keywords

hidden Markov chainsmonitorslabelled Markov chains

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Cited In (3)

• Runtime monitors for Markov decision processes
• A tale of two diagnoses in probabilistic systems
• Verification of detectability in probabilistic finite automata

This page was built for publication: Distinguishing hidden Markov chains

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