Publication 2005-010

It was established in [4, 5] that importance sampling algorithms for estimating rare-event probabilities are intimately connected with twoperson zero-sum differential games and the associated Isaacs equation. The purpose of the present paper and a companion paper [6] is to show that the classical sense subsolutions of the Isaacs equation can be used as a basic and flexible tool for the construction and analysis of efficient importance sampling schemes. The importance sampling algorithms based on subsolutions are dynamic in the sense that during the course of a single simulation, the change of measure used at each time step may depend on the outcome of the simulation up until that time. While [6] focuses on a theoretical aspects, the present paper discusses explicit methods of constructing subsolutions, implementation issues, and simulation results.