Intrinsic ordering, combinatorial numbers and reliability engineering

Intrinsic ordering, combinatorial numbers and reliability engineering Luis Gonz´alez∗ Research Institute of Intelligent Systems &Numerical Applications in Engineering, Department of Mathematics, University of Las Palmas de Gran Canaria, Campus de Tafira, 35017 Las Palmas de Gran Canaria, Spain Abstract A new algorithm for evaluating the top event probability of large fault trees (FTs) is presented. This algorithm does not require any previous qualitative analysis of the FT. Indeed, its efficiency is independent of the FT logic, and it only depends on the number nof basic system components and on their failure probabilities. Our method provides exact lower and upper bounds on the top event probability by using new properties of the intrinsic order relation between binary strings. The intrinsic order enables one to select binary n-tuples with large occurrence probabilities without necessity to evaluate them. This drastically reduces the complexity of the problem from exponential (2nbinary n-tuples) to linear (nBoolean variables). Our algorithm is mainly based on a recursive formula for rapidly computing the sum of the occurrence probabilities of all binary n-tuples with weight mwhose 1s are placed among the kright-most positions. This formula, as well as the balance between accuracy and computational cost, is closely related to the famous Pascal’s triangle. Keywords: Reliability engineering modelling; fault tree analysis; top event probability; intrinsic order; intrinsic order graph; Hamming weight ∗Tel.: +34 928458832 Email address: [email protected] (Luis Gonz´alez) Preprint submitted to Applied Mathematical Modelling July 29, 2012 1. Introduction One of the most common techniques for analyzing system safety and reliability is the fault tree analysis (FTA), an extensively used method worldwide, which is mainly based on probability theory and Boolean algebra [1, 2, 3]. Large, complex systems where FTA has been widely applied can be found in many different scientific or engineering areas, such as aeronautics, chemistry and materials, energy resources, mechanics, meteorology and climatology, nuclear physics, robotics, etc. (see, e.g., [4] for an exhaustive list of such subject categories). FTA was first conceived in 1961 by H. A. Watson of Bell Telephone Laboratories to perform a safety evaluation of the Minuteman Launch Control System [5]. The basic idea of FTA is the translation of the failure behavior of a technical system into a visual diagram involving logic gates, i.e., the fault tree (FT) [6]. A FT is a logical representation of the manner in which combinations of failures of the basic components of a system lead to the undesired state of the system, the so-called top event [7, 8]. One of the main topics in FTA is to estimate the failure probability of the whole system –also called the system unavailability, or the top event probability. Many different techniques have been proposed in the literature to evaluate the system unavailability; see, e.g., [6, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21] and the references contained therein. Throughout this paper, we consider complex systems depending on an arbitrarily large number nof statistically independent random Boolean variables x1, . . . , xn. The usual convention is to assign the value 1 or 0 to variable xiif component ifails or works, respectively. So, each one of the binary ntuples of 0s and 1s, u= (u1, . . . , un)∈ {0,1}n, describes the current situation of the nbasic components of the system (failing or working) and, in the following, we shall refer to these binary n-tuples as binary strings, or as system elementary states. Then, using a more precise algebraic terminology, the FT can be described by a stochastic Boolean function Φ : {0,1}n−→ {0,1} (x1, . . . , xn)7→ Φ (x1, . . . , xn) depending on the nbasic variables xiof the system. Assuming that Φ = 1 if the system fails, Φ = 0 otherwise, then the failure probability of the whole system can be evaluated by computing the probability Pr {Φ = 1}. 2 Let us recall that a fault tree is said to be coherent if its structure function Φ satisfies the following two conditions (see, e.g., [22, 23, 24]) (i) Relevance. Each component xiis relevant, i.e., it contributes to the system state. Formally, for all i= 1,2, . . . , n Φ (0i, x)6= Φ (1i, x),for some vector x, where Φ (0i, x) = Φ (x1, . . . , xi−1,0, xi+1, . . . , xn), Φ (1i, x) = Φ (x1, . . . , xi−1,1, xi+1, . . . , xn). (ii) Monotonicity. The system neither transits from a failed state to a good state by the failure of a component, nor transits from a good state to a failed state by the repair of a component. Formally, the structure function Φ is non-decreasing in each variable, i.e., Φ (x)≥Φ (y) if x > y, where x, y ∈ {0,1}n, and x>ymeans that xi≥yifor every component i= 1,2, . . . , n, with xi> yifor some i. When at least one of the two above conditions is not fulfilled, the system is non-coherent. Most of FTA methods for evaluating the top event probability Pr {Φ = 1} are based on the minimal cut set approach [8]. A (minimal) cut set is a (minimal) combination of component failures that leads to the system failure (top event). However, for large, complex FTs it is not possible, in general, to enumerate all its minimal cut sets due to high memory requirements and long computing time, since the number of potential minimal cut sets exponentially increases, in general, with the size of the FTs, that is, with the numbers of their basic events and gates [13]. The main goal of this paper is to present a new algorithm for obtaining exact lower and upper bounds on the top event probability (for both coherent and non-coherent systems), with no need to find the minimal cut sets. Moreover, indeed our method does not require any previous qualitative analysis of the FT to estimate the system unavailability. At the end of this paper, we will explain in detail the characteristics and advantages of our proposed method. At this moment, let us mention that 3 its main advantage, compared with many other techniques proposed in the literature to obtain exact lower and upper bounds on system unavailability, is the following. Our algorithm does not require any knowledge or information (often required by other techniques) about the Boolean (structure) function of the FT. Moreover, we shall prove that it is possible (and easy) to assure a priori the maximum admissible error in the estimation, since this error is independent of the FT to be evaluated, and it only depends on the occurrence probabilities of certain selected binary n-tuples. The bounds on system unavailability can be obtained from the occurrence probabilities of any subset of selected system elementary states. However, the main point is that the accuracy in the estimation (difference between upper and lower bounds) of Pr {Φ = 1}improves at the same time as the sum of the occurrence probabilities of all the selected elementary states increases. Hence, in order to get a good compromise between accuracy and computational cost, we need to select as few binary n-tuples uas possible, with occurrence probabilities Pr {u}as large as possible. For selecting the binary strings uwith large occurrence probabilities, we use a theorem that states new properties related to the intrinsic order criterion (IOC). IOC is a simple, positional criterion that allows us to compare the occurrence probabilities Pr {u},Pr {v}of two given binary n-tuples u, v with no need to evaluate them, simply looking at the relative positions of their 0s and 1s. IOC was first described in [25]: a theoretical paper where the intrinsic ordering is introduced in the context of the evaluation of stochastic Boolean functions. Other theoretical results and practical applications of IOC can be found in [26, 27, 28, 29, 30, 31, 32]. Let us briefly describe the main ideas or techniques presented in these works. In [26], different characterizations as well as necessary conditions and sufficient conditions for the intrinsic order are derived. In [28, 30], we provide two different algorithms for counting and generating all the binary n-tuples which are always more probable (less probable) than a fixed n-tuple u∈ {0,1}n. Based on these algorithms, in [31] we determine, for any fixed binary n-tuple u, all its possible “ranks” (positions) in the list of all the 2nbinary n-tuples, arranged in decreasing order of their occurrence probabilities. The usual representation for the intrinsic order, the so-called intrinsic order graph, is constructed in [29], and some ordertheoretic and graph-theoretic properties of this graph are derived in [32]. All the above commented papers are mainly theoretical, and they do not contain algorithms for evaluating the unavailability of technical systems. An 4 algorithm for estimating the top event probability is given in [27], and it is also based on IOC. The main differences between the algorithm performed in [27] and the one proposed here are the following: (i) The former selects a proper set of binary n-tuples, basically by taking into account the weight (number of 1-bits in the bitstring) and the lexicographic (truth-table) order between the bitstrings. The latter improves this selection strategy by using new properties of the intrinsic order instead of the lexicographic order. This leads to a more efficient algorithm, since the occurrence probabilities of the selected bitstrings are now larger, and thus the number of binary n-tuple probabilities that need to be computed is reduced. (ii) For computing the occurrence probability of each selected binary n-tuple with weight m, the former needs to multiply nfactors, while the latter only needs to multiply m+ 1 factors. This is especially useful, for computational purposes, when the selected binary n-tuples have small weights, which is in general the case in the algorithm proposed in this paper. (iii) For computing the maximum error in the estimation of the system unavailability (so that we can assure the required accuracy), both algorithms evaluate the total sum of the selected binary n-tuple probabilities. However, while the former uses a non-recursive formula for this purpose, the latter uses a recurrence relation, which is computationally more efficient. Moreover, the balance between accuracy and computational cost in our new algorithm is based on the above mentioned recursive formula, which is closely related to the famous Pascal’s triangle. This paper has been organized as follows. Section 2 is devoted to set the assumptions and basic notations used in this work. In Section 3, we present all the required background about the above mentioned deterministic method for estimating the system unavailability and about the intrinsic order relation. Beginning with our new, unpublished results, in Section 4, we state some new properties of the intrinsic order. Section 5 is devoted to present a simple recurrence relation, closely related to the Pascal’s formula, for computing the sums of the selected binary string probabilities. In Section 6, we present our algorithm for estimating the system unavailability, and we illustrate it with a real-life example. Finally, in Section 7 we present our conclusions. 2. Assumptions and notation 2.1. Assumptions (i) The components and system have binary states. 5 (ii) The basic components are non-repairable. (iii) The FT contains only static gates; it is not a dynamic FT. (iv) The basic events are assumed to be mutually statistically independent. (v) The probability of failure of each basic event is given. In addition to the above assumptions, let us mention that the number of basic components and the number of gates of the FT to be solved may be arbitrarily large. Moreover, any event, basic or gate, may appear at multiple locations in the FT (i.e., repeated events are allowed). Finally, our method can be applied to both coherent and non-coherent FTs, and the FT logic may be arbitrarily complex. 2.2. Nomenclature and notation nnumber of basic system components {0,1}nset of all the 2nbinary n-tuples xii-th basic Boolean variable of the system: xi= 1 if component ifails, xi= 0 otherwise xinegation of variable xi pibasic (failure) probability of component i: pi= Pr {xi= 1}, 1 −pi= Pr {xi= 0} qia quotient: qi=pi/(1 −pi), 1 ≤i≤n u= (u1, . . . , un) binary n-tuple describing a system elementary state Mu vthe (2 ×n)-matrix whose first and second row are the binary n-tuples uand v, respectively Pr {u}occurrence probability of system elementary state u Φ Boolean (structure) function describing the FT: Φ = 1 if the system fails, Φ = 0 otherwise Pr {Φ = 1}top event probability or system unavailability C1,C0subsets of the sets of binary n-tuples for which Φ = 1,0, respectively: C1⊆ {u∈ {0,1}n|Φ (u) = 1} C0⊆ {u∈ {0,1}n|Φ (u) = 0} L,Ulower and upper bounds on system unavailability wH(u) Hamming weight of u, i.e., its number of 1-bits: wH(u) = Pn i=1 ui u(10 decimal numbering of binary n-tuple u: 6 u(10 =Pn i=1 2n−iui intrinsic order relation between binary n-tuples .covering relation associated to the intrinsic order Inthe partially ordered set ({0,1}n,) S0occurrence probability of the binary n-tuple (0,...,0): S0= Pr {(0,...,0)}=Qn i=1 (1 −pi) Ck mset of all binary n-tuples with weight mwhose 1s are placed among the kright-most positions Sk msum of probabilities of all binary n-tuples of Ck m required accuracy to estimate system unavailability Cset of selected binary n-tuples used in the algorithm Ttotal number of binary n-tuples used in the algorithm Ssum of occurrence probabilities of all binary n-tuples used in the algorithm A−Bset difference: A−B={x∈A|x /∈B} u+Carithmetic sum of element uand set C: u+C={u+v|v∈C} |·| cardinality of a set 3. Preliminary results As commented in Section 1, our algorithm will provide exact lower and upper bounds on the failure probability Pr {Φ = 1}of an n-component system. In the next subsection, we explain how such bounds can be obtained from any arbitrary subset of the set {0,1}nof all system elementary states. 3.1. Bounds on system unavailability Denoting by pithe failure probability of the i-th system component, i.e., Pr {xi= 1}=pi,Pr {xi= 0}= 1 −pi,1≤i≤n, then, due to the statistical independence between basic components, the occurrence probability of each system elementary state uis given by the expression Pr {u}= Pr {(u1, . . . , un)}= n Y i=1 pui i(1 −pi)1−uifor all u∈ {0,1}n.(3.1) 7 In other words, Eq. (3.1) means that Pr {u}can be simply computed as the product of factors pior 1 −pi, if ui= 1 or ui= 0, respectively. Now, it is well known that the probability of a Boolean function Φ taking value 1 can be exactly computed as the sum of the occurrence probabilities of all system elementary states for which Φ = 1 or, alternatively, as the remainder to 1 of the sum of the occurrence probabilities of all system elementary states for which Φ = 0 [33]. That is, X u∈{0,1}n Φ(u)=1 Pr {u}= Pr {Φ = 1} ≡ 1−Pr {Φ = 0}= 1 −X u∈{0,1}n Φ(u)=0 Pr {u}.(3.2) For small values of the number nof basic system components, Eq. (3.2) enables one to exactly compute the failure probability, Pr {Φ = 1}, of the system. However, for large values of nthis procedure is not feasible in practice because of the exponential nature of the problem. Just think that there are 2nbinary n-tuples of 0s and 1s. To overcome this obstacle, we can obtain lower and upper bounds L,Uon the top event probability, Pr {Φ = 1}, as follows. Let C⊆ {0,1}nbe an arbitrary subset of binary n-tuples (system elementary states), and let C1and C0be the two subsets of Cfor which Φ = 1 and Φ = 0, respectively, i.e., C1={u∈C|Φ (u) = 1}, C0={u∈C|Φ (u) = 0}. Then using Eq. (3.2) we have X u∈C1 Pr {u} ≤ X u∈{0,1}n Φ(u)=1 Pr {u}= Pr {Φ = 1},(3.3) X u∈C0 Pr {u} ≤ X u∈{0,1}n Φ(u)=0 Pr {u}= Pr {Φ = 0}(3.4) and from (3.3) and (3.4) we get the following lower and upper bounds L,U L=X u∈C1 Pr {u} ≤ Pr {Φ = 1} ≡ 1−Pr {Φ = 0} ≤ 1−X u∈C0 Pr {u}=U. (3.5) 8 Note that, for a fixed set Cof binary n-tuples, the above bounds Land Udepend on the Boolean function Φ, because the same happens with the set partition C={u∈C|Φ (u) = 0}∪{u∈C|Φ (u) = 1}=C0∪C1. However, the maximum error in the estimation (difference between upper and lower bounds) U−L= 1−X u∈C0 Pr {u}!−X u∈C1 Pr {u}= 1 −X u∈C0∪C1=C Pr {u}(3.6) is completely independent of the FT logic (i.e., it is the same for any Boolean function Φ), and it only depends on the total sum, Pu∈CPr {u}, of the occurrence probabilities of all the selected binary n-tuples u∈C. More precisely, the accuracy in the estimate of the system unavailability, Pr {Φ = 1}, improves at the same time as the maximum error U−Ldecreases, i.e., at the same time as this total sum, Pu∈CPr {u}, increases, as Eq. (3.6) has shown [27]. Consequently, the main question is how to select the minor number of system elementary states, u∈C, with occurrence probabilities, Pr {u}, as large as possible, in order to minimize the computational cost –by increasing the last sum in Eq. (3.6)– when estimating the system unavailability with an acceptable accuracy, by using Eq. (3.5). Note that the simplest answer to this question, namely ordering the 2n binary n-tuple probabilities is not valid, because of the exponential nature of the problem and the high computational costs in sorting algorithms. To avoid this obstacle, in [25] we have established a simple, positional criterion that allows us to compare two given elementary state probabilities, Pr {u},Pr {v}, without computing them, simply looking at the positions of the 0s and 1s in the n-tuples u, v. This criterion is explained in detail below. 3.2. The intrinsic order In the following, we indistinctly denote the n-tuple u∈ {0,1}nby its binary representation (u1, . . . , un) or by its decimal representation, denoted here by u(10 , and we use the symbol “≡” to indicate the conversion between them, i.e., u= (u1, . . . , un)≡u(10 = n X i=1 2n−iui, 9 Obviously, if uis a binary n-tuple with weight mwhose 1s are placed among the k−1 right-most positions, then uis also a binary n-tuple with weight mwhose 1s are placed among the kright-most positions, i.e., Cm m⊂Cm+1 m⊂ · · · ⊂ Ck−1 m⊂Ck m⊂ · · · ⊂ Cn−1 m⊂Cn m, and thus Sm m< Sm+1 m<· · · < Sk−1 m< Sk m<· · · < Sn−1 m< Sn m. Theorem 4.1. Let n≥1. Then (i)For every binary n-tuple vwith weight m > 0, there exists, at least, one binary n-tuple uwith weight m−1such that uv. (ii)For every binary n-tuple v∈Ck m−Ck−1 m, such that 0< m < k ≤n, there exists, at least, one binary n-tuple u∈Ck−1 msuch that uv. Proof. We give a constructive proof explicitly defining the binary strings u. (i) Let vbe a binary n-tuple with weight m > 0. Choose any index j∈ {1, . . . , n}such that vj= 1. Define uas follows ui=0 if i=j, viif i6=j. In this way, wH(u) = wH(v)−1 = m−1. Moreover, matrix Mu vhas exactly one 0 1column (its j-th one), while its remaining n−1 columns are either 0 0 or 1 1. Hence, Mu vhas no 1 0columns and then, by Theorem 3.1, it satisfies IOC. Therefore, by Definition 3.1, uv. (ii) Let v∈Ck m−Ck−1 m(m<k≤n). Then vis a binary n-tuple with weight mwhose 1s are placed among the kright-most positions, but not among the k−1 right-most positions. Hence, since vn−k+1 is the bit placed at the k-th position from right to left in the n-tuple v, we have vn−k+1 = 1 and ∃j > n −k+ 1 s.t. vj= 0. Define uas follows ui=   0 if i=n−k+ 1, 1 if i=j, viif i6=n−k+ 1, j. 16 In this way, wH(u) = wH(v) = m, and u∈Ck−1 m. Moreover, matrix Mu v has exactly one 1 0column (its j-th one) and exactly one 0 1column (its (n−k+ 1)-th one), while its remaining n−2 columns are either 0 0or 1 1. Hence, the only 1 0column of Mu vis preceded by a corresponding 0 1column (since n−k+1 < j), and thus, by Theorem 3.1, Mu vsatisfies IOC. Therefore, by Definition 3.1, uv. Theorem 4.1 and its proof can be illustrated by Fig. 3, where the digraph of I4(the right-most one in Fig. 2) is depicted using now the binary representation of their nodes, instead of their decimal equivalents. For instance, consider the binary 4-tuple v= (1,1,0,0) ∈ {0,1}4. On one hand, since m=wH(v) = 2 then, according to Theorem 4.1-(i), we can choose, e.g., u= (1,0,0,0), so that wH(u) = 1 and uv. On the other hand, since v= (1,1,0,0) ∈C4 2−C3 2then, according to Theorem 4.1-(ii), we can choose, e.g., u= (0,1,1,0), so that wH(u) = 2, u∈C3 2and uv. (0,0,0,0) | (0,0,0,1) | (0,0,1,0) | (0,0,1,1) (0,1,0,0) | (0,1,0,1) (1,0,0,0) || (0,1,1,0) (1,0,0,1) || (0,1,1,1) (1,0,1,0) | (1,0,1,1) (1,1,0,0) | (1,1,0,1) | (1,1,1,0) | (1,1,1,1) Fig. 3. The intrinsic order graph for n= 4 using binary representation. 17 5. The sums Sk mand the Pascal’s triangle In this section, we present a simple recurrence relation, closely related to the Pascal’s triangle, for rapidly computing the sums Sk mdefined in the previous section. This relation is given in the next theorem. Due to its recursiveness, our formula is very adequate for computational purposes and, indeed, it is the main result underlying our algorithm for estimating the system unavailability –presented in the next section. First, we associate to each one of the basic probabilities pi(1 ≤i≤n), the corresponding quotient qi=pi 1−pi for all i= 1,2, . . . , n. Note that, due to our hypothesis (3.7) and to the increasing character of function y=x 1−x, we have 0< q1≤q2≤ · · · ≤ qn≤1. Remark 5.1. We must highlight here that the above quotients qican be used to reduce the computational cost, when computing the occurrence probabilities of the binary n-tuples u= (u1, . . . , un). Instead of using Eq. (3.1), taking advantage of the occurrence probability S0of the zero n-tuple (computed by Eq. (4.1)), we have Pr {u}= Pr {(u1, . . . , un)}= n Y i=1 pui i(1 −pi)1−ui= n Y i=1 ui=1 pi n Y i=1 ui=0 (1 −pi) = n Y i=1 ui=1 pi 1−pi n Y i=1 (1 −pi) = Pr 0,n |{z} . . . , 0 n Y i=1 ui=1 qi=S0 n Y i=1 ui=1 qi, so that Pr {u}= Pr {(u1, . . . , un)}=S0 n Y i=1 ui=1 qi.(5.1) The above strategy for deriving Eq. (5.1) (which computes the binary string probabilities) has also been used in [27] for a different purpose, namely for obtaining an explicit, non-recursive formula to compute the maximum error in the estimation of the system unavailability. 18 We stress out the fact that Eq. (5.1) is especially useful for reducing the computational cost, when the Hamming weight of u(i.e., the number of bits ui= 1) is small, which is in general the case for the bitstrings used in the algorithm that we propose in the next section. Indeed, suppose that we want to compute the occurrence probability of a binary n-tuple u= (u1, . . . , un) with a small weight m. If we use Eq. (3.1), we need to multiply the nfactors pui i(1 −pi)1−ui=piif ui= 1, 1−piif ui= 0 (1 ≤i≤n). Otherwise, using Eq. (5.1), we only need to multiply the m+ 1 factors S0, qi1, . . . , qim, where i1, . . . , imare the positions of the m1-bits in u. For instance, for n= 9, u = (0,0,1,0,0,0,0,1,1) , wH(u) = 3, using Eq. (3.1), we get Pr {u}= (1 −p1) (1 −p2)p3(1 −p4) (1 −p5) (1 −p6) (1 −p7)p8p9, while, using Eq. (5.1), we get Pr {u}=S0q3q8q9. Theorem 5.1. For all n≥1and for all m, k such that 1≤m≤k≤n Sk m=Sk−1 m+qn−k+1Sk−1 m−1,(5.2) where we adopt the conventions that Sk 0=S0for all k= 0,1, . . . , n −1and Sm−1 m= 0 for all m= 1,2, . . . , n. Proof. First, note that, according to the definition of the sums Sk m, the expressions Sk 0(0 ≤k≤n−1) and Sm−1 m(1 ≤m≤n), to which the above conventions are referred, do not make sense. We distinguish the following two cases. (a) For k=m, we have Sm m= Pr ( 0,n−m |{z} . . . , 0,1,m |{z} . . . , 1!) =pn−m+1 1−pn−m+1 Pr ( 0,n−m+ 1 |{z } . . . , 0,1,m−1 |{z} . . . , 1!)=qn−m+1Sm−1 m−1 19 and this is exactly Eq. (5.2) for k=m, since we have adopted the convention that Sm−1 m= 0 (1 ≤m≤n). (b) For k > m, we give a combinatorial proof. The set Ck mof the binary n-tuples (u1, . . . , un) with weight mwhose 1s are placed among the krightmost positions, namely n−k+1, . . . , n, can be partitioned into the following two subsets: (b.1) The subset of n-tuples u∈Ck msuch that un−k+1 = 0. (b.2) The subset of n-tuples u∈Ck msuch that un−k+1 = 1. The first subset is exactly the set of binary n-tuples with weight mwhose m1s are placed among the k−1 right-most positions, i.e., the set Ck−1 m. The second subset is exactly the set of binary n-tuples with weight msuch that un−k+1 = 1 and whose remaining m−1 1-bits are placed among the k−1 right-most positions, i.e., the set 0,n−k |{z} . . . , 0,1,0,k−1 |{z} . . . , 0!+Ck−1 m−1 =( 0,n−k |{z} . . . , 0,1,0,k−1 |{z} . . . , 0!+vv∈Ck−1 m−1). So, we have the set partition Ck m=Ck−1 m∪" 0,n−k |{z} . . . , 0,1,0,k−1 |{z} . . . , 0!+Ck−1 m−1#(5.3) and thus we get Sk m=Sk−1 m+qn−k+1Sk−1 m−1, since Sk m,Sk−1 mand qn−k+1Sk−1 m−1are obviously the sums of the occurrence probabilities of all the n-tuples belonging to the sets Ck m, Ck−1 mand 0,n−k |{z} . . . , 0,1,0,k−1 |{z} . . . , 0!+Ck−1 m−1, respectively.  The above combinatorial proof suggests a tight connection between our model and the famous Pascal’s triangle. Indeed, note that each sum Sk mis 20 taken over the corresponding set Ck m, whose cardinality is the combinatorial number k m, since m1s must be placed among kpositions. That is, Sk m=X u∈Ck m Pr {u}and Ck m=k m,1≤m≤k≤n. (5.4) In Fig. 4, we illustrate this connection. The left triangle contains the sums Sk m(1 ≤m≤k≤4) of system elementary state probabilities. The right triangle contains the binomial coefficients k m(1 ≤m≤k≤4), that is, it is the Pascal’s triangle where its left-most diagonal k 0k≥0has been deleted in order to avoid the repetition of the zero n-tuple probability S0. Clearly, Eq. (5.4) shows that each one of the sums Sk mis taken over exactly k mbinary strings. The interpretation of Fig. 4, for the relationship between accuracy and computational cost, is the following. The error estimate of the system unavailability, Pr {Φ = 1}, is reduced by the quantity Sk mat the same time as the Boolean function Φ, describing the FT logic, needs to be evaluated at k mbinary strings. S1 1 S2 1S2 2 S3 1S3 2S3 3 S4 1S4 2S4 3S4 4 1 1 2 1 2 2 3 1 3 2 3 3 4 1 4 2 4 3 4 4 Fig. 4. Accuracy/computational cost ratio and the Pascal’s triangle. Moreover, for the case m < k, counting the binary n-tuples involved in each of the three sums of formula (5.2) or, equivalently, counting the binary n-tuples belonging to each of the three sets of partition (5.3), we get Ck m=Ck−1 m+Ck−1 m−1, and then, using Eq. (5.4), we obtain the famous Pascal’s formula k m=k−1 m+k−1 m−1. 6. The algorithm Based on the previous ideas and propositions, in this section we present a new algorithm for evaluating the system unavailability. We call it the 21 FTA via Intrinsic Ordering &Pascal’s Triangle Algorithm (FTAIOPT - Algorithm, for short) because the FTA of the current system is based on an adequate selection of binary n-tuples (i.e., with large occurrence probabilities) tightly connected to both the intrinsic ordering and the Pascal’s triangle. Next, we illustrate our approach on a real-world analysis problem taken from [35]. 6.1. The FTAIOPT-Algorithm For each given maximum admissible error ε, the FTAIOPT-Algorithm provides lower and upper bounds on the failure probability Pr {Φ = 1}of a (coherent or non-coherent) system depending on nmutually independent basic components. The set {pi}n i=1 of basic probabilities must satisfy the (non-restrictive) hypothesis (3.7). If this assumption is not satisfied by the current system, then we proceed as explained in Remark 3.1 and next, we rewrite the Boolean function Φ using the new Boolean variables. The following are the main ideas of the FTAIOPT-Algorithm: (i) Theorem 4.1-(i) has stated that for every nonzero binary n-tuple vof weight mwe can always find a binary n-tuple uof weight m−1, s.t. Pr {u}> Pr {v}. Theorem 4.1-(ii) has stated that for every nonzero binary n-tuple v of weight mwhose 1s are placed among the kright-most positions, but not among the k−1 right-most positions, we can always find a binary n-tuple uof weight mwhose 1s are placed among the k−1 right-most positions, s.t. Pr {u}>Pr {v}. Hence, we select the sets Ck mof binary n-tuples in increasing order of the weight m(for m= 1 to n), and for each fixed weight m, in increasing order of k(for k=mto n). (ii) To compute the sums Sk m, we use the recurrence formula (5.2) stated by Theorem 5.1. (iii) In order to get the required accuracy (maximum admissible error ε), we select the binary n-tuples until we assure that the sum of their occurrence probabilities is greater than or equal to 1 −ε. In this way, according to Eq. (3.6), we have X u∈C Pr {u} ≥ 1−ε⇔U−L= 1 −X u∈C Pr {u} ≤ ε. (6.1) (iv) For each one of the selected binary n-tuples, u∈C, we compute its occurrence probability, Pr {u}, by Eq. (3.1) and evaluate the Boolean function Φ. According to Eq. (3.5), we get the lower and upper bounds on system 22 unavailability L=X u∈C, Φ(u)=1 Pr {u} ≤ Pr {Φ = 1} ≤ 1−X u∈C, Φ(u)=0 Pr {u}=U, satisfying, as desired, U−L≤ε. Based on these ideas, our algorithm can be described as follows. The FTAIOPT-Algorithm Step 1. For i= 1 to ncompute qi=pi 1−pi. Step 2. Compute S0= Pr 0,n |{z} . . . , 0(using Eq. (4.1)). Step 3. If S0≥1−(the zero n-tuple is enough!) then goto Step 9 (due to Eq. (6.1)) Step 4. For k= 0,1, . . . , n −1 : define Sk 0=S0(by convention, Theorem 5.1). Step 5. For m= 1,2, . . . , n : define Sm−1 m= 0 (by convention, Theorem 5.1). Step 6. Call S=S0. Step 7. For m= 1 to n(due to Theorem 4.1) For k=mto n(due to Theorem 4.1) compute Sk m=Sk−1 m+qn−k+1Sk−1 m−1(by Theorem 5.1) if S+Sk m≥1−then goto Step 8 (due to Eq. (6.1)) Next k Compute S=S+Sn m(Sis the sum of the probabilities of all n-tuples with weights 0, . . . , m, due to Eq. (4.2)) Next m Step 8. For all nonzero selected n-tuples u∈Cn 1∪ · · · ∪ Cn m−1∪Ck mcompute Pr {u}(using Eq. (5.1)). Step 9. For all nonzero selected n-tuples u∈Cn 1∪ · · · ∪ Cn m−1∪Ck mand for the zero n-tuple do: If Φ (u) = 1 then L=L+ Pr {u}, If Φ (u) = 0 then V=V+ Pr {u}. Step 10. Compute U= 1 −Vand write (due to Eq. (3.5)) L≤Pr {Φ = 1} ≤ U. 23 6.2. A real-world example Our real-life example corresponds to the accumulator system (ACC) of a pressured water reactor (PWR) in a nuclear power plant, which has been taken from [35]. The ACC is a passive injection system that is a part of the PWR emergency core coolant injection system, where one accumulator is attached to the cold leg of each loop of the reactor coolant system to provide a source of emergency make-up water for that loop if a loss of coolant accident (LOCA) occurs. The accumulator is simply a pressure vessel partially filled with borated water, and pressurized with nitrogen gas. When pressure in the cold leg drops below 650 psig, the check valves open, and borated water is forced into the reactor coolant system. The PWR has 3 loops, hence there are three accumulators, one attached to cold leg of each loop. The contents of 2 accumulators are required to successfully reflood the core following a large LOCA. If a LOCA occurs in a cold leg, the content of the corresponding accumulator is lost through the break; thus both of the remaining 2 accumulators must successfully discharge their contents into the reactor coolant system to protect the core. Therefore, success for the accumulator discharge to the reactor coolant system for the postulated cold leg LOCA requires both accumulators. The total CPU time required to solve this numerical example was less than one second, using a 2GHz Pentium IV. The ACC failure behavior is represented by a coherent fault tree with 83 basic components and 42 logic gates. For a maximum admissible error = 10−6, it was enough to use the zero 83-tuple (with weight m= 0); all the 83 binary 83-tuples of weight m= 1; and the 34 2= 561 binary 83-tuples of weight m= 2, whose 1s are placed among the k= 34 right-most positions. That is, the set of selected binary 83-tuples was C={0} ∪ C83 1∪C34 2. Then, using a total number of (see Eq. (5.4) and Fig. 4) T=|{0}| +C83 1+C34 2=83 0+83 1+34 2= 645 binary 83-tuples, the sum of the occurrence probabilities of all selected bitstrings was (see Eqs. (4.1) & (5.4)) X u∈C Pr {u}=S=S0+S83 1+S34 2= 9999.99065·10−4≥9999.99·10−4= 1−. 24 In this way, we have obtained the following lower and upper bounds on the ACC unavailability L= 3.74552 ·10−4≤Pr {Φ = 1} ≤ 3.75487 ·10−4=U, satisfying, as desired (see Eq. (6.1) and Step 7), U−L= 9.35 ·10−7<10−6=. Note that Steps 1-7 of the algorithm have determined that the above binary 83-tuples are enough for estimating the ACC unavailability with the required accuracy = 10−6. These steps only involve the basic probabilities piand the required accuracy . Thus, the same 645 binary strings are also enough to estimate the top event probability of any other coherent or noncoherent 83-system with the same set {pi}83 i=1 of basic probabilities as the ACC system, and for the same maximum admissible error = 10−6. Next, in Step 8 the occurrence probabilities of these 645 selected binary strings are computed. Of course, due to the way in which Step 7 selects the binary n-tuples (in increasing order of their Hamming weights), these calculations can be carried out, with a very low computational cost (taking advantage of the value S0computed in Step 2), simply by using Eq. (5.1). See Remark 5.1 and Step 8. Note that the Boolean structure (function) of the system has not yet used, i.e., the results obtained by Steps 1-8 are valid with independence of the FT logic! In particular, it is also irrelevant whether the current system is coherent or non-coherent. Then, for each given structure function Φ, we only need to evaluate the current Boolean function Φ on the 645 selected binary 83-tuples for obtaining the corresponding exact lower and upper bounds L, U for each given maximum admissible error (Steps 9-10). Under quite general hypotheses, our algorithm provides exact lower and upper bounds on system unavailability for a given accuracy. The main characteristics and advantages of the proposed method are the following: (i) Our algorithm, based on Eq. (3.5) and on the IOC, does not require any knowledge or information (that other techniques often require) about the FT structure function. This is the main advantage, compared with many other methods. (ii) Because of Eqs. (3.5) and (3.6), the accuracy in the estimation is independent of the FT logic, and it only depends on the sum of the occurrence probabilities of the selected binary n-tuples. (iii) Due to Eqs. (3.5) 25