Summary: A stochastic binary system (SBS) is a multicomponent on-off system subject to random independent failures on its components. After potential failures, the state of the subsystem is ruled by a logical function (called structure function) that determines whether the system is operational or not. A SBS serves as a natural generalization of network reliability analysis, where the goal is to find the probability of correct operation of the system (in terms of connectivity, network diameter, or different measures of success). A particular subclass of interest is stochastic monotone binary systems (SMBS), which are characterized by nondecreasing structure. We explore the combinatorics of SBS, which provide building blocks for system reliability estimation, looking at minimal nonoperational subsystems, called mincuts. One key concept to understand the underlying combinatorics of SBS is duality. As methods for exact evaluation take exponential time, we discuss the use of Monte Carlo algorithms. In particular, we discuss the \(F\)-Monte Carlo method for estimating the reliability polynomial for homogeneous SBS, the recursive variance reduction for SMBS, which builds upon the efficient determination of mincuts, and three additional methods that combine in different ways the well-known techniques of permutation Monte Carlo and splitting. These last three methods are based on a stochastic process called the creation process, a temporal evolution of the SBS which is static by definition. All the methods are compared using different topologies, showing large efficiency gains over the basic Monte Carlo scheme.
{© 2021 The Authors. International Transactions in Operational Research © 2021 International Federation of Operational Research Societies}