Research on Stochastic Processes and Optimization

随机过程与优化研究

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

The proposed research is concerned with two topics in the area of stochastic processes and optimization: (1) theoretical foundations for importance sampling, (2) large deviations analysis of urn occupancy models. Importance sampling is a widely used Monte Carlo simulation technique for the estimation of quantities that are largely determined by rare events. With few exceptions, importance sampling algorithms are based on a change of measure that is not allowed to adapt in the course of generating a sample. Recent studies, however, indicate that these schemes may fail miserably in very common circumstances. These difficulties reflect the absence of a broad theoretical foundation for importance sampling. One contribution of the proposed research is to build such a foundation in a general setting. Roughly speaking, at the heart of any importance sampling problem is a stochastic game, and an understanding of this game is the key to designing and analyzing efficient importance sampling algorithms. This perspective motivates the concept of dynamic importance sampling, where the change of measure is allowed to vary depending on the simulation history. It can be shown that dynamic schemes, properly designed, are optimal in a suitable sense. The second topic, urn occupancy problems, is concerned with the distribution of multiple balls in multiple urns. This classical topic has found applications in many fields. The proposed research concerns large deviation approximations, new techniques for explicitly solving the associated variational problem, and the development of relations between equilibrium distributions for stochastic networks and occupancy problems.If one were to ask an average person whether unlikely events are important, their first response might be that an event with very little chance of happening could not be significant. After a moment's reflection, however, they would realize that such events have a profound impact in many circumstances. For example, measuring credit risk is very important to those who manage portfolios of loans, corporate bonds, and other financial instruments that are subject to default risk. Often the problem reduces to estimating the probability of default, which is usually very small, especially for highly rated obligors. However, an accurate estimation is crucial for risk management because these rare defaults can induce significant losses. Similar considerations apply in many other circumstances, especially when performance standards are stringent. The dominant technique for estimating small probabilities has been a simulation algorithm called importance sampling. However, the traditional design methodology for importance sampling has very limited applications and has been observed to break down in very common situations. Part of the proposed research is concerned with the most basic question, that is, how to build a broad theoretical foundation for importance sampling, upon which efficient algorithms can be designed for very general problems. A new concept of design is introduced in the proposal and the resulting importance sampling algorithms work well in practice. The other part of the proposal is concerned with a class of urn occupancy models. These models are very useful in the design and analysis of large-scale networks, biological systems, and physics. However, due to the complexity of the models, approximation becomes exceedingly important. The proposed research will develop an asymptotic method that can yield good approximations with only a modest computation effort.

本论文主要研究随机过程与最优化领域的两个问题：（1）重要抽样的理论基础;（2）骨灰盒占用模型的大偏差分析。重要性抽样是一种广泛使用的蒙特卡罗模拟技术，用于估计在很大程度上由罕见事件决定的数量。除了少数例外，重要性抽样算法是基于在生成样本的过程中不允许适应的测量变化。然而，最近的研究表明，这些计划在非常常见的情况下可能会失败。这些困难反映了重要性抽样缺乏广泛的理论基础。拟议研究的一个贡献是在一般环境中建立这样一个基础。粗略地说，任何重要性抽样问题的核心都是一个随机博弈，对这个博弈的理解是设计和分析有效的重要性抽样算法的关键。这种观点激发了动态重要性采样的概念，其中允许测量的变化取决于模拟历史。它可以表明，动态格式，适当的设计，在适当的意义下是最优的。第二个主题，瓮占有问题，是关于多个球在多个瓮中的分布。这一经典课题已在许多领域得到应用。拟议的研究涉及大偏差近似，新技术，明确解决相关的变分问题，和发展之间的关系的平衡分布的随机网络和occupancy problems.If一个人问一个普通人是否不太可能的事件是重要的，他们的第一反应可能是，一个事件与非常小的机会发生可能是不重要的。 然而，经过片刻的思考，他们会意识到，这些事件在许多情况下都有深远的影响。例如，衡量信用风险对于那些管理贷款、公司债券和其他面临违约风险的金融工具的投资组合的人来说非常重要。这个问题常常归结为估计违约概率，而违约概率通常很小，特别是对于高评级的债务人。然而，准确的估计对于风险管理至关重要，因为这些罕见的违约可能导致重大损失。 类似的考虑适用于许多其他情况，特别是当性能标准很严格时。 估计小概率的主要技术是一种称为重要性抽样的模拟算法。然而，传统的设计方法的重要性抽样有非常有限的应用程序，并已被观察到打破在非常常见的情况。部分拟议的研究涉及最基本的问题，即如何建立一个广泛的理论基础的重要性抽样，在此基础上，可以设计出有效的算法非常一般的问题。该算法引入了一种新的设计思想，并在实际应用中取得了较好的效果。该建议的另一部分是关于一类骨灰盒占用模型。这些模型在大规模网络、生物系统和物理学的设计和分析中非常有用。然而，由于模型的复杂性，近似变得非常重要。拟议的研究将开发一种渐近方法，可以产生良好的近似只有一个适度的计算工作。