Importance Sampling and the Subsolutions of an Associated Isaacs Equation

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

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.