A Monte Carlo Sampling Plan for Estimating Network Reliability

For an undirected network G = ( V , E ) whose arcs are subject to random failure, we present a relatively complete and comprehensive description of a general class of Monte Carlo sampling plans for estimating g = g ( s , T ), the probability that a specified node s is connected to all nodes in a node set T . We also provide procedures for implementing these plans. Each plan uses known lower and upper bounds [ B , A ] on g to produce an estimator of g that has a smaller variance ( A − g )( g − B )/ K on K independent replications than that obtained for crude Monte Carlo sampling ( B = 0, A = 1). We describe worst-case bounds on sample sizes K , in terms of B and A , for meeting absolute and relative error criteria. We also give the worst-case bound on the amount of variance reduction that can be expected when compared with crude Monte Carlo sampling. Two plans arc studied in detail for the case T = { t }. An example illustrates the variance reductions achievable with these plans. We also show how to assess the credibility that a specified error criterion for g is met as the Monte Carlo experiment progresses, and show how confidence intervals can be computed for g . Lastly, we summarize the steps needed to implement the proposed technique.