Approximate Zero-Variance Importance Sampling for Static Network Reliability Estimation
- 21 April 2011
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Reliability
- Vol. 60 (3), 590-604
- https://doi.org/10.1109/tr.2011.2135670
Abstract
We propose a new Monte Carlo method, based on dynamic importance sampling, to estimate the probability that a given set of nodes is connected in a graph (or network) where each link is failed with a given probability. The method generates the link states one by one, using a sampling strategy that approximates an ideal zero-variance importance sampling scheme. The approximation is based on minimal cuts in subgraphs. In an asymptotic rare-event regime where failure probability becomes very small, we prove that the relative error of our estimator remains bounded, and even converges to 0 under additional conditions, when the unreliability of individual links converges to 0. The empirical performance of the new sampling scheme is illustrated by examples.Keywords
This publication has 21 references indexed in Scilit:
- Asymptotic robustness of estimators in rare-event simulationACM Transactions on Modeling and Computer Simulation, 2010
- Importance Sampling in Rare Event SimulationPublished by Wiley ,2009
- Robustness Properties and Confidence Interval Reliability IssuesPublished by Wiley ,2009
- Chapter 11 Rare-Event Simulation Techniques: An Introduction and Recent AdvancesPublished by Elsevier BV ,2006
- THE TREE CUT AND MERGE ALGORITHM FOR ESTIMATION OF NETWORK RELIABILITYProbability in the Engineering and Informational Sciences, 2003
- Adaptive importance sampling on discrete Markov chainsThe Annals of Applied Probability, 1999
- Fast simulation of rare events in queueing and reliability modelsACM Transactions on Modeling and Computer Simulation, 1995
- Importance Sampling for the Simulation of Highly Reliable Markovian SystemsManagement Science, 1994
- System Reliability By Simulation: Random Hazards Versus Importance SamplingProbability in the Engineering and Informational Sciences, 1992
- Network reliability and the factoring theoremNetworks, 1983