On the Number of Appearances of a Word in a Sequence of I.I.D. Trials

Let X ₁,...,X _n be a sequence of i.i.d. random variables taking values in an alphabet =₁,...,_q,q 2, with probabilities P(X _a=_i)=p _i,a=1,...,n,i=1,...,q. We consider a fixed h-letter word W=w₁...w_h which is produced under the above scheme. We define by R(W) the number of appearances of W as Renewal (which is equal with the maximum number of non-overlapping appearances) and by N(W) the number of total appearances of W (overlapping ones) in the sequence X _{a 1} a1n under the i.i.d. hypothesis. We derive a bound on the total variation distance between the distribution (R(W)) of the r.v. R(W) and that of a Poisson with parameter E(R(W)). We use the Stein-Chen method and related results from Barbour et al. (1992), as well as, combinatorial results from Schbath (1995b) concerning the periodic structure of the word W. Analogous results are obtained for the total variation distance between the distribution of the r.v. N(W) and that of an appropriate Compound Poisson r.v. Related limit theorems are obtained and via numerical computations our bounds are presented in tables.     

Compound Poisson Approximation for Multiple Runs in a Markov Chain

We consider a sequence X ₁, ..., X _n of r.v.'s generated by a stationary Markov chain with state space A = {0, 1, ..., r}, r 1. We study the overlapping appearances of runs of k _i consecutive i's, for all i = 1, ..., r, in the sequence X ₁,..., X _n. We prove that the number of overlapping appearances of the above multiple runs can be approximated by a Compound Poisson r.v. with compounding distribution a mixture of geometric distributions. As an application of the previous result, we introduce a specific Multiple-failure mode reliability system with Markov dependent components, and provide lower and upper bounds for the reliability of the system.