Keywords: system unavailability, stochastic Boolean function, Hamming weight, intrinsic order, top binary n-tuples, Pascal's triangle.

Many different technical systems in engineering depend on a large number n of mutually independent basic components. Often, these components, , can be considered as random Boolean variables. That is, they only take two possible values: if the i-th component fails, otherwise, and the (basic) probability of failure of each component is assumed to be known a priori [1]. So, each one of the possible situations is given by a binary n-tuple of 0s and 1s, and it has its own occurrence probability . Moreover, the technical system can be described by a stochastic Boolean function , depending on its n basic components. Then, assuming that if the system fails, otherwise, the system unavailability -also called the top event probability- is evaluated by computing the probability  [1,2].

A wide class of different strategies has been proposed in reliability theory and risk analysis to estimate the top event probability (a central question in fault tree analysis) [2,3]. One of these methods is based on the canonical normal forms of the Boolean function , and it provides lower and upper bounds on the system unavailability, from any arbitrary subsets of binary n-tuples for which , respectively [1,4]. The accuracy in the above mentioned estimation of improves at the same time as the total sum, , of the occurrence probabilities of all the selected binary n-tuples increases. Consequently, the main (and the most difficult) question is how to select the minor number of binary strings with occurrence probabilities as large as possible, in order to minimize the computational cost. Note that the simplest answer to this question, namely, computing all the binary n-tuple probabilities and then ordering them by their occurrence probabilities, is not feasible due to the exponential nature of the problem: There are n-tuples of 0s and 1s.

To avoid this obstacle, we have established a simple, positional criterion that allows to compare two given elementary state probabilities without computing them, simply looking at the positions of their 0s and 1s [4,5]. The so-called intrinsic order criterion (because it is independent of the basic probabilities and it is determined by the positions of the 0 and 1 bits) defines a partial order relation (intrinsic order), denoted by , on the set . Theoretical results and practical applications of the intrinsic order can be found in [5,6], and the graphical structure of the partially ordered set is described in [7]. One of the topics in the intrinsic order model is the set of binary n-tuples whose occurrence probabilities are always (that is, for any set of parameters, , satisfying certain non-restrictive assumptions) among the largest ones, the so-called top binary n-tuples [8]. These binary strings can be characterized by several simple positional criteria related to their 0s and 1s.

In this context, we present a new method for selecting different sets of binary n-tuples, with large occurrence probabilities, in order to estimate the system unavailability with a low computational cost. Basically, the two main ideas underlying our new approach are: (i) we only select Top binary n-tuples. (ii) we provide a simple, recursive formula for rapidly computing the sums of the occurrence probabilities of the binary n-tuples with weight m whose 1s are placed among the k right-most positions . This formula is tightly related to the famous Pascal's triangle. Moreover, this connection highlights, in an elegant way, the balance between accuracy and computational cost.

In this way, we present an easily implementable algorithm which determines a priori different sets of top binary n-tuples that assure us the estimation of the system unavailability -via the above mentioned bounds- with a prespecified maximum error.

1

W.G. Schneeweiss, "Boolean Functions with Engineering Applications and Computer Programs", Springer-Verlag, Berlin Heidelberg New York, 1989.

2

N.D. Singpurwalla, "Foundational Issues in Reliability and Risk Analysis", SIAM Review, 30(2), 264-282, 1988. doi:10.1137/1030047

3

J. Andrews, B. Moss, "Reliability and Risk Assessment", 2nd edition, Professional Engineering Publishing, London, United Kingdom, 2002.

4

L. González, D. García, B. Galván, "An Intrinsic Order Criterion to Evaluate Large, Complex Fault Trees", IEEE Transactions on Reliability, 53(3), 297-305, 2004. doi:10.1109/TR.2004.833307

5

L. González, "N-tuples of 0s and 1s: Necessary and Sufficient Conditions for Intrinsic Order", Lecture Notes in Computer Science, 2667(1), 937-946, 2003. doi:10.1007/3-540-44839-X_99

6

L. González, "A New Algorithm for Complex Stochastic Boolean Systems", Lecture Notes in Computer Science, 3980(1), 633-643, 2006. doi:10.1007/11751540_67

7

L. González, "A Picture for Complex Stochastic Boolean Systems: The Intrinsic Order Graph", Lecture Notes in Computer Science, 3993(3), 305-312, 2006. doi:10.1007/11758532_42

8

L. González, "A New Method for Ordering Binary States Probabilities in Reliability and Risk Analysis", Lecture Notes in Computer Science, 2329(1), 137-146, 2002. doi:10.1007/3-540-46043-8_13

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £105 +P&P)