2026-07-21T19:27:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17072 2024-03-06T10:58:40Z ddc:004 open_access

On the Sequential Probability Ratio Test in Hidden Markov Models Darwin, Oscar Kiefer, Stefan Markov chains hidden Markov models probabilistic systems verification 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Oscar Darwin and Stefan Kiefer 2022 Is Part Of LIPIcs, Volume 243, 33rd International Conference on Concurrency Theory (CONCUR 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CONCUR.2022.9 urn:nbn:de:0030-drops-170728 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2022.9 eng https://creativecommons.org/licenses/by/4.0/legalcode