DROPS

Document

DOI: 10.4230/LIPIcs.CONCUR.2022.9

On the Sequential Probability Ratio Test in Hidden Markov Models

Authors: Oscar Darwin and Stefan Kiefer

Published in: LIPIcs, Volume 243, 33rd International Conference on Concurrency Theory (CONCUR 2022)

Abstract

We consider the Sequential Probability Ratio Test applied to Hidden Markov Models. Given two Hidden Markov Models and a sequence of observations generated by one of them, the Sequential Probability Ratio Test attempts to decide which model produced the sequence. We show relationships between the execution time of such an algorithm and Lyapunov exponents of random matrix systems. Further, we give complexity results about the execution time taken by the Sequential Probability Ratio Test.

Cite as

Oscar Darwin and Stefan Kiefer. On the Sequential Probability Ratio Test in Hidden Markov Models. In 33rd International Conference on Concurrency Theory (CONCUR 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 243, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{darwin_et_al:LIPIcs.CONCUR.2022.9,
  author =	{Darwin, Oscar and Kiefer, Stefan},
  title =	{{On the Sequential Probability Ratio Test in Hidden Markov Models}},
  booktitle =	{33rd International Conference on Concurrency Theory (CONCUR 2022)},
  pages =	{9:1--9:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-246-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{243},
  editor =	{Klin, Bartek and Lasota, S{\l}awomir and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2022.9},
  URN =		{urn:nbn:de:0030-drops-170728},
  doi =		{10.4230/LIPIcs.CONCUR.2022.9},
  annote =	{Keywords: Markov chains, hidden Markov models, probabilistic systems, verification}
}

Document

DOI: 10.4230/LIPIcs.FSTTCS.2020.43

Equivalence of Hidden Markov Models with Continuous Observations

Authors: Oscar Darwin and Stefan Kiefer

Published in: LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)

Abstract

We consider Hidden Markov Models that emit sequences of observations that are drawn from continuous distributions. For example, such a model may emit a sequence of numbers, each of which is drawn from a uniform distribution, but the support of the uniform distribution depends on the state of the Hidden Markov Model. Such models generalise the more common version where each observation is drawn from a finite alphabet. We prove that one can determine in polynomial time whether two Hidden Markov Models with continuous observations are equivalent.

Cite as

Oscar Darwin and Stefan Kiefer. Equivalence of Hidden Markov Models with Continuous Observations. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 43:1-43:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{darwin_et_al:LIPIcs.FSTTCS.2020.43,
  author =	{Darwin, Oscar and Kiefer, Stefan},
  title =	{{Equivalence of Hidden Markov Models with Continuous Observations}},
  booktitle =	{40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)},
  pages =	{43:1--43:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-174-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{182},
  editor =	{Saxena, Nitin and Simon, Sunil},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.43},
  URN =		{urn:nbn:de:0030-drops-132845},
  doi =		{10.4230/LIPIcs.FSTTCS.2020.43},
  annote =	{Keywords: Markov chains, equivalence, probabilistic systems, verification}
}

Search Results

Documents authored by Darwin, Oscar

On the Sequential Probability Ratio Test in Hidden Markov Models

Abstract

Cite as

Equivalence of Hidden Markov Models with Continuous Observations

Abstract

Cite as

Thanks for your feedback!

Could not send message