Richard M. Karp and Michael G. Luby

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-83-117

, 1983

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1983/CSD-83-117.pdf

A new formula for the probability of a union of events is used to express the failure probability of an n-component system. a very simple Monte-Carlo algorithm based on the new probability formula is presented. The input to the algorithm gives the failure probabilities of the n components of the system and a list of the failure sets of the system. The output is an unbiased estimator of the failure probability of the system. We show that the average value of the estimator over many runs of the algorithm tends to converge quickly to the failure Probability of the system. The overall time to estimate the failure probability with high accuracy compares very favorably with the execution times of other methods used for solving this problem.


BibTeX citation:

@techreport{Karp:CSD-83-117,
    Author= {Karp, Richard M. and Luby, Michael G.},
    Title= {A New Monte-Carlo Method for Estimating the Failure Probability of an n-Component System},
    Year= {1983},
    Month= {Feb},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1983/6351.html},
    Number= {UCB/CSD-83-117},
    Abstract= {A new formula for the probability of a union of events is used to express the failure probability of an n-component system. a very simple Monte-Carlo algorithm based on the new probability formula is presented. The input to the algorithm gives the failure probabilities of the n components of the system and a list of the failure sets of the system. The output is an unbiased estimator of the failure probability of the system. We show that the average value of the estimator over many runs of the algorithm tends to converge quickly to the failure Probability of the system. The overall time to estimate the failure probability with high accuracy compares very favorably with the execution times of other methods used for solving this problem.},
}

EndNote citation:

%0 Report
%A Karp, Richard M. 
%A Luby, Michael G. 
%T A New Monte-Carlo Method for Estimating the Failure Probability of an n-Component System
%I EECS Department, University of California, Berkeley
%D 1983
%@ UCB/CSD-83-117
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1983/6351.html
%F Karp:CSD-83-117