Recursive variance reduction estimators for the static communication network reliability problem
Seminar Room 1, Newton Institute
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 . 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 . We show that the
method does not verify the bounded relative error (BRE) property  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 . 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.
 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.
 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.
 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.
 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.