報告人： Bruno Tuffin
INRIA in Rennes (France)
時 間：2019年 10月10日午10:00
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.
In a first part, we will briefly remind them and compare their respective advantages but later (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.
Bio: Bruno TUFFIN received his PhD degree in applied mathematics from the University of Rennes 1 (France) in 1997. Since then, he has been with INRIA in Rennes. His research interests include developing Monte Carlo and quasi-Monte Carlo simulation techniques for the performance evaluation of telecommunication systems and telecommunication-related economical models. He is currently Area Editor for INFORMS Journal on Computing Associate Editor for ACM Transactions on Modeling and Computer Simulation. He has written or co-written three books (two devoted to simulation): Rare event simulation using Monte Carlo methods published by John Wiley & Sons in 2009, La simulation de Monte Carlo (in French), published by Hermes Editions in 2010, and Telecommunication Network Economics: From Theory to Applications, published by Cambridge University Press in 2014. His email address is [email protected] and web web page is http://www.irisa.fr/dionysos/pages_perso/tuffin/Tuffin_en.htm