# A Formula for the Reliability of ad-Dimensional Consecutive-k-out-of-n:F System

Authors: Simon Cowell
Journal: International Journal of Combinatorics
 (2015)

---

## Abstract

We derive a formula for the reliability of ad-dimensional consecutive-k-out-of-n:F system, that is, a formula for the probability that an n1×⋯×nd array whose entries are (independently of each other) 0 with probability p and 1 with probability q=1-p does not include a contiguous s1×⋯×sd subarray whose every entry is 1.


---

## Body

## 1. Introduction

Consider a pipeline punctuated by several pumping stations. Suppose the pumping stations are redundant in that if one of them fails, then its predecessor will be strong enough to pump the fluid past it to the next pumping station. Perhaps each pump will even be able to compensate for the failure of its successor and its successor’s successor but perhaps not for the failure of the first 3 pumping stations in the chain of its successors. In this case, the system fails if and only if among the sequence of pumping stations there exists a consecutive run of 3 or more failed pumping stations. This is an example of what is known as a consecutive-k-out-of-n:F system.Suppose that such a system havingn nodes fails if and only if k consecutive nodes fail, and suppose that any given node in the system works correctly with probability p∈[0,1], independently of the other nodes. Then the probability that any given node fails is q=1-p. Thereliability of the system is the probability R(k,n;q) that the system does not fail. Then R(k,n;q)=1-P(k,n;q), where P(k,n;q) is the probability that the sequence of n nodes includes a contiguous interval of k or more failed nodes. Here we are using notation as in [1].As noted in [1], the concept of the reliability of a consecutive system was introduced to Engineering by Kontoleon in 1980 [2]. In the following year Chiang and Niu [3] discussed some applications of consecutive systems. The concept has been generalised in several directions, for instance, to systems deemed to have failed if and only if they include k consecutive failed componentsorf failed components [4], k consecutive components of which at least r have failed [5], and at least m nonoverlapping runs of k consecutive failed components [6]. In 2001 Chang et al. published a book on the subject [7]. Four reviews are also available [8–11].An exact formula forR(k,n;q) first appeared in [12]. de Moivre’s approach depends on deriving the generating function (see [13]) for P(k,n;q). This work has been rephrased in a modern style in [14]. Much later a different exact formula for R(k,n;q) using Markov chains was found [15–17].Both of these exact formulae forR(k,n;q) are difficult to use in Engineering, where values of k and n may be very large. Efficient algorithms have been found [18, 19], but even with modern computing resources, evaluating the formulae takes a lot of time and memory. This problem has been addressed at length in the study of upper and lower bounds for R(k,n;q). Such bounds have been found which are close approximations to the exact value of R(k,n;q) and which are also much easier to evaluate than the exact value of R(k,n;q). In [1, 20, 21] the authors compare many such results from the 1980s to the present day.Dăuş and Beiu were the first to use de Moivre’s original formula to derive upper and lower bounds forR(k,n;q). As shown in [1] this method compares very favourably with the previous upper and lower bounds, especially for small q, and also with the exact algorithms given in [18, 19] (using their bounds is about 100 times faster than the algorithm from [18] and 1000 times faster than the algorithm from [19]).One possible extension to higher dimensions is as follows. Givend∈N and n1,n2,…,nd∈N, suppose that some system is represented by an n1×n2×⋯×nd array of 0s and 1s. Suppose that each node in the array is 0 with probability p∈[0,1] and is 1 with probability q=1-p, independently of the other nodes. Suppose that s1,s2,…,sd∈N are given, with sr≤nr for each r, and suppose that the system is deemed to have failed if and only if the d-dimensional array includes a contiguous s1×s2×⋯×sd subarray of 1s. Define the reliability of the system as the probability R(s1,…,sd,n1,…,nd;q) that the system does not fail, and let P(s1,…,sd,n1,…,nd;q)=1-R(s1,…,sd,n1,…,nd;q), so that P(s1,…,sd,n1,…,nd;q) is the probability that the array includes a contiguous s1×s2×⋯×sd subarray of 1s.Let us survey in chronological order some recent papers dealing with the higher dimensional case. In [22] the 2-dimensional special case R(s,s,n,n;q) is treated. Upper and lower bounds are found by reducing to the 1-dimensional case. Using empirical approximations to the exact value, R(s,s,n,n;q) is plotted as a function of q for n=5 and s=2,3, and 4, for n=10 and s=2,4,6, and 8, and for n=50 and s=2,5,10, and 20. The authors do not attempt to find an explicit expression for R(s,s,n,n;q). In [23] the 2-dimensional case is considered, for R(s1,s2,n1,n2;q) with (s1,s2)∈{1,n1}×{1,n2}. Exact formulae are derived by comparison with the 1-dimensional case. Similar results are also given for a cylindrical version of the 2-dimensional array. The 2-dimensional case R(s,s,n,n;q) of [22] is revisited in [24]. Again, upper and lower bounds are given, but in the more general case where the probabilities of distinct nodes of the system failing are not necessarily equal. For the general 2-dimensional case R(s1,s2,n1,n2;q), recursive formulae for the exact reliability have been given by Yamamoto and Miyakawa [25] and also by Noguchi et al. [26]. The result presented herein is distinct from their work, in that we give a closed-form formula for the exact reliability as a polynomial in q, for a general system, of arbitrary dimension. The 3-dimensional case is treated in [27], where exact formulae for the reliability are given in special cases analogous to those studied in [23].In the present paper we derive general closed-form exact formulae forR(s1,…,sd,n1,…,nd;q) and for P(s1,…,sd,n1,…,nd;q), where the dimension d∈N is arbitrary. As far as the author knows, no such formulae were known before for d>1, even in the case d=2. Indeed, in [24] the authors write “It is very difficult (probably impossible) to derive simple explicit formulas for the reliability of a general 2D-consecutive-k-out-n:F system.”


