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计划，广泛的过程模型类。 这种方法利用了IS和相关微分博弈之间的密切联系。 事实证明，与游戏相关的Isaacs方程的子解可以用来构建IS方案，其性能可以严格表征。 调查人员特别感兴趣的是发展理论和实践方面的重要性抽样在随机网络，亚稳定性分析，系统与不连续动态，小噪声扩散，计数问题，分析高阶矩的IS估计，和重尾分布。 该项目还将研究使用子解构建和分析基于分支过程的快速模拟方法，如分裂和重新开始。罕见事件，如化学物理模型中稳定威尔斯之间的转换，高度可靠的通信系统中的数据丢失，或意外的保险索赔中的巨额支出，通常是系统整体行为的关键定量测量。 它们还在风险评估和管理方面发挥核心作用。 需要可靠的数值方法，以设计系统和协议，可以尽量减少和减轻罕见事件的负面影响。 重要抽样是稀有事件快速模拟的主要技术。 重要性抽样算法在过去的三十年中已经发展到许多不同的应用领域。 然而，迄今为止的发展在很大程度上是临时性的，没有适当的理论基础。 从业者在构建重要性抽样算法时依赖于一些基本的算法。 这些方案的性能得到了有限的数值证据的支持，不幸的是，最近的工作表明，这些算法一般是不可靠的。 这个项目带来了新的想法，从概率论和工具，从博弈论和偏微分方程的问题的设计和分析的重要性抽样方案。 这项工作的目的是开发系统的方法，建设和严格的分析可靠的算法。