Splitting the unity, bisecting a graph: applications to stochastic Boolean systems

Abstract

This paper deals with the reliability and risk analysis of those complex systems depending on n stochastic Boolean variables. Each one of the 2(n) elementary states associated to such a system is given by its corresponding binary n-tuple of 0s and 1s. A symmetric fractal graph on 2(n) nodes (the so-called intrinsic order graph In) is used for displaying all the binary n-tuples in decreasing order of their occurrence probabilities. The successive bisections of this graph into smaller subgraphs one-to-one correspond to the successive splits of 1 as sum of the occurrence probabilities of those subgraphs. This iterative bisection process satisfies a nice property: if we replace each one of the subgraphs C (obtained after k successive bisections of the original intrinsic order graph I-n) by an unique node weighted by the sum of the probabilities of all vertices lying on C and we sort the new nodes in decreasing order of their weights, then the new condensed graph is exactly the intrinsic order graph I-k. Finally, based on these results, a new algorithm for estimating the unavailability of stochastic Boolean systems is presented.