File Download
  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
KeywordsMarkov chain
Pattern occurrence
Penney's game
Waiting time
Issue Date2016
PublisherSchloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Dagstuhl Publishing. The Proceedings' web site is located at hhttp://www.dagstuhl.de/publikationen/lipics/
Citation
27th International Symposium on Algorithms and Computation (ISAAC 2016), Sydney, Australia, 12-14 December 2016. In Seok-Hee Hong (ed.), LIPICS - Leibniz International Proceedings in Informatics, 2016, v. 64, article no. 39, 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.
DescriptionSession 8B: Pattern Matching/String Algorithm
Persistent Identifierhttp://hdl.handle.net/10722/247692
ISBN
ISSN
2023 SCImago Journal Rankings: 0.796

 

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), Sydney, Australia, 12-14 December 2016. In Seok-Hee Hong (ed.), LIPICS - Leibniz International Proceedings in Informatics, 2016, v. 64, article no. 39, p. 39:1-39:12-
dc.identifier.isbn978-3-95977-026-2-
dc.identifier.issn1868-8969-
dc.identifier.urihttp://hdl.handle.net/10722/247692-
dc.descriptionSession 8B: Pattern Matching/String Algorithm-
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 GmbH, Dagstuhl Publishing. The Proceedings' web site is located at hhttp://www.dagstuhl.de/publikationen/lipics/-
dc.relation.ispartofLIPICS - Leibniz International Proceedings in Informatics-
dc.subjectMarkov chain-
dc.subjectPattern occurrence-
dc.subjectPenney's game-
dc.subjectWaiting time-
dc.titleComputing the Pattern Waiting Time: A Revisit of the Intuitive Approach-
dc.typeConference_Paper-
dc.identifier.emailJin, K: cskaijin@hku.hk-
dc.description.naturepublished_or_final_version-
dc.identifier.doi10.4230/LIPIcs.ISAAC.2016.39-
dc.identifier.scopuseid_2-s2.0-85010767438-
dc.identifier.hkuros282119-
dc.identifier.volume64-
dc.identifier.spage39:1-
dc.identifier.epage39:12-
dc.publisher.placeSaarbrücken/Wadern, Germany-
dc.identifier.issnl1868-8969-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats