Accession Number:

ADA458989

Title:

Subsolutions of an Isaacs Equation and Efficient Schemes for Importance Sampling: Convergence Analysis

Descriptive Note:

Journal article preprint

Corporate Author:

BROWN UNIV PROVIDENCE RI LEFSCHETZ CENTER FOR DYNAMICAL SYSTEMS

Personal Author(s):

Report Date:

2005-08-08

Pagination or Media Count:

34.0

Abstract:

Previous papers by authors establish the connection between importance sampling algorithms for estimating rare-event probabilities, two-person zero-sum differential games, and the associated Isaacs equation. In order to construct nearly optimal schemes in a general setting, one must consider dynamic schemes, i.e., changes of measure that, in the course of a single simulation, can depend on the outcome of the simulation up till that time. The present paper and a companion paper show that classical sense subsolutions of the Isaacs equation provide a basic and flexible tool for the construction and analysis of nearly optimal schemes. Asymptotic analysis is the topic of the present paper, while the companion paper focuses on explicit methods for the construction of subsolutions, implementation aspects and numerical results.

Subject Categories:

  • Operations Research
  • Numerical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE