Groupe d’études et de recherche en analyse des décisions

# Effective Approximation of Zero-Variance Simulation in a Reliability Setting

## Pierre L'Ecuyer et Bruno Tuffin

For every stochastic simulation model, there is in theory a way of changing the probability laws that drive the system so that the resulting IS estimator has zero variance. This optimal estimation scheme is generally impractical to implement, but it can be possible to approximate it in an effective way. When the model is described by a discrete-time Markov chain that evolves up to some random stopping time, the zero-variance change of measure can be written exactly in terms of a value function that gives the expected cost-to-go from any state of the chain, so it can be approximated by approximating this value function. We detail this approach and show how it can be effectively used to estimate the reliability of a highly-reliable multicomponent system with Markovian behavior. In our implementation, we start with a very simple crude approximation, use it in a first-order IS scheme to obtain a better approximation at a few selected states, interpolate in between, and use this interpolation in our final (second-order) IS scheme. In numerical illustrations, our approach outperforms the popular IS heuristics previously proposed for this class of problems

, 17 pages