2 Search Results for "Darwin, Oscar"

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-dev.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-dev.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}
}
  • Refine by Author
  • 2 Darwin, Oscar
  • 2 Kiefer, Stefan

  • Refine by Classification
  • 2 Mathematics of computing → Stochastic processes
  • 2 Theory of computation → Logic and verification
  • 2 Theory of computation → Random walks and Markov chains

  • Refine by Keyword
  • 2 Markov chains
  • 2 probabilistic systems
  • 2 verification
  • 1 equivalence
  • 1 hidden Markov models

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2020
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact