Abstract
We consider the problem of efficient estimation via simulation of first passage time probabilities for a multidimensional random walk with heavy-tailed increments. In addition to being a natural generalization to the problem of computing ruin probabilities in insurance - in which the focus is the maximum of a one-dimensional random walk with negative drift - this problem captures important features of large deviations for multidimensional heavy-tailed processes (such as the role played by the mean of the process in connection to the location of the target set). We develop a state-dependent importance sampling estimator for this class of multidimensional problems. Then, using techniques based on Lyapunov inequalities, we argue that our estimator is strongly efficient in the sense that the relative mean squared error of our estimator can be made arbitrarily small by increasing the number of replications, uniformly as the probability of interest approaches 0.
Introduction
In finance and insurance, "ruin" represents the ultimate rare event: the point at which total losses exceed available capital. For companies managing multiple lines of business, calculating this probability is a critical regulatory requirement. However, when risks exhibit "heavy-tailed" behavior—where extreme outliers occur more frequently than predicted by Gaussian models—standard Monte Carlo simulation methods become computationally prohibitive.
A significant breakthrough by Jose Blanchet and Jingchen Liu (2010) addresses this by developing a state-dependent importance sampling (IS) algorithm. Their method remains "strongly efficient" even as the event of interest becomes vanishingly rare, providing a robust tool for multidimensional risk assessment.
Methodology: State-Dependent Mixtures and Lyapunov Bounds
The core challenge in heavy-tailed systems is that rare events typically occur due to a single catastrophic increment—the "one-big-jump" phenomenon—rather than a sequence of small adverse movements. Traditional IS techniques designed for light-tailed data fail to capture this.
The authors propose a state-dependent mixture distribution. At each step of the simulation, the algorithm selects a new distribution based on the current position of the random walk. This mixture consists of:
- Nominal Dynamics: A component following the original distribution.
- Biased Dynamics: A component designed to produce a large jump toward the ruin set.
To prove the efficiency of this approach, the authors utilize Lyapunov inequalities, a technique borrowed from control theory. By constructing appropriate Lyapunov functions, they bound the second moment of the estimator, ensuring that the relative error remains bounded as the target probability approaches zero.
Geometry and the One-Big-Jump Heuristic
In a multidimensional setting, the geometry of the "target set" (the ruin zone) relative to the process's drift is paramount. The algorithm identifies an optimal direction to "push" the process to trigger the necessary large jump.
As shown in Figure 1, the orientation of the target set $A$ and the vector $v^*$ define the "cone of directions" that the sampler uses to bias the increments. This geometric approach allows the method to handle complex, non-convex ruin sets that were previously inaccessible to efficient simulation.
Key Results and Efficiency
The paper establishes two primary theorems:
- Theorem 1 (Bounded Relative Error): Confirms that the state-dependent IS estimator maintains a bounded relative error regardless of how rare the event becomes.
- Theorem 2 (Computational Complexity): Demonstrates that a bias-controlled version of the algorithm can achieve a prescribed accuracy with a computational cost that scales linearly ($O(b)$) with the rarity parameter.
Furthermore, the Lyapunov functions used for the proofs provide new analytical upper bounds for large deviation probabilities, bridging the gap between simulation and theoretical probability.
Conclusion and Future Directions
While the framework is powerful, its implementation requires calculating jump probabilities into specific sets at each step, which may be computationally intensive for complex increment distributions. Future work may address cases where increments lack a defined mean (index $\alpha \leq 1$) or where the increment distributions are harder to sample in polar coordinates. Nonetheless, this research provides a foundational tool for managing multidimensional heavy-tailed risks in modern financial systems.
Summary updated