A MONTE CARLO SIMULATION OF THE FLOW NETWORK RELIABILITY USING IMPORTANCE AND STRATIFIED SAMPLING

摘要

We consider the evaluation of the flow network reliability parameter. Because its exact computation has exponential time complexity, simulation methods are alternatives used to evaluate large networks. In this paper, we use the state space decomposition methodology of Doulliez and Jamoulle in order to construct a new simulation method which combines the importance and the stratified Monte Carlo principles. We show that the related estimator belongs to the variance reduction family and it offers more accurate estimates than those obtained by a previous stratified sampling technique based on the same decomposition. By experimental results, we show the interest of the proposed method when compared to previous methods.%Nous considérons le problème de l'évaluation de la fiabilité d'un réseau de transport stochastique. Le fait que le calcul analytique de ce paramètre soit de complexité temporelle exponentielle, conduit à utiliser des simulations de Monte Carlo pour l'analyse des réseaux de grande taille. Dans ce papier, nous exploitons la procédure de décomposition de l'espace d'états de Doulliez et Jamoulle pour construire une nouvelle méthode de simulation. Elle est basée sur les échantillonnages stratifié et préférentiel. Nous démontrons théoriquement que cette méthode appartient à la famille des méthodes de réduction de la variance et que l'estimateur associé est de variance plus réduite que celle d'un estimateur stratifié basé sur la même décomposition. Par des résultats expérimentaux, nous montrons l'intérêt de la méthode proposée en la comparant à d'autres méthodes.