License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2022.9
URN: urn:nbn:de:0030-drops-170728
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17072/
Darwin, Oscar ;
Kiefer, Stefan
On the Sequential Probability Ratio Test in Hidden Markov Models
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.
BibTeX - Entry
@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/opus/volltexte/2022/17072},
URN = {urn:nbn:de:0030-drops-170728},
doi = {10.4230/LIPIcs.CONCUR.2022.9},
annote = {Keywords: Markov chains, hidden Markov models, probabilistic systems, verification}
}
|
Keywords: |
|
Markov chains, hidden Markov models, probabilistic systems, verification |
|
Collection: |
|
33rd International Conference on Concurrency Theory (CONCUR 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
06.09.2022 |
