Abstract
This paper introduces a new Importance Sampling scheme, called Adaptive Twisted Importance Sampling (ATIS), which is adequate for the improved estimation of rare event probabilities in the range of moderate deviations pertaining to the empirical mean of real i.i.d. summands. It is based on a sharp approximation of the density of long runs extracted from a random walk conditioned on its end value.
Introduction
In fields such as industrial reliability, telecommunications, and financial risk management, the estimation of rare event probabilities—events occurring with probabilities as low as $10^{-8}$—is a critical task. Standard Monte Carlo (MC) simulations are often computationally prohibitive for these scenarios, as the number of samples required to observe a sufficient number of events scales inversely with the probability of the event itself.
Importance Sampling (IS) addresses this by "tilting" the underlying probability distribution to make the rare event more frequent, then re-weighting the results to ensure an unbiased estimate. However, for "moderate deviations"—events that are rare but do not fall into the extreme tail behavior described by standard Large Deviation Theory—traditional IS techniques often suffer from high variance. This paper proposes Adaptive Twisted Importance Sampling (ATIS), a method that leverages the structure of conditioned random walks to achieve superior variance reduction.
The Challenge of Moderate Deviations
The optimal sampling distribution for any IS scheme is the distribution of the random variables conditioned on the occurrence of the rare event. In practice, this conditional distribution is unknown and difficult to approximate. The classical approach, based on the Gibbs conditional principle, involves a global shift in the mean of the distribution (tilting). While effective for extreme deviations, this global shift is often suboptimal for moderate deviations or finite sample sizes. The core problem addressed here is finding a more granular, path-dependent approximation of the conditional distribution that remains computationally tractable.
Methodology: Adaptive Twisted Importance Sampling (ATIS)
ATIS moves beyond a simple static shift in the mean by employing a recursive, path-dependent sampling strategy. The method is built upon two primary innovations:
1. Sharp Conditional Path Approximation
The authors derive a sharp approximation for the density of a partial random walk $(X_1, \dots, X_k)$ conditioned on the final sum $S_n$. Unlike standard approaches that rely on rough large deviation estimates, this method utilizes Edgeworth expansions to capture the local fluctuations and behavior of the path more accurately. This allows the sampler to follow the "typical path" that leads to the rare event.
2. The ATIS Algorithm
The algorithm proceeds in two distinct phases:
- Adaptive Phase: For the first $k$ components of the path, the algorithm samples recursively. At each step $i \in \{1, \dots, k\}$, the sampling density is adjusted dynamically based on the "remaining" sum required to reach the target threshold. This ensures the path stays on a trajectory likely to result in the rare event.
- Standard Phase: The remaining $n-k$ components are sampled using a standard tilted distribution (the classical i.i.d. twisted scheme).
By choosing an appropriate $k$, the algorithm balances the high precision of the adaptive approach with the lower computational cost of standard tilting.
Theoretical Insights and Efficiency
The primary advantage of ATIS lies in its focus on "typical paths." The authors demonstrate that an importance sampling scheme does not need to be globally optimal; it only needs to be a high-quality approximation along the sequences of random variables most likely to trigger the rare event.
Propositions 21 and 22 in the paper provide the theoretical foundation for this efficiency, showing that the Mean Square Error (MSE) of the ATIS estimate is significantly lower than that of classical approaches. Specifically, the relative gain in simulation efficiency is shown to be proportional to $\sqrt{n-k}/\sqrt{n}$. Crucially, the computational burden required to achieve a specific relative precision does not grow exponentially with the sample size $n$, a common pitfall in rare event simulation.
Numerical Results
The authors validated ATIS using synthetic simulations for two benchmark distributions:
- Gaussian Case: Using i.i.d. standard normal variables with $n=100$ and a target probability $P_n \approx 10^{-2}$, ATIS (with $k=60$) produced significantly tighter confidence intervals and more stable estimates compared to the classical i.i.d. twisted scheme.
- Exponential Case: In simulations with i.i.d. exponential variables, the stability of ATIS was even more pronounced. While the classical sampler required $L=10,000$ replications to begin stabilizing, ATIS achieved superior accuracy and stability with only $L=1,000$ replications.
Limitations and Future Directions
While ATIS offers significant variance reduction, it introduces additional computational complexity. The recursive nature of the sampling requires solving equations and performing numerical approximations (using a parameter $M$ for mixture density) at each step of the adaptive phase. This increases the "wall-clock" time per sample compared to simple tilting. Furthermore, the choice of $k$ and $M$ requires careful tuning; in very high-dimensional settings, the number of Monte Carlo points $M$ needed for the mixture approximation may grow.
Future work could explore extending this path-adaptive logic to more complex, non-linear statistics beyond the empirical mean, such as M-estimators or robust means.
Conclusion
Adaptive Twisted Importance Sampling represents a significant step forward in the simulation of rare events. By bridging the gap between the global Gibbs principle and the local dynamics of conditioned random walks, ATIS provides a robust framework for estimating probabilities in the moderate deviation range with high precision and reduced variance.
Summary updated