Distributions of Runs and Scans on Higher-Order Markov Trees

Abstract

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.

Keywords:

• Consecutive system
• Directed tree
• Enumeration schemes
• Graph
• Higher-order Markov tree
• Probability generating function
• Reliability
• Scan
• Success run

Mathematics Subject Classification:

• Primary 60E05
• Secondary 60J10