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