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

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

Authors: Stefanov, Valeri T. and Szpankowski, Wojciech

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.


Source : oai:HAL:hal-00966498v1
Volume: Vol. 9 no. 1
Section: Analysis of Algorithms
Published on: January 1, 2007
Submitted on: March 26, 2015
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]


Share

Browsing statistics

This page has been seen 64 times.
This article's PDF has been downloaded 85 times.