https://hal.inria.fr/hal-00966498Stefanov, Valeri T.Valeri T.StefanovSchool of Mathematics and Statistics [Crawley, Perth] - UWA - The University of Western AustraliaSzpankowski, WojciechWojciechSzpankowskiDepartment of Computer Science [Purdue] - Purdue University [West Lafayette]Waiting time distributions for pattern occurrence in a constrained sequenceHAL CCSD2007[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]Inria Sophia Antipolis-MÃ©diterranÃ©e / I3s, Service Ist2014-03-26 16:59:112017-11-29 10:26:162014-03-27 13:34:33enJournal articleshttps://hal.inria.fr/hal-00966498/document10.46298/dmtcs.382application/pdf1A 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.