Past Awards
The challenge of efficient rare-event simulation arises in many areas of applied probability and has motivated the development of theory and algorithms for over thirty years. Most advances in the field have addressed models built from light-tailed distributions and have relied on importance sampling through an exponential change of measure.
This series of papers marks a major advance in the design and analysis of provably efficient simulation algorithms. They contain new algorithms for simulation of rare-event probabilities in multi-dimensional random walks, multiple-server queues, and counting problems in combinatorial optimization and statistics. They specifically address the setting of queueing systems with heavy tails, which has attracted much attention from researchers.
A unifying theme of the papers is an innovative analysis through Lyapunov functions. The papers show that this approach can be used in problems as diverse as multi-dimensional queueing systems and combinatorial counting problems. By introducing a systematic approach to the development and analysis of algorithms, the papers have opened new opportunities for research in the field.