A Monte Carlo estimator based on a state space decomposition methodology for flow network reliability. (English) Zbl 1091.65500

Bulteau, Stéphane; El Khadiri, Mohamed

Niederreiter, Harald (ed.) et al., Monte Carlo and quasi-Monte Carlo methods 1996. Proceedings of a conference at the University of Salzburg, Austria, July 9–12, 1996. Berlin: Springer (ISBN 0-387-98335-X). Lect. Notes Stat. 127, 161-175 (1997).

Summary: The exact evaluation of the probability that the maximum \(st\)-flow is greater than or equal to a fixed value \(d\) in a stochastic flow network is an NP-hard problem. This limitation leads us to consider Monte Carlo alternatives. In this paper, we show how to exploit the state space decomposition methodology of Doulliez and Jamoulle for deriving a Monte Carlo simulation algorithm. We show that the resulting Monte Carlo estimator belongs to the variance-reduction family and we give a worst-case bound on the variance-reduction ratio that can be expected when compared with the standard sampling. We illustrate by numerical comparisons that the proposed simulation algorithm allows substantial variance reduction with respect to the standard algorithm and it is competitive when compared to previous work in this context.
For the entire collection see [Zbl 0879.00054].

MSC:

65C05	Monte Carlo methods
90B15	Stochastic network models in operations research