Poisson Approximation for the Non-Overlapping Appearances of Several Words in Markov Chains

Abstract

Let X₁, …, X_n be a sequence of r.v.s produced by a stationary Markov chain with state space an alphabet Ω = {ω₁, …, ω_q}, q [ges ] 2. We consider a set of words {A₁, …, A_r}, r [ges ] 2, with letters from the alphabet Ω. We allow the words to have self-overlaps as well as overlaps between them. Let [Escr ] denote the event of the appearance of a word from the set {A₁, …, A_r} at a given position. Moreover, define by N the number of non-overlapping (competing renewal) appearances of [Escr ] in the sequence X₁, …, X_n. We derive a bound on the total variation distance between the distribution of N and a Poisson distribution with parameter [ ]N. The Stein–Chen method and combinatorial arguments concerning the structure of words are employed. As a corollary, we obtain an analogous result for the i.i.d. case. Furthermore, we prove that, under quite general conditions, the r.v. N converges in distribution to a Poisson r.v. A numerical example is presented to illustrate the performance of the bound in the Markov case.