Importance sampling, large deviations, and differential games

Professor Paul Dupuis

ABSTRACT

It is tempting to use importance sampling when estimating probabilities and functionals associated with rare events.  A heuristic that has emerged is the following:  the measure used to prove the lower bound in large deviations is a good one to use for importance sampling.  However, recent examples due to Glasserman and Wang show that this distribution can actually perform poorly, in that the resulting estimator can have high variance.  The conflict between the two can be resolved once one recognizes that there are many measures that can be used to prove the lower bound.  In the first part of the talk we will review the basic formulas of importance sampling.  We then specialize to the setting of Cramer's Theorem, which is a convenient vehicle for illustrating the main points.  We relate the variance associated with the sampling scheme to a differential game, and thereby characterize the nearly optimal sampling schemes.  (Joint work with Hui Wang.)