2026-07-21T12:28:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6809 2024-03-06T10:38:56Z ddc:004 open_access

Computing the Pattern Waiting Time: A Revisit of the Intuitive Approach Jin, Kai Pattern Occurrence Waiting Time Penney’s Game Markov Chain We revisit the waiting time of patterns in repeated independent experiments. We show that the most intuitive approach for computing the waiting time, which reduces it to computing the stopping time of a Markov chain, is optimum from the perspective of computational complexity. For the single pattern case, this approach requires us to solve a system of m linear equations, where m denotes the length of the pattern. We show that this system can be solved in O(m + n) time, where n denotes the number of possible outcomes of each single experiment. The main procedure only costs O(m) time, while a preprocessing rocedure costs O(m + n) time. For the multiple pattern case, our approach is as efficient as the one given by Li [Ann. Prob., 1980]. Our method has several advantages over other methods. First, it extends to compute the variance or even higher moment of the waiting time for the single pattern case. Second, it is more intuitive and does not entail tedious mathematics and heavy probability theory. Our main result (Theorem 2) might be of independent interest to the theory of linear equations. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kai Jin 2016 Is Part Of LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2016.39 urn:nbn:de:0030-drops-68096 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.39 eng https://creativecommons.org/licenses/by/3.0/legalcode