Efficient rare-event simulation for the maximum of heavy-tailed random walks

José Blanchet, Peter W. GlynnThe Annals of Applied Probability 2008 · DOI

Abstract

Let $(X_n : n \ge 0)$ be a sequence of i.i.d. random variables with negative mean. Defining $S_n = X_1 + \dots + X_n$, we propose an importance sampling algorithm to estimate the tail of $M = \max \{S_n : n \ge 0\}$ that is strongly efficient for both light and heavy-tailed increment distributions. Under heavy-tailed increments and specific technical assumptions, our estimator demonstrates asymptotically vanishing relative variance, meaning its coefficient of variation vanishes as the tail parameter increases. This state-dependent approach generalizes Siegmund’s (1979) algorithm and utilizes new Lyapunov-type inequalities to prove efficiency.

Introduction

In fields ranging from insurance risk (calculating ruin probabilities) to queueing theory (estimating long wait times), researchers must frequently calculate the probability that the maximum value of a random walk ($M$) exceeds a very high threshold ($b$). When the mean of the walk is negative, reaching such a threshold is a "rare event."

Standard Monte Carlo simulations are notoriously inefficient for these tasks. As the event becomes rarer, the number of samples required to observe even a single success grows exponentially. Importance Sampling (IS) addresses this by "twisting" the probability distribution to make the rare event more frequent, then re-weighting the results. However, traditional IS techniques, such as Siegmund’s algorithm, were designed for "light-tailed" distributions (e.g., Gaussian). When applied to "heavy-tailed" distributions (e.g., Pareto or Log-normal)—where a single massive jump often causes the rare event—these traditional methods fail, often producing estimators with infinite variance.

Methodology: State-Dependent Importance Sampling

The authors propose a state-dependent importance sampling algorithm that adapts the increment distribution based on the current position of the random walk.

1. Guidance via Asymptotic Theory

Unlike standard IS where the "twist" is constant, this algorithm changes the distribution at each step. The change of measure is guided by the Pakes–Veraberbeke theorem, which provides an asymptotic approximation of the tail probability. The algorithm essentially samples increments from a distribution conditioned on a "large jump" occurring eventually, based on the current distance to the goal.

2. Lyapunov Functions for Efficiency

The core theoretical contribution is a framework using Lyapunov-type inequalities to bound the second moment of the estimator. While Lyapunov functions are typically used to prove stability in dynamical systems, the authors demonstrate they are a powerful tool for proving the efficiency of simulation algorithms, ensuring the variance does not "blow up" as the event becomes rarer.

Key Insights

  • The "Single Big Jump" Principle: In heavy-tailed systems, rare events usually happen because of one massive outlier rather than a sequence of moderately large steps. The algorithm mimics this physical reality by occasionally forcing a large jump.
  • Vanishing Relative Error: A significant finding is that for many heavy-tailed distributions, the estimator's coefficient of variation (a measure of relative error) actually goes to zero as the threshold $b$ goes to infinity. This makes the algorithm exceptionally robust for extremely rare events.
  • Unification of Theory: The method serves as a bridge between light- and heavy-tailed theory. In the presence of light tails, the procedure naturally simplifies back to Siegmund’s (1979) classic algorithm.

Numerical Results and Benchmarks

As a theoretical study, the algorithm was evaluated using simulated stochastic models rather than empirical datasets, comparing the new "BG" algorithm against existing methods like Asmussen & Kroese (AK) and Dupuis, Leder & Wang (DLW):

  • M/G/1 Queue: In simulations with Pareto-distributed service times, the BG algorithm showed a decreasing coefficient of variation as the threshold increased (e.g., from 3.68 at $S_0 = -10$ to 2.83 at $S_0 = -650$), confirming the "vanishing relative error" theory.
  • G/G/1 Queue: The algorithm successfully handled models with Weibull-type service tails, a case where other specialized methods were previously unavailable or inefficient.

Conclusion and Future Work

The proposed algorithm provides the first importance sampling approach that is strongly efficient for estimating the maximum of a random walk with general heavy-tailed increments. While the algorithm requires $O(b)$ steps per simulation run and involves evaluating complex asymptotic functions, its theoretical robustness is a major step forward. The authors suggest that the Lyapunov framework developed here could be applied to more complex problems, such as multidimensional random walks or high-dimensional state-dependent importance sampling.

Summary updated

Abstract

Let (Xn : n≥0) be a sequence of i.i.d. r.v.’s with negative mean. Set S0=0 and define Sn=X1+⋯+Xn. We propose an importance sampling algorithm to estimate the tail of M=max {Sn : n≥0} that is strongly efficient for both light and heavy-tailed increment distributions. Moreover, in the case of heavy-tailed increments and under additional technical assumptions, our estimator can be shown to have asymptotically vanishing relative variance in the sense that its coefficient of variation vanishes as the tail parameter increases. A key feature of our algorithm is that it is state-dependent. In the presence of light tails, our procedure leads to Siegmund’s (1979) algorithm. The rigorous analysis of efficiency requires new Lyapunov-type inequalities that can be useful in the study of more general importance sampling algorithms.
BibTeX
@article{blanchet2008efficient,
  author = {José Blanchet and Peter W. Glynn},
  title = {{Efficient rare-event simulation for the maximum of heavy-tailed random walks}},
  journal = {The Annals of Applied Probability},
  year = {2008},
  doi = {10.1214/07-aap485},
}
Figure