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

Source abstract

Let X 1 , …, X n be a sequence of r.v.s produced by a stationary Markov chain with state space an alphabet Ω = {ω 1 , …, ω q }, q [ges ] 2. We consider a set of words { A 1 , …, 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 1 , …, A r } at a given position. Moreover, define by N the number of non-overlapping (competing renewal) appearances of [Escr ] in the sequence X 1 , …, 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.