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.