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与相关差异游戏之间的紧密联系。 事实证明，与游戏相关的ISAACS方程的种类可以用于构建，其性能可以严格表征。 研究人员特别有兴趣在随机网络，亚稳定性分析，不连续动态的系统，小噪声扩散，计数问题，对IS IS估计器的高阶分析和重尾分布的区域中开发重要性采样的理论和实践方面。 该项目还将研究基于分支过程的快速模拟方法的构建和分析，例如分裂和重新启动。Rare事件，例如化学物理学模型中稳定井之间的过渡，高度可靠的通信系统中的数据丢失，或在保险索赔中出乎意料的大型支出，通常是系统整体行为的关键量化。 它们在风险评估和管理中也起着核心作用。 为了设计可以最大程度地减少和减轻罕见事件的负面影响的系统和协议，需要可靠的数值方法。 快速模拟罕见事件的主要技术是重要性采样。 在过去的30年中，针对许多不同的应用领域开发了重要性采样算法。 但是，迄今为止的发展在很大程度上是临时的，没有适当的理论基础。 从业者依靠一些基本的启发式方法来构建重要性采样算法。 这些方案的性能得到了有限的数值证据的支持，不幸的是，最近的工作表明，这些启发式方法通常是不可靠的。 该项目从概率理论和工具中带来了从游戏理论和部分微分方程到设计和分析重要性抽样方案的问题的新想法。 该作品旨在开发系统的方法，以对可靠算法进行构建和严格分析。