A Monte Carlo Sampling Plan for Estimating Network Reliability

Publisher Website
Google Scholar
Abstract
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.

This publication has 0 references indexed in Scilit: