Distributions of runs and consecutive systems on directed trees (Q1300754)

During the last 60 years several authors have developed the exact distribution theory of runs of random sequences using a number of methods. In particular, the reviewer and \textit{A. A. Muwafi} [Fibonacci Q. 20, 28-32 (1982; Zbl 0476.60008)] introduced an innovating approach for this problem, based on enumerative combinatorics, \textit{M. Ebneshahrashoob} and \textit{M. Sobel} [Stat. Probab. Lett. 9, No. 1, 5-11 (1990; Zbl 0695.60016)] introduced the powerful method of conditional pgf's, and \textit{J. C. Fu} and \textit{M. V. Koutras} [J. Am. Stat. Assoc. 89, No. 427, 1050-1058 (1994; Zbl 0806.60011)] introduced the method of Markov chain imbedding. Two of the most simple and interesting applications of this theory are the derivations of the failure probability of consecutive-\(k\)-out-of-\(n\):\(F\) systems and \(m\)-consecutive-\(k\)-out-of-\(n\):\(F\) systems [see, e.g., the reviewer, in: Fibonacci numbers and their applications. Math. Appl., D. Reidel Publ. Co. 28, 203-227 (1986; Zbl 0602.60023), and \textit{M. Chao} et al., IEEE Trans. Reliability 40, 120-127 (1995)]. Presently, the author derives recurrences for the pgf's of runs on directed trees and applies them in studying the lifetime of consecutive systems. More precisely, let \(T\) be a directed tree with all its edges directed away from its root, and denote the latter by \(v_0\). Let \(V\) be the set of vertices of \(T\), and let \(\{X_v\), \(v\in V\}\) be a given collection of \(\{0,1\}\)-valued random variables. Assume that \(\{X_v\), \(v\in V\}\) has the directed Markov distribution [see, e.g., \textit{S. L. Lauritzen}, ``Graphical models'' (1998; Zbl 0907.62001)], with the initial distribution at the root \(P(X_{v_0}= 1)= p= 1-q\) and the conditional probabilities \(P(X_v= 1\mid X_{p\alpha(v)}= 1)= p_1= 1-q_1\) and \(P(X_v= 1\mid X_{p\alpha(v)}= 0)= p_0= 1- q_0\), for each vertex \(v\) except for the root, where \(p\alpha (v)\) denotes the parent of the vertex \(v\). Then, the collection of the random variables \(\{X_v\), \(v\in V\}\) is often called a Markov tree. Fix any vertex \(v\) except for the root, and suppose that it has \(\alpha(v)\) ancestors \(v^1, v^2,\dots, v^{\alpha(v)}\) with \(p\alpha (v^j)= v^{j+1}\) for \(j= 1, 2,\dots, \alpha(v)- 1\). Assume that the vertex \(v\) has \(c(v)\) children \(c_1, c_2,\dots, c_{c(v)}\). Denote by \(T_v\) the subtree which consists of the vertex \(v\) (the root of the subtree) and the descendants of \(v\), and let \(V_v\) denote the set of vertices of \(T_v\). Furthermore, let \(\varphi_{v_0} (t)\) be the pgf of the distribution of the number of non-overlapping ``1''-runs of length \(k\) along the direction in \(\{X_v\), \(v\in V\}\). For every vertex \(v\) except for the root \(v_0\), let \(\varphi_v^0 (t)\) be the pgf of the conditional distribution of the number of non-overlapping ``1''-runs of length \(k\) along the direction in \(\{X_w\), \(w\in V_v\}\) given that \(X_{p\alpha(v)}= 0\), and let \(\psi_v^0 (t)\) be the pgf of the conditional distribution of the number of non-overlapping ``1''-runs of length \(k\) along the direction in \(\{X_w\), \(w\in V_v\}\) given that at the vertex \(p\alpha(v)\) a ``1''-run of length \(k\) along this direction is observed. Finally, for \(I= 1, 2,\dots\), \(\min \{(k-1), \alpha(v)\}\), let \(\varphi^I_v(t)\) be the pgf of the conditional distribution of the number of non-overlapping ``1''-runs of length \(k\) along the direction in \(\{X_w\), \(w\in V_v\}\) given that at the vertex \(p\alpha(v)\) a ``1''-run of length \(I\) along this direction is observed. The main result, Theorem 2.1, consists of recurrences for the above-mentioned pgf's and provides a feasible algorithm for computations. As a simple illustration, an example is given of a specific directed tree in which the exact pgf of the distribution (and the distribution itself) of the number of ``1''-runs of length 3 is derived. In addition, the author defines and studies, via recurrences of pgf's, consecutive-\(k\)-out-of-\(n\):\(F\) systems on directed trees.