Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

Monte-Carlo Methods for Estimating System Reliability

Michael G. Luby

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-84-168
1983

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

An n-component system contains n components, where each component may be either failing or working. Each component i is failing with probability Pi independently of the other components in the system. A system state is a specification of the states of the n components. Let F, the set of failure states, be a specified subset of all system states. In this paper we develop Monte Carlo algorithms to estimate Pr[F], the probability that the system is in a failure state.

We now describe the two different formats for the representation of F considered in this paper. In the first format F is represented by m failure sets F1, F2, . . . , Fm. Each failure set is specified by an n-tuple in the input. The set of failure states is then F=m,t=1Fi. We develop a formula for the probability of a union of events. A Monte Carlo algorithm which estimates the failure probability of an n-component system is developed based on this formula. One trial of the algorithm outputs an unbiased estimator of Pr[F]. Let Y 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 nm, Y is provably close to Pr[F] with high probability.

The second format for the representation of F can be described as follows. A network is an undirected graph G, where the edges in the graph correspond to the components in the system. Let G be a planar network and let x1, . . . , xK be K specified nodes in G. For the planar K-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 Pr[F] for the planar K-terminal problem. The algorithm works especially well when the edge failure probabilities are small. In this case the algorithm produces an estimator Y which is provably close to Pr[F] 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.

Advisor: 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 = {1983},
    Month = {Jun},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/1983/5978.html},
    Number = {UCB/CSD-84-168}
}

EndNote citation:

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