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.