This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Dupuis, P. Articles by Wang, H. Search for Related Content

Subsolutions of an Isaacs Equation and Efficient Schemes for Importance Sampling

Lefschetz Center for Dynamical Systems, Brown University, Providence, Rhode Island 02912, USA
Lefschetz Center for Dynamical Systems, Brown University, Providence, Rhode Island 02912, USA
dupuis{at}dam.brown.edu, http://www.dam.brown.edu/people/facultypage.dupuis.html
huiwang{at}dam.brown.edu, http://www.dam.brown.edu/people/facultypage.huiwang.html

It was established in Dupuis and Wang [Dupuis, P., H. Wang. 2004. Importance sampling, large deviations, and differential games. Stoch. Stoch. Rep. 76 481–508, Dupuis, P., H. Wang. 2005. Dynamic importance sampling for uniformly recurrent Markov chains. Ann. Appl. Probab. 15 1–38] that importance sampling algorithms for estimating rare-event probabilities are intimately connected with two-person zero-sum differential games and the associated Isaacs equation. This game interpretation shows that dynamic or state-dependent schemes are needed in order to attain asymptotic optimality in a general setting. The purpose of the present paper is to show that classical subsolutions of the Isaacs equation can be used as a basic and flexible tool for the construction and analysis of efficient dynamic importance sampling schemes. There are two main contributions. The first is a basic theoretical result characterizing the asymptotic performance of importance sampling estimators based on subsolutions. The second is an explicit method for constructing classical subsolutions as a mollification of piecewise affine functions. Numerical examples are included for illustration and to demonstrate that simple, nearly asymptotically optimal importance sampling schemes can be obtained for a variety of problems via the subsolution approach.

Key Words: importance sampling; large deviations; Isaacs equation; rare events; simulation; Monte Carlo
History: Received: August 11, 2005; revision received: June 2, 2006;