# Monte-Carlo Methods for Estimating System Reliability

### Michael G. Luby

### EECS Department, University of California, Berkeley

### Technical Report No. UCB/CSD-84-168

### , 1984

### http://www2.eecs.berkeley.edu/Pubs/TechRpts/1984/CSD-84-168.pdf

An <i>n</i>-component system contains <i>n</i> components, where each component may be either failing or working. Each component <i>i</i> is failing with probability <i>Pi</i> independently of the other components in the system. A system state is a specification of the states of the <i>n</i> components. Let <i>F</i>, the set of failure states, be a specified subset of all system states. In this paper we develop Monte Carlo algorithms to estimate <i>Pr</i>[<i>F</i>], the probability that the system is in a failure state. <p> We now describe the two different formats for the representation of <i>F</i> considered in this paper. In the first format <i>F</i> is represented by <i>m</i> failure sets <i>F1</i>, <i>F2</i>, . . . , <i>Fm</i>. Each failure set is specified by an <i>n</i>-tuple in the input. The set of failure states is then <i>F</i>=m,t=1<i>Fi</i>. We develop a formula for the probability of a union of events. A Monte Carlo algorithm which estimates the failure probability of an <i>n</i>-component system is developed based on this formula. One trial of the algorithm outputs an unbiased estimator of <i>Pr</i>[<i>F</i>]. Let <i>Y</i> be the average of the estimators produced by many trials of the algorithm. We show that, when the algorithm is run for an amount of time proportional to <i>nm</i>, <i>Y</i> is provably close to <i>Pr</i>[<i>F</i>] with high probability. <p> The second format for the representation of <i>F</i> can be described as follows. A network is an undirected graph <i>G</i>, where the edges in the graph correspond to the components in the system. Let <i>G</i> be a planar network and let <i>x1</i>, . . . , <i>xK</i> be <i>K</i> specified nodes in <i>G</i>. For the planar <i>K</i>-terminal problem, the network is in a failing state if there is no path of working edges between some pair of specified nodes. We develop a Monte Carlo algorithm to estimate <i>Pr</i>[<i>F</i>] for the planar <i>K</i>-terminal problem. The algorithm works especially well when the edge failure probabilities are small. In this case the algorithm produces an estimator <i>Y</i> which is provably close to <i>Pr</i>[<i>F</i>] with high probability in time polynomial in the size of the graph. This compares very favorably with the execution times of other methods used for solving this problem.

**Advisors:** Richard M. Karp

BibTeX citation:

@phdthesis{Luby:CSD-84-168, Author= {Luby, Michael G.}, Title= {Monte-Carlo Methods for Estimating System Reliability}, School= {EECS Department, University of California, Berkeley}, Year= {1984}, Month= {Jun}, Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1984/5978.html}, Number= {UCB/CSD-84-168}, Abstract= {An <i>n</i>-component system contains <i>n</i> components, where each component may be either failing or working. Each component <i>i</i> is failing with probability <i>Pi</i> independently of the other components in the system. A system state is a specification of the states of the <i>n</i> components. Let <i>F</i>, the set of failure states, be a specified subset of all system states. In this paper we develop Monte Carlo algorithms to estimate <i>Pr</i>[<i>F</i>], the probability that the system is in a failure state. <p> We now describe the two different formats for the representation of <i>F</i> considered in this paper. In the first format <i>F</i> is represented by <i>m</i> failure sets <i>F1</i>, <i>F2</i>, . . . , <i>Fm</i>. Each failure set is specified by an <i>n</i>-tuple in the input. The set of failure states is then <i>F</i>=m,t=1<i>Fi</i>. We develop a formula for the probability of a union of events. A Monte Carlo algorithm which estimates the failure probability of an <i>n</i>-component system is developed based on this formula. One trial of the algorithm outputs an unbiased estimator of <i>Pr</i>[<i>F</i>]. Let <i>Y</i> be the average of the estimators produced by many trials of the algorithm. We show that, when the algorithm is run for an amount of time proportional to <i>nm</i>, <i>Y</i> is provably close to <i>Pr</i>[<i>F</i>] with high probability. <p> The second format for the representation of <i>F</i> can be described as follows. A network is an undirected graph <i>G</i>, where the edges in the graph correspond to the components in the system. Let <i>G</i> be a planar network and let <i>x1</i>, . . . , <i>xK</i> be <i>K</i> specified nodes in <i>G</i>. For the planar <i>K</i>-terminal problem, the network is in a failing state if there is no path of working edges between some pair of specified nodes. We develop a Monte Carlo algorithm to estimate <i>Pr</i>[<i>F</i>] for the planar <i>K</i>-terminal problem. The algorithm works especially well when the edge failure probabilities are small. In this case the algorithm produces an estimator <i>Y</i> which is provably close to <i>Pr</i>[<i>F</i>] with high probability in time polynomial in the size of the graph. This compares very favorably with the execution times of other methods used for solving this problem.}, }

EndNote citation:

%0 Thesis %A Luby, Michael G. %T Monte-Carlo Methods for Estimating System Reliability %I EECS Department, University of California, Berkeley %D 1984 %@ UCB/CSD-84-168 %U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1984/5978.html %F Luby:CSD-84-168