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.
