Developments of the Markov chain approach within the distribution theory of runs

Recently, Alexandrou, Fu and Koutras showed how to deal with the distribution of many run and scan statistics using the so-called finite Markov chain imbedding approach. This paper shows how such an approach may be used also to deal with the distribution of a more general statistic (called window statistic) which is defined as the number of the times that an nz-length subsequence of an arbitrary type appears in a sequence of R independent and discrete random variables also not identically distributed. Then, on the basis of this approach, some algorithms are proposed. They allow one to compute: (i) the distribution of a window statistic even in presence of rather large values of m and R; (ii) just the probability of never observing a subsequence of a certain kind even for rather large values of m and any R; (iii) the expected waiting time till a subsequence of a certain kind appears. Therefore, as will be shown by some examples, these algorithms make the approach useful within many fields such as biology or quality control. (C) 2001 Elsevier Science B.V. All rights reserved.