Intrinsic ordering, combinatorial numbers and reliability engineering

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 n of 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 (2n binary n-tuples) to linear (n Boolean 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 m whose 1s are placed among the k right-most positions. This formula, as well as the balance between accuracy and computational cost, is closely related to the famous Pascal’s triangle.