## 2. Results

Theorem 1 (main result).
Let the terms(1)d,s1,…,sd,n1,…nd,p,q,Rs1,…,sd,n1,…,nd;qPs1,…,sd,n1,…,nd;qbe as in the Introduction, and let(2)E=∏r=1d1,…,nr-sr+1.Then(3)Rs1,…,sd,n1,…,nd;q=1+∑J∈PE∖∅-1J∏J′∈PJ∖∅exp⁡-1J′ln⁡1q∏r=1dmax⁡0,sr-maxe∈J′⁡er-mine∈J′⁡er,(4)Ps1,…,sd,n1,…,nd;q=-∑J∈PE∖∅-1J∏J′∈PJ∖∅exp⁡-1J′ln⁡1q∏r=1dmax⁡0,sr-maxe∈J′⁡er-mine∈J′⁡er,where P(A) denotes the power set of the set A, that is, the set of subsets of A, and ∅ denotes the empty set.Theorem1 implies the following combinatorial result.Corollary 2.
With all terms as in Theorem1, the number a(s1,…,sd,n1,…,nd) of failed systems among the 2∏r=1d‍nr possible systems is (5)as1,…,sd,n1,…,nd=-2∏r=1dnr∑J∈PE∖∅-1J∏J′∈PJ∖∅exp⁡-1J′ln⁡2∏r=1dmax⁡0,sr-maxe∈J′⁡er-mine∈J′⁡er.Proof.
In casep=q=1/2, all possible systems occur with equal probability, so the probability measure on the power set of the set of all systems becomes the counting measure, divided by a factor of 2∏r=1d‍nr.Settingd=1, n1=n, and s1=2,3, and 4 in Corollary 2 yields the sequences [28], [29], and [30], respectively. Setting d=2, n1=n2=n, and s1=s2=2 in Corollary 2 yields the sequence [31], whose complementary sequence is [32].Proof of Theorem1.
Call a systeme an “elementary failure case” if and only if it includes a contiguous s1×⋯×sd subarray of 1s, and its other elements are all 0. We identify the set of all elementary failure cases e with the set E, according to the rule(6)e⟷e1,…,edif and only if the (i1,…,id)th element of e is 1 precisely when, for all r∈{1,…,d},(7)er≤ir≤er+sr-1.For example, in the two-dimensional case, we identify an elementary failure case with the indices (e1,e2) of the top left corner of its contiguous subrectangle of 1s. Denote by G the simple acyclic directed graph whose vertices are all the possible systems and in which system b is a direct successor of system a if and only if b is obtained from a by changing a single 0 element to 1. Then the failed systems f in G are precisely those vertices having some elementary failure case e∈E as an ancestor (including the possibility that f=e). Therefore if F denotes the set of all failed systems f (in terms of probability, F is the event that the system fails), then(8)F=⋃e∈Ethe  set  of  descendents  ofe,where by “b is a descendent of a” we mean to include the possibility that b=a. Then (9)Ps1,…,sd,n1,…,nd;q=PF=P⋃e∈Ethe  set  of  descendents  ofe=∑J∈PE∖∅-1J+1·P⋂e∈Jthe  set  of  descendents  ofe,by the Inclusion-Exclusion Principle for the probability measure on the power set of the set of all possible systems. But(10)⋂e∈Jthe  set  of  descendents  ofe=the  set  of  descendents  of  hcdJ,where by hcd(K) we mean the highest common descendent of any given set K of vertices in G. That is, in the partial order on the vertices of G defined by a≲b precisely when a is an ancestor of b, hcd(K) is the least upper bound of K. Moreover,(11)hcdJ=⋃e∈Je,where by the union of several n1×⋯×nd systems we mean the system whose generic element is 1 if and only if the corresponding element in at least one of those systems is also 1. Thus(12)Ps1,…,sd,n1,…,nd;q=∑J∈PE∖∅-1J+1·P⋂e∈Jthe  set  of  descendents  ofe=∑J∈PE∖∅-1J+1·Pthesetofdescendentsof⋃e∈Je.However, for any vertex a of G, (13)Pthe  set  of  descendents  ofa=∑bis  a  descendent  ofaPb=∑bis  a  descendent  ofapn1n2⋯nd-kqk,where k=k(b) is the number of failed nodes in the system b. Gathering like powers of q in the above sum, we have (14)Pthe  set  of  descendents  ofa=∑k=kan1n2⋯ndn1n2⋯nd-kak-kapn1n2⋯nd-kqk=qka∑k=kan1n2⋯ndn1n2⋯nd-kak-kapn1n2⋯nd-kqk-ka=qka∑j=0n1n2⋯nd-kan1n2⋯nd-kajpn1n2⋯nd-ka-jqj=qkap+qn1n2⋯nd-ka=qka.That is, for any vertex a of G,(15)Pthesetofdescendentsofa=qka,where k(a) denotes the number of failed nodes in the system a. Therefore from (12) we obtain(16)Ps1,…sd,n1,…nd;q=∑J∈PE∖∅-1J+1·Pthe  set  of  descendents  of⋃e∈Je=∑J∈PE∖∅-1J+1qk⋃e∈Je.The next task is to compute the number k⋃e∈J‍e of 1s in the system ⋃e∈J‍e, where J is some nonempty subset of the set E of elementary failure cases e. We use the Inclusion-Exclusion Principle again, this time for the counting measure on the power set of the set of elements of a system, to obtain(17)k⋃e∈Je=∑J′∈PJ∖∅-1J′+1k⋂e∈J′e.Each elementary failure case consists entirely of 0s except for a contiguous s1×⋯×sd subarray of 1s. Therefore ⋂e∈J′e‍ also consists entirely of 0s except for a (possibly empty) contiguous subarray of dimensions t1×⋯×td, where, for each r∈{1,…d}, (18)tr=max⁡0,mine∈J′⁡er+sr-1-maxe∈J′⁡er+1=max⁡0,sr-maxe∈J′⁡er-mine∈J′⁡er.The volume of that contiguous t1×⋯×td subarray is equal to k⋂e∈J′e‍; that is,(19)k⋂e∈J′e=∏r=1dtr=∏r=1dmax⁡0,sr-maxe∈J′⁡er-mine∈J′⁡er.Considering (16), (17), and (19), we have (20)Ps1,…,sd,n1,…,nd;q=∑J∈PE∖∅-1J+1qk⋃e∈Je=∑J∈PE∖∅-1J+1exp⁡ln⁡q∑J′∈PJ∖∅-1J′+1k⋂e∈J′e=∑J∈PE∖∅-1J+1exp⁡ln⁡q∑J′∈PJ∖∅-1J′+1∏r=1dmax⁡0,sr-maxe∈J′⁡er-mine∈J′⁡er=-∑J∈PE∖∅-1J∏J′∈PJ∖∅exp⁡-1J′ln⁡1q∏r=1dmax⁡0,sr-maxe∈J′⁡er-mine∈J′⁡er,which proves (4). Equation (3) follows immediately.As an example, we compute the reliabilities of 3 consecutive systems, having dimensions 1, 2, and 3:(21)R1,2;q=1-2q+q2,R1,2,2,3;q=1-4q2+2q3+4q4-4q5+q6,R1,2,3,2,3,4;q=1-8q6+4q8+4q9+4q10-8q11+18q12-16q14-16q15-12q16+40q17+4q18-8q19-8q20-12q21+20q22-8q23+q24.See also Figure1.Figure 1


## 3. Conclusion

We have provided a novel formula for the reliability of a generald-dimensional consecutive-k-out-of-n:F system, as an exact polynomial in q. We believe ours to be the first general exact closed-form formula published for the reliability in d dimensions. This answers an open question in Engineering.



---

*Source: 140909-2015-07-13.xml*