IMA Complex Systems Seminar
1:30, Thursday, January 22, 2004
Importance sampling, large deviations, and differential games
Division of Applied Mathematics
Providence, RI 02912
(Joint work with Paul Dupuis.) Importance sampling is a variance reduction technique for efficient estimation of rare-event probabilities by Monte Carlo. In standard importance sampling schemes, the system is simulated using an a priori fixed change of measure suggested by a large deviation analysis. In this work, we consider adaptive importance sampling schemes. By "adaptive", we mean that the change of measure depends on the sample history. The existence of asymptotically optimal adaptive schemes is demonstrated in great generality. The implementation of the adaptive schemes is carried out with the help of a limiting Isaacs equation. The idea of subsolution is also exploited for constructing implementation-friendly adaptive schemes.