File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Computing the Pattern Waiting Time: A Revisit of the Intuitive Approach

TitleComputing the Pattern Waiting Time: A Revisit of the Intuitive Approach
Authors
Issue Date2016
PublisherSchloss Dagstuhl--Leibniz-Zentrum fuer Informatik.
Citation
27th International Symposium on Algorithms and Computation (ISAAC 2016), v. 64, p. 39:1--39:12 How to Cite?
AbstractWe 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.
Persistent Identifierhttp://hdl.handle.net/10722/247692
ISSN

 

DC FieldValueLanguage
dc.contributor.authorJin, K-
dc.date.accessioned2017-10-18T08:31:07Z-
dc.date.available2017-10-18T08:31:07Z-
dc.date.issued2016-
dc.identifier.citation27th International Symposium on Algorithms and Computation (ISAAC 2016), v. 64, p. 39:1--39:12-
dc.identifier.issn9783959770262-
dc.identifier.urihttp://hdl.handle.net/10722/247692-
dc.description.abstractWe 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.-
dc.languageeng-
dc.publisherSchloss Dagstuhl--Leibniz-Zentrum fuer Informatik. -
dc.relation.ispartof27th International Symposium on Algorithms and Computation (ISAAC 2016)-
dc.titleComputing the Pattern Waiting Time: A Revisit of the Intuitive Approach-
dc.typeConference_Paper-
dc.identifier.emailJin, K: cskaijin@hku.hk-
dc.identifier.doi10.4230/LIPIcs.ISAAC.2016.39-
dc.identifier.hkuros282119-
dc.identifier.volume64-
dc.identifier.spage39:1-
dc.publisher.placeDagstuhl, Germany-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats