Covering runs in binary Markov sequences

We describe distributions of the lengths of initial, covering, and final runs in binary Markov sequences. For the means and variances, we give exact and asymptotic formulas. We also give the generating functions. We observe that in Markov sequences the probabilities of run lengths do not necessarily decrease as the lengths grow, and hence, the corresponding distributions may be of quite complex form. We investigate conditions under which, due to the Markov property, the probabilities increase as the run lengths do. We consider operator equations which include final runs.
This research was supported by the Russian Foundation for Basic Research, grant 02–01–00946.