Building Reliability Bounds in Stochastic Binary Systems

A Stochastic Binary System (SBS) is a mathematical model of multi-component on-off systems subject to random failures. SBS models extend classical network reliability models (where the components subject to failure are nodes or links of a graph) and are able to represent more complex interactions between the states of the individual components and the operation of the system under study.The reliability evaluation of stochastic binary systems belongs to the class of ${\mathcal{N}}{\mathcal{P}}$-Hard computational problems. Furthermore, the number of states is exponential with respect to the size of the system (measured in the number of components). As a consequence, the representation of an SBS becomes a key element in order to develop exact and/or approximation methods for reliability evaluation.We introduce the concept of separable stochastic binary systems, whose structure can be efficiently represented. Reliability bounds for arbitrary SBS are provided inspired by a measure of a distance to a separable system, duality and Chernoff inequality. Opportunities for future work arising from this representation are also discussed.