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

From MaRDI portal
Revision as of 12:43, 18 July 2023 by Importer (talk | contribs) (‎Created a new Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
Distributions of runs and consecutive systems on directed trees
scientific article

    Statements

    Distributions of runs and consecutive systems on directed trees (English)
    0 references
    0 references
    19 November 2000
    0 references
    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.
    0 references
    runs of random sequences
    0 references
    enumerative combinatorics
    0 references
    consecutive-\(k\)-out-of-\(n\):\(F\) systems
    0 references

    Identifiers