Skip to Main content Skip to Navigation
Journal articles

Waiting time distributions for pattern occurrence in a constrained sequence

Abstract : 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.
Document type :
Journal articles
Complete list of metadata

Cited literature [30 references]  Display  Hide  Download
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s Connect in order to contact the contributor
Submitted on : Wednesday, March 26, 2014 - 4:59:11 PM
Last modification on : Wednesday, November 29, 2017 - 10:26:16 AM
Long-term archiving on: : Thursday, June 26, 2014 - 11:50:25 AM


Files produced by the author(s)




Valeri T. Stefanov, Wojciech Szpankowski. Waiting time distributions for pattern occurrence in a constrained sequence. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2007, Vol. 9 no. 1 (1), pp.305--320. ⟨10.46298/dmtcs.382⟩. ⟨hal-00966498⟩



Record views


Files downloads