Distributions of Numbers of Success Runs of Fixed Length in Markov Dependent Trials

Let {Z_n, n 1} be a time-homogeneous {0, 1}-valued Markov chain, and let N_n be a random variable denoting the number of runs of "1" of length k in the first n trials. In this article we conduct a systematic study of N_n by establishing formulae for the evaluation of its probability generating function, probability mass function and moments. This is done in three different enumeration schemes for counting runs of length k, the "non-overlapping", the "overlapping" and the "at least" scheme. In the special case of i.i.d. trials several new results are established.