State-dependent importance sampling for regularly varying random walks

José Blanchet, Jingchen LiuAdvances 2008 · DOI

TL;DR

This paper introduces two novel state-dependent importance sampling algorithms to efficiently simulate rare events in random walks with heavy-tailed (regularly varying) increments. By using Lyapunov-type inequalities to design and prove the "strong efficiency" of these estimators, the authors provide a robust framework for calculating large deviation probabilities that are otherwise computationally impossible to estimate using standard Monte Carlo methods.

What Problem Does This Paper Address?

In probability theory, "rare events" are outcomes with extremely low probabilities that nonetheless have significant impacts—think of a massive stock market crash or a 100-year flood. Simulating these events is difficult because a standard Monte Carlo approach would require billions of trials to see even a single occurrence.

For "light-tailed" distributions (like the Normal distribution), we have well-established tools like Cramer’s Theorem and exponential twisting to make these events happen more often in simulation. However, these tools fail for "heavy-tailed" distributions (like the Pareto or Cauchy distributions often found in finance and insurance). In heavy-tailed systems, a rare event usually happens because of one single "big jump" rather than the accumulation of many small deviations. This paper tackles the challenge of designing simulation algorithms that correctly capture this "big jump" logic to provide accurate estimates with bounded relative error.

Methods

The authors propose State-Dependent Importance Sampling (SDIS), where the simulation's probability distribution changes at each step based on the current position of the random walk.

  1. Algorithm 1 (Asymptotic Approximation): This method uses known large-deviation approximations to mimic the "zero-variance" change of measure. While theoretically sound, it is computationally expensive ($O(n^2)$ complexity) because it requires calculating complex normalizing constants at every step.
  2. Algorithm 2 (Mixture-Based Sampling): This is the paper's more practical contribution. It uses a mixture distribution:
  3. With probability $p$, the next step is sampled from a distribution forced to be a "big jump."
    • With probability $1-p$, the next step is sampled from the original (nominal) distribution.
  4. Lyapunov Inequalities: The core mathematical innovation is using Lyapunov functions to "tune" the parameters of these mixtures. If a specific inequality holds, the authors can mathematically guarantee that the estimator is strongly efficient (meaning the relative error doesn't explode as the event becomes rarer).

Datasets

As a theoretical mathematics and probability paper, no real-world datasets were used. Instead, the authors evaluated their algorithms using:

  • Synthetic Random Walks: Specifically, walks where increments follow a "regularly varying" distribution (a mathematical definition of heavy tails where the tail decays like a power law).
  • Financial Option Models: A "down-and-in" call option (a knock-in option) was used as a path-dependent benchmark to test if the algorithm could handle events requiring multiple specific jumps (e.g., hitting a low barrier then ending above a high strike price).

Key Insights and Ideas

  • The "Big Jump" Principle: The authors formalize the intuition that in heavy-tailed regimes, the most likely path to a rare event is a single extreme outlier. Their mixture importance sampler explicitly forces this behavior.
  • Efficiency via Lyapunov Bounds: Traditionally, Lyapunov functions are used to prove the stability of dynamical systems. Here, they are used as a design tool to bound the second moment of a simulation estimator, ensuring the variance remains under control.
  • Computational Speedup: By moving from the asymptotic approximations of Algorithm 1 to the mixture model of Algorithm 2, the authors reduced the computational complexity from $O(n^2)$ to $O(n)$, making it feasible for long-horizon simulations.

Key Results

  • Theoretical Guarantee: The authors proved that their mixture-based SDIS estimators achieve "strong efficiency" for both simple tail probabilities ($P(S_n > b)$) and complex path-dependent events.
  • Numerical Performance: In experiments simulating events with probabilities as low as $10^{-18}$, the SDIS algorithms maintained a low Coefficient of Variation (CV). For example, at $n=1000$ steps, Algorithm 2 produced an estimate of $1.16 \times 10^{-8}$ with a standard deviation of only $4.72 \times 10^{-10}$.
  • Robustness: The algorithms remained efficient even in the "moderate deviations" regime, where the target threshold isn't extremely far out in the tail.

Limitations and Future Work

  • Tail Specificity: The current work is specifically tailored to "regularly varying" distributions. While these are common, the authors note that other heavy-tailed classes (like Weibull or Lognormal) might require different Lyapunov functions.
  • Parameter Tuning: While the paper provides a framework, selecting the optimal mixture parameters ($p$ and the jump threshold $a$) still requires some analytical "guesswork" based on the specific tail behavior of the input variables.
  • Extension to Markov Processes: The authors suggest that these techniques could be applied to more complex Markovian structures (like queues or storage models), which they flagged as a direction for future research.

Summary updated

Abstract

Consider a sequence ( X k : k ≥ 0) of regularly varying independent and identically distributed random variables with mean 0 and finite variance. We develop efficient rare-event simulation methodology associated with large deviation probabilities for the random walk ( S n : n ≥ 0). Our techniques are illustrated by examples, including large deviations for the empirical mean and path-dependent events. In particular, we describe two efficient state-dependent importance sampling algorithms for estimating the tail of S n in a large deviation regime as n ↗ ∞. The first algorithm takes advantage of large deviation approximations that are used to mimic the zero-variance change of measure. The second algorithm uses a parametric family of changes of measure based on mixtures. Lyapunov-type inequalities are used to appropriately select the mixture parameters in order to guarantee bounded relative error (or efficiency) of the estimator. The second example involves a path-dependent event related to a so-called knock-in financial option under heavy-tailed log returns. Again, the importance sampling algorithm is based on a parametric family of mixtures which is selected using Lyapunov bounds. In addition to the theoretical analysis of the algorithms, numerical experiments are provided in order to test their empirical performance.
BibTeX
@inproceedings{blanchet2008state,
  author = {José Blanchet and Jingchen Liu},
  title = {{State-dependent importance sampling for regularly varying random walks}},
  booktitle = {Advances},
  year = {2008},
  doi = {10.1017/s0001867800002986},
}
Figure