Recursive Variance Reduction method in stochastic monotone binary systems

A multi-component system is usually defined over a ground set S with m = |S| components that work (or fail) stochastically and independently, ruled by the probability vector p ϵ [0, 1]^m, where p_i is the probability that component i works. We study systems which can be either in “up” or “down” state, according to their ability to comply with their stated mission given the subset of components under operation, through a function φ :P(S) → {0,1}, called structure. A stochastic binary system (SBS) is the triad (S, p, φ), and the reliability r of an SBS is the probability that the system is up. The reliability evaluation of an arbitrary SBS belongs to the class of ℕP-Hard computational problems. Therefore, there is no polynomial time algorithm to find r for every SBS, unless P = ℕP. The goal of this paper is to study approximation algorithms to accurately estimate the reliability of a stochastic monotone binary system, or SMBS, where its structure is monotonous. First, two Monte Carlo approaches are discussed. Then, the Recursive Variance Reduction (RVR) method (designed originally for the particular case of network reliability) is generalized to estimate the reliability of an SBMS. The performance of these algorithms under different SMBS (inspired mainly in network design and k-out-of-m structures) is illustrated numerically. Hints and challenges for future work are discussed in the conclusions.