Distributions of Runs and Scans on Higher-Order Markov Trees

In this article, we consider the distributions of the number of success runs of specified length and scans on a higher-order Markov tree under three different enumeration schemes (the non overlapping, the at least, and the overlapping scheme). Recursive formulae for the evaluation of their probability generating functions are established. We provide a proper framework for extending the exact distribution theory of runs and scans from based on sequences to based on directed trees. Some numerical results for the run and scan statistics are given in order to illustrate the computational aspects and the feasibility of our theoretical results. Finally, two special reliability systems are considered, which are closely related to our general results.