Importance Sampling and the Subsolutions of an Associated Isaacs Equation

点击翻译按钮获取中文摘要

In many scientific areas, an extensively used technique for the fast simulation of rare events is importance sampling [IS]. The basic idea of IS to simulate the system under a different probability distribution, and correct for biasedness via the likelihood ratio. During the last three decades, most of the IS schemes that were developed were based on heuristics, and led to algorithms with questionable performance. In contrast, this research project develops a systematic methodology for the construction of simple, efficient IS schemes for broad classes of process models. This approach capitalizes on the intimate connection between IS and a related differential game. It turns out that subsolutions to the Isaacs equation associated with the game can be used to build IS schemes whose performance can be rigorously characterized. The investigators are particularly interested in developing both theoretical and practical aspects of importance sampling in the areas of stochastic networks, metastability analysis, systems with discontinuous dynamics, small noise diffusions, counting problems, analysis of higher-order moments of IS estimators, and heavy-tailed distributions. The project will also study the use of subsolutions for the construction and analysis of fast simulation methods based on branching processes, such as splitting and RESTART.Rare events, such as transitions between stable wells in a model from chemical physics, data loss in a highly reliable communication system, or unexpectedly large payouts in insurance claims, are often key quantitative measures of a system's overall behavior. They also play a central role in risk assessment and management. Reliable numerical methods are required in order to design systems and protocols that can minimize and mitigate the negative effects of rare events. The main technique for the fast simulation of rare events is importance sampling. Importance sampling algorithms have been developed over the last thirty years for many different application areas. However, the development to date has been largely ad hoc and without a proper theoretical foundation. Practitioners have relied on a few rudimentary heuristics in constructing importance sampling algorithms. The performance of these schemes was supported by limited numerical evidence, and unfortunately recent work has shown that these heuristics are in general unreliable. This project brings new ideas from probability theory and tools from game theory and partial differential equations to the problem of design and analysis of importance sampling schemes. The work aims to develop systematic methods for the construction and rigorous analysis of reliable algorithms.