Bounded Relative Error for Heavy Tailed Rare Event Simulation

This direction is merged into another direction: rare event estimation, asymptotically vanishing relative error. Its last version stays readable and citable here.

Version 1 of 129 papers47 conceptsfrozen 2026-10-04

In fields ranging from insurance risk to wireless communications, the most important events are often the rarest. Calculating the probability of a "ruin" event—where an insurance company's losses exceed its capital—or an "outage"—where a receiver loses its signal—is critical for system design. However, standard Monte Carlo simulations fail spectacularly in these regimes. As the event becomes rarer, the number of samples required to observe it even once grows inversely with the probability, leading to an explosion in computational cost.

To solve this, researchers have developed a framework of Importance Sampling (IS) designed to achieve Bounded Relative Error. This property ensures that the computational effort required to reach a specific precision remains constant, or even decreases, no matter how rare the event becomes.

The Failure of the Bell Curve

In a "light-tailed" (Gaussian) world, rare events usually happen through the accumulation of many small, unlucky fluctuations. To simulate these, you can simply "tilt" the distribution, shifting the mean so that the rare event becomes common.

However, many real-world risks are heavy-tailed (or subexponential). In these systems, extreme outliers are far more common than a bell curve suggests. As Bohan Chen, Chang-Han Rhee, and Bert Zwart explore in Efficient Rare-Event Simulation for Multiple Jump Events in Regularly Varying Random Walks and Compound Poisson Processes, rare events in heavy-tailed systems typically occur because of a "single big jump"—one massive outlier rather than a series of small ones. Standard tilting methods fail here because they try to force many small jumps, which is an extremely unlikely way for a heavy-tailed system to fail, leading to estimators with infinite variance.

Defining Strong Efficiency

The gold standard for a rare-event simulator is Strong Efficiency. An estimator is strongly efficient if its relative error (the standard deviation divided by the mean) remains bounded as the probability of the event approaches zero.

Peter W. Glynn and Jingchen Liu demonstrated in Efficient rare-event simulation for the maximum of heavy-tailed random walks that it is possible to achieve not just bounded error, but asymptotically vanishing relative error. This means the simulation actually becomes more precise the rarer the event gets—the exact opposite of standard Monte Carlo behavior.

The Mechanism: State-Dependent Importance Sampling

To achieve this efficiency, the simulation must "know" how the rare event is likely to happen. This is often done through state-dependent importance sampling. Instead of using a fixed biased distribution, the algorithm changes the sampling distribution at each step based on the current state of the system.

Jingchen Liu has pioneered the use of Lyapunov-type inequalities to design these samplers. By satisfying specific mathematical bounds, researchers can prove that the second moment of the estimator stays controlled. In State-dependent importance sampling for regularly varying random walks, Liu shows that using mixture distributions—which combine a "large jump" component with a "regular" component—allows the simulation to capture the different ways a ruin event might occur, ensuring the simulation terminates in finite time even when the underlying process might not.

Simplifying the Approach: State-Independence

While state-dependent methods are powerful, they can be mathematically complex to implement. Karthyek Murthy and Sandeep Juneja challenged the necessity of this complexity in State-independent Importance Sampling for Random Walks with Regularly Varying Increments. They showed that by carefully decomposing the rare event into "big jump" and "residual" components, one can achieve the same vanishing relative error using simpler, state-independent measures. This makes the techniques much more accessible for practical engineering problems.

Applications in High-Reliability Systems

The practical impact of these theoretical bounds is most visible in the verification of ultra-reliable systems:

By shifting the focus from "how many samples" to "how the error scales," this research direction has turned the simulation of "impossible" rare events into a tractable engineering reality.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_bounded_relative_error_for_heavy_tailed__9901dab0,
  title = {Bounded Relative Error for Heavy Tailed Rare Event Simulation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/bounded-relative-error-for-heavy-tailed-rare-event-simulation/rdr_9901dab0e62a4ca0a497818e6873fe0a},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_bounded_relative_error_for_heavy_tailed__9901dab0_v1,
  title = {Bounded Relative Error for Heavy Tailed Rare Event Simulation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/bounded-relative-error-for-heavy-tailed-rare-event-simulation/rdr_9901dab0e62a4ca0a497818e6873fe0a/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}