Valeri T. Stefanov ; Wojciech Szpankowski - Waiting time distributions for pattern occurrence in a constrained sequence

dmtcs:382 - Discrete Mathematics & Theoretical Computer Science, January 1, 2007, Vol. 9 no. 1 - https://doi.org/10.46298/dmtcs.382
Waiting time distributions for pattern occurrence in a constrained sequence

Authors: Valeri T. Stefanov 1; Wojciech Szpankowski 2

  • 1 School of Mathematics and Statistics [Crawley, Perth]
  • 2 Department of Computer Science [Purdue]

A binary sequence of zeros and ones is called a (d; k)-sequence if it does not contain runs of zeros of length either lessthan d or greater than k, where d and k are arbitrary, but fixed, non-negative integers and d < k. Such sequences find requires that (d; k)-sequences do not contain a specific pattern w. Therefore, distribution results concerning pattern occurrence in (d; k)-sequences are of interest. In this paper we study the distribution of the waiting time until the r-th occurrence of a pattern w in a random (d; k)-sequence generated by a Markov source. Numerical examples are also provided.

https://doi.org/10.46298/dmtcs.382
Source: HAL:hal-00966498v1
Volume: Vol. 9 no. 1
Section: Analysis of Algorithms
Published on: January 1, 2007
Imported on: March 26, 2015
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]
Funding:
    Source : OpenAIRE Graph
  • Analytic Information Theory, Combinatorics, and Algorithmics: The Precise Redundancy and Related Problems; Funder: National Science Foundation; Code: 0208709
  • Collaborative Research: Nonlinear Equations Arising in Information Theory and Computer Sciences; Funder: National Science Foundation; Code: 0503742
  • Crossroads of Information Theory and Computer Science: Analytic Algorithmics, Combinatorics, and Information Theory; Funder: National Science Foundation; Code: 0513636

1 Document citing this article

Share and export

Consultation statistics

This page has been seen 648 times.
This article's PDF has been downloaded 224 times.