Research on Stochastic Processes and Optimization

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

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.