License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2016.39
URN: urn:nbn:de:0030-drops-68096
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6809/
Go to the corresponding LIPIcs Volume Portal

Jin, Kai

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

pdf-format:
LIPIcs-ISAAC-2016-39.pdf (0.5 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{jin:LIPIcs:2016:6809,
  author =	{Kai Jin},
  title =	{{Computing the Pattern Waiting Time: A Revisit of the Intuitive Approach}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{39:1--39:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Seok-Hee Hong},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6809},
  URN =		{urn:nbn:de:0030-drops-68096},
  doi =		{10.4230/LIPIcs.ISAAC.2016.39},
  annote =	{Keywords: Pattern Occurrence, Waiting Time, Penney’s Game, Markov Chain}
}

Keywords: Pattern Occurrence, Waiting Time, Penney’s Game, Markov Chain
Collection: 27th International Symposium on Algorithms and Computation (ISAAC 2016)
Issue Date: 2016
Date of publication: 07.12.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI