Abstract
We consider the problem of estimating the probability that the maximum of a Gaussian process with negative mean and indexed by positive integers reaches a high level, say $b$. In great generality such a probability converges to 0 exponentially fast in a power of $b$. Under mild assumptions on the marginal distributions of the process and no assumption on the correlation structure, we develop an importance sampling procedure, called the target bridge sampler (TBS), which takes a polynomial (in $b$) number of function evaluations to achieve a small relative error. The procedure also yields samples of the underlying process conditioned on hitting $b$ in finite time. In addition, we apply our method to the problem of estimating the tail of the maximum of a superposition of a large number, $n$, of independent Gaussian sources. In this situation TBS achieves a prescribed relative error with a bounded number of function evaluations as $n \to \infty$. A remarkable feature of TBS is that it is not based on exponential changes of measure. Our numerical experiments validate the performance indicated by our theoretical findings.
Introduction
Gaussian processes are fundamental tools for modeling complex systems in econometrics, communication networks, and queueing theory. A critical challenge in these fields is estimating the all-time maximum of a process—specifically, the probability that a process with a negative drift will ever hit a very high threshold $b$.
As the threshold $b$ increases, this event becomes "rare," and its probability $\alpha(b)$ decays exponentially toward zero. This creates two major hurdles for researchers: naive Monte Carlo simulation fails because it requires billions of simulations to observe a single event, and standard asymptotic formulas are often inaccurate, ignoring discrete-time corrections or specific correlation structures. This paper introduces the Target Bridge Sampler (TBS), a novel importance sampling algorithm designed to bridge this gap by efficiently simulating rare events without relying on complex "exponential tilting."
Methodology: The Target Bridge Sampler (TBS)
The TBS algorithm operates by reversing the typical logic of path simulation. Instead of starting at time zero and hoping to hit the threshold, it constructs a path specifically designed to cross it.
The process follows three key steps:
- Targeting: The algorithm first selects a random time $\tau$ and a value $X_\tau$ such that the threshold is guaranteed to be crossed at that specific moment. This "target" is chosen based on the marginal distribution of the process.
- Bridging: Once the target $(\tau, X_\tau)$ is fixed, the algorithm simulates the rest of the path (from time 1 to $\tau-1$) as a Gaussian Bridge. Because Gaussian processes have well-defined conditional distributions, the path between the start and the target point can be filled in exactly.
- Trimming and Weighting: The algorithm identifies the first time the threshold was hit ($T(b)$) and applies an Importance Sampling weight (a likelihood ratio) to ensure the final estimate remains unbiased.
Unlike traditional methods, TBS avoids "exponential tilting," which involves shifting the mean of the entire process—a task that is mathematically difficult for processes with complex correlations. By focusing on the "target set," TBS becomes much easier to apply to a wider range of processes.
Key Insights and Results
The paper evaluates TBS using synthetic Fractional Gaussian Noise (fGn) with negative linear drift, a standard benchmark for modeling long-range dependence in internet traffic and financial data.
Performance Gains
- Superior Accuracy: In numerical experiments, TBS achieved a relative error of about 2% using only 25 to 27 replications. In contrast, standard asymptotic approximations (LM asymptotics) were off by nearly 70%.
- Massive Speedup: TBS reached its goal in just 1.27 seconds, whereas a naive Monte Carlo approach required over 627,000 simulation runs and 960 seconds of CPU time to achieve comparable confidence.
- Efficiency: TBS is shown to be strongly efficient in "many-sources" scaling (where the number of independent sources $n \to \infty$), meaning the relative error remains bounded regardless of how rare the event becomes.
Limitations and Future Work
While TBS is highly efficient, it faces a computational bottleneck in matrix inversion ($O(N^3)$) if the time horizon $t^+(b)$ is extremely long. The authors suggest that "circulant embedding" techniques could potentially speed this up for stationary processes. Additionally, while the "target" idea is robust for Gaussian processes, extending this framework to non-Gaussian, heavy-tailed processes remains an open area for future research.
Summary updated