SCS

Abstract

The exact evaluation of static network reliability parameters belongs to the NP-hard class of problems and Monte Carlo simulation is therefore a relevant tool to provide their evaluations [2]. The first goal of this presentation is to review a Recursive Variance Reduction (RVR) estimator for the unreliability parameter which works by recursively reducing the graph based on a random choice (following a natural distribution) of the first working link on selected cuts [1]. We show that the method does not verify the bounded relative error (BRE) property [3] as the reliability of individual links goes to one, i.e., that the estimator is not robust to high reliability of links. We then propose to use the RVR principle in conjunction with the importance sampling technique. Two new estimators are presented: the first one, called Balanced RVR, follows an uniform distribution to choose the first working link on cuts, while the second, called Zero-Variance Approximation RVR, tries to mimic the distribution used by the (ideal) estimator with variance zero [4]. We show that in both cases the BRE property is verified and, moreover, that a Vanishing Relative Error property can be obtained by the Zero-Variance Approximation RVR under sufficient conditions. Finally, numerical illustrations of the power of both methods are provided. [1] H. Cancela and M. El Khadiri. A recursive variance-reduction algorithm for estimating communication-network reliability. IEEE Tr. on Reliability, 44(4):595–602, 1995. [2] H. Cancela, M. El Khadiri, and G. Rubino. In G. Rubino and B. Tuffin, editors, Rare Event Simulation using Monte Carlo Methods, chapter Rare events analysis by Monte Carlo techniques in static models, pages 145–170. John Wiley & Sons, 2009. [3] P. L’Ecuyer, J. H. Blanchet, B. Tuffin, and P. W. Glynn. Asymptotic robustness of estimators in rare-event simulation. ACM Tr. on Modeling and Computer Simulation, 2010. To appear. [4] P. L’Ecuyer, G. Rubino, S. Saggadi, and B. Tuffin. Approximate zero-variance importance sampling for static network reliability estimation. Submitted. Available at http://www. irisa.fr/dionysos/pages_perso/tuffin/Publis/static-IS.pdf, 2010.