Rare-Event Simulation of Regenerative Systems: Estimation of the Mean and Distribution of Hitting Times

Bruno Tuffin

présentera le vendredi 20 Novembre 15:00 en visio ses travaux intitulés:

Rare-Event Simulation of Regenerative Systems:

Estimation of the Mean and Distribution of Hitting Times
 

Abstract:

Rare events occur by definition with a very small probability but are important to analyze because of potential catastrophic consequences. During this talk, we will focus on rare event for so-called regenerative processes, that are basically processes such that portions of the process are statistically independent of each other. For many complex and/or large models, simulation is the only tool at hand but requires specific implementations to get an accurate answer in a reasonable time. There are two main families of rare-event simulation techniques: importance sampling (IS) and splitting.
We will (somewhat arbitrarily) devote most of the talk to IS.

We will then focus on the estimation of the mean hitting time of a rarely visited set. A natural and direct estimator consists in averaging independent and identically distributed copies of simulated hitting times, but an alternative standard estimator uses the regenerative structure allowing to represent the mean as a ratio of quantities. We will see that in the setting of crude simulation, the two estimators are actually asymptotically identical in a rare-event context, but inefficient for different, even if related, reasons: the direct estimator requires a large average computational time of a single run whereas the ratio estimator faces a small probability computation. We then explain that the ratio estimator is advised when using IS.

In the third part of the talk, we will discuss the estimation of the distribution, not just the mean, of the hitting time to a rarely visited set of states. We will exploit the property that the distribution of the hitting time divided by its expectation converges weakly to an exponential as the target set probability decreases to zero. The problem then reduces to the extensively studied estimation of the mean described previously. It leads to simple estimators of a quantile and conditional tail expectation of the hitting time. Some variants will be presented and the accuracy of the estimators illustrated on numerical examples.

This talk is mostly based on collaborative works with Peter W. Glynn and Marvin K. Nakayama.

Short bio:

Bruno Tuffin received his PhD degree in applied mathematics from the University of Rennes 1 (France) in 1997 and got a one-year position at the Institut Mathématique de Rennes after that.
Since 1998, he has been with Inria in Rennes. He spent 8 months as a postdoc at Duke University in 1999.
His research interests include network economics and developing Monte Carlo and quasi-Monte Carlo simulation techniques for the performance evaluation of telecommunication systems. He organized or co-chaired 17 international conferences.
He is currently Area Editor for INFORMS Journal on Computing and Associate Editor for ACM Transactions on Modeling and Computer Simulation and was an Associate Editor for Mathematical Methods of Operations Research. He has written or co-written three books, two devoted to simulation (Rare event simulation using Monte Carlo methods, John Wiley \& Sons, 2009 and La simulation de Monte Carlo, Hermes, 2010), and
Telecommunication Network Economics: From Theory to Applications, Cambridge University Press, 2014. He has published 56 papers in international journals, 12 book chapters and around 110 papers in peer-reviewed international conferences.