A Monte Carlo Sampling Plan for Estimating Network Reliability

Consider an acyclic undirected network G = (V,E) with node set V and arc set E whose arcs are subject to random failure. Let s be a node in V and T a set of nodes in V such that s ⊄ T. This paper presents a relatively complete and comprehensive description of a general class of Monte Carlo sampling plans for estimating g = g(s,T), the probability that s is connected to all nodes in T. The paper also provides 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 than one obtains for crude Monte Carlo sampling (B-O, A-1) on K independent replications. The paper describes worst case bounds on sample sizes K, in terms of B and A, for meeting absolute and relative error criteria. It also gives the worst case bound on the amount of variance reduction that can be expected when compared with crude Monte Carlo sampling. Two plans are studied in detail for the case T - {t}. An example illustrates the variance reductions achievable with these plans. The paper next shows how to assess the credibility that a specified error criterion for g is met as the Monte Carlo experiment progresses and then shows how confidence intervals can be computed for g. Lastly, the paper summarizes the steps needed toimplement the proposed technique