Importance Sampling and the Subsolutions of an Associated Isaacs Equation

重要性采样和相关 Isaacs 方程的子解

• 批准号: 0706003
• 负责人: Paul Dupuis
• 金额: $ 70.97万
• 依托单位: Brown University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-08-15 至 2011-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0706003&HistoricalAwards=false
• 关键词: Importance; Sampling; Subsolutions; Associated; Isaacs

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.

在许多科学领域，用于快速模拟罕见事件的一种广泛使用的技术是重要采样[is]。IS的基本思想是模拟不同概率分布下的系统，并通过似然比对偏性进行校正。在过去的三十年中，大多数开发的IS方案都是基于启发式的，这导致了性能有问题的算法。相比之下，本研究项目开发了一种系统的方法，用于为广泛类别的过程模型构建简单、有效的信息系统方案。这种方法利用了IS和相关微分对策之间的密切联系。结果表明，与游戏相关的Isaacs方程的子解可以用来构建性能可以严格表征的IS方案。研究人员特别感兴趣的是在随机网络、亚稳态分析、不连续动力学系统、小噪声扩散、计数问题、IS估计器的高阶矩分析和重尾分布等领域发展重要抽样的理论和实践方面。该项目还将研究使用子解决方案来构建和分析基于分支过程的快速仿真方法，例如拆分和RESTART。一些罕见事件，如化学物理模型中稳定井之间的过渡、高度可靠的通信系统中的数据丢失，或者保险索赔中的意外大额赔付，通常是系统整体行为的关键定量指标。它们还在风险评估和管理中发挥核心作用。需要可靠的数值方法来设计系统和协议，以尽量减少和减轻罕见事件的负面影响。重要采样是实现罕见事件快速模拟的主要技术。在过去的三十年里，重要性采样算法在许多不同的应用领域得到了发展。然而，迄今为止的发展在很大程度上是临时的，没有适当的理论基础。从业者在构建重要抽样算法时依赖于一些基本的启发式方法。这些方案的性能是由有限的数值证据支持的，不幸的是，最近的工作表明，这些启发式通常是不可靠的。本课题将概率论的新思想、博弈论和偏微分方程的新工具引入到重要抽样方案的设计和分析问题中。这项工作旨在开发系统的方法来构建和严格分析可靠的算法。