The research objective of this Faculty Early Career Development (CAREER) project is to investigate and develop a framework that exploits asymptotic analysis, expressed at a coarse scale, to systematically generate efficient rare-event simulation algorithms for complex stochastic systems, which must necessarily be implemented at a fine scale. The objective is to study five types of environments that exhibit stylized features that have not been well studied in rare-event simulation, namely, a) Stochastic recursions with heavy-tails (which are used to model insurance risk and reservoir processes), b) Heavy-tailed queues (which arise in database and networking applications), c) Counting problems and inference for combinatorial structures (arising in sociology and biology), d) Location of objects immersed in a random medium (with particular emphasis on military applications where one needs to find targets that have eluded detection for long time), and e) Random fields (which arise in settings such as oceanography, environmental studies and medical imaging). The strategy consists in connecting large deviations analysis with algorithmic design of efficient simulation estimators. A key tool that we exploit in the design and performance analysis of our algorithms is a systematic use of Lyapunov bounds for Markov chains, combined with parametric families of importance sampling distributions.
Events such as environmental or natural disasters, major market crashes, pension and insurance breakdowns and terrorist attacks are rare but consequential. If successful, the proposed research program will provide efficient computational tools for risk assessment of such events which exhibit features such as heavy-tails, complex dependence and incorporation of combinatorial objects. Efficient evaluation of rare-event probabilities can provide decision makers with key quantitative policy assessment metrics and accompanying insights. Examples include computing the probability that a target is able to evade a set of detectors as well as its conditional most likely location, and assessing ruin probabilities for purposes of sizing the capital reserve of insurance and financial companies.
The goal of this research is to create and investigate a framework that exploits asymptotic analysis, expressed at a coarse scale, to systematically generate efficient rare-event simulation algorithms for complex stochastic systems, which must necessarily be implemented at a fine scale. In pursuit of this goal, a powerful set of tools has been built, encompassing common principles that cover rare-event analysis in the following environments: a) Stochastic recursions with heavy-tails (used to model insurance risk processes), b) Heavy-tailed queues (arising in logistics and network applications), c) Counting problems and inference for combinatorial structures (used in sociology and biology), d) Location of objects immersed in a random medium, and e) Random fields (arising in settings such as oceanography and medical imaging). This project’s educational goal includes creating tools that provide the students with a modern perspective on the analysis of probabilistic models, in which computation goes hand-in-hand with exposure to both classical methods and asymptotic analysis. A new course on modeling and state-of-the-art Monte Carlo computation was created with a focus on the trade-offs between model fidelity and computational complexity. The course has been taught now several times across different schools at Columbia University. The project also includes a significant undergraduate research experience component. In addition, several students where mentored under the sponsorship of this grant, including minority students. Some of these students have become faculty members in mathematical sciences in various U.S. universities. Others are now working in the financial sector industry, also in the U.S. Intellectual Merit: Rare event analysis is known to be challenging both analytically and computationally. Although approximations might be known for some performance measures of interest, it is often the case that the approximation is too rough or the convergence rate too slow. One might also be interested in predicting the most likely way an event occurs and not only its likelihood. In such settings, efficient simulation algorithms are clearly valuable. For example, the enclosed figures show a typical path leading to the loss of a call (due to high congestion) during an operation cycle in a critical call center (e.g. 911). The cycle lasts for two units of time (think of it as day and night shifts), this is represented in the t axis. The number of call center operators is assumed to be 100, the quantity Q(t,y) is the number of customers who are in the system at time t and whose call is estimated to last y units of time or more. One can see that the loss event, which has a very low likelihood, builds up and peaks at around time 1.5. The PI built and investigated a framework aimed at designing efficient stochastic simulation techniques for rare event analysis. Substantial emphasis is placed on rigorous evaluation techniques aimed at showing optimal running times as the event of interest becomes increasingly rare. The PI systematically combined techniques from different, apparently unrelated mathematical areas, to successfully produce such a framework. For example, Lyapunov inequalities, which are traditionally applied in stability of Markov chains, were used in this project in applications to combinatorial analysis and large deviations estimates. The PI’s framework has been applied to areas covering the environments a) to e) described earlier. The specific findings are reported in top journals in Probability and Operations Research, including Annals of Applied Probability, Bernoulli, Mathematics of Operations Research, Stochastic Processes and Their Applications, Stochastic Systems, among others. Broader Impact: Events such as environmental or natural disasters, major market crashes, pension and insurance breakdowns and terrorist attacks are rare but consequential. The project has built efficient computational tools for risk assessment of such events which exhibit features such as heavy-tails, complex dependence and incorporation of combinatorial objects. The tools are to be applied to models that are informed by experts with domain knowledge. However, this research project’s outcomes provide modelers with more freedom because they can concentrate on model fidelity and less worried about tractability of computations. In fact, the results of this project are currently being used by the PI in models of systemic risk for insurance and reinsurance networks which are informed by actual data. Results on this and other specific applications will be provided in future proposals. We mentioned earlier that several students, some of them minorities, were mentored under this grant. Two students, one of them a female, went on to become faculty members, one at Boston University (Department of Mathematics and Statistics) and the other one at Stony Brook (Department of Applied Mathematics). In addition, two undergraduate students, one of them female, worked on applied research projects partly. A doctoral course on large deviations theory and stochastic simulation has been taught in the School of Engineering and the School of Arts and Sciences at Columbia University. The PI participated on outreach conferences such as SACNAS, sponsored by NSF.
