Eficient Monte Carlo Simulation of the Left Tail of Positive Gaussian Quadratic Forms

Chaouki Ben Issaid, Mohamed‐Slim Alouini, Raúl TemponearXiv 2019 · DOI · arXiv

Abstract

Estimating the left tail of quadratic forms in Gaussian random vectors is of major practical importance in many applications. In this paper, we propose an efficient and robust importance sampling estimator that is endowed with the bounded relative error property. This property significantly reduces the number of simulation runs required by the proposed estimator compared to naive Monte Carlo. Thus, our importance sampling estimator is especially useful when the probability of interest is very small. Selected simulation results are presented to illustrate the efficiency of our estimator compared to naive Monte Carlo in both central and non-central cases, as well as both real and complex settings.

Introduction

In fields ranging from wireless communications to string theory, researchers frequently encounter the need to calculate the probability that a quadratic form of a Gaussian random vector falls below a very small threshold. A primary example is found in wireless receiver design using Maximum Ratio Combining (MRC), where this calculation represents the "outage probability"—the likelihood that the signal-to-noise ratio (SNR) drops so low that the connection fails.

Mathematically, this involves estimating the "left tail" of a distribution. While analytical approximations exist, they often become numerically unstable or computationally prohibitive when the probability is extremely small (e.g., $10^{-9}$ or lower). Standard "naive" Monte Carlo (MC) simulations are equally impractical; to accurately estimate an event with a probability of $10^{-9}$, one would typically require tens of billions of simulation runs to achieve statistical significance. This paper addresses the need for a simulation framework that is fast, stable, and theoretically robust for these rare-event scenarios.

Methodology

Importance Sampling and Variance Reduction

The proposed solution utilizes Importance Sampling (IS), a variance reduction technique that replaces the original probability density function (PDF) with a "biased" distribution. Under this biased measure, the rare event of interest is no longer rare, allowing for frequent observations of the tail event. To maintain an unbiased estimate, the results are weighted by a likelihood ratio.

The Proposed Estimator

The core innovation of this work lies in the construction of the biased distribution through two primary mechanisms:

  1. Mean Shifting and Variance Scaling: For a given Gaussian vector, the mean is shifted and the variance of each component is scaled.
  2. Optimal Parameter Selection: A scaling parameter is specifically chosen such that the expected value of the quadratic form under the new biased distribution is exactly equal to the target threshold $\gamma_0$. This transformation effectively turns a "rare" event into a "typical" one under the new measure.

Bounded Relative Error (BRE)

The authors rigorously prove that this specific IS scheme satisfies the Bounded Relative Error (BRE) property. In simulation theory, BRE is considered the "gold standard" for efficiency. It guarantees that the number of samples required to achieve a specific level of accuracy does not increase as the probability being estimated approaches zero. This ensures the estimator remains robust even in the limit of vanishingly small probabilities.

Experimental Setup

To validate the estimator, the authors evaluated the method across three distinct simulated scenarios:

  • Toy Example: A 3x3 non-zero mean Gaussian vector used to verify the fundamental mechanics of the algorithm.
  • Nakagami-m Fading Channels: A real-valued scenario modeling wireless diversity receivers.
  • Rician Fading Channels: A complex-valued scenario, representing the standard for modeling line-of-sight wireless communications.

Key Results and Discussion

Efficiency and Speedup

The proposed IS method demonstrates massive efficiency gains over naive MC. In the toy example, for a probability of approximately $1.7 \times 10^{-5}$, the IS method provided a variance reduction (efficiency gain) of over 700,000 times compared to naive MC.

Stability at the Limit

In wireless simulations (Example 2), the IS scheme provided stable, rock-solid estimates using only $10^4$ samples, even as the threshold dropped to levels where naive MC (using $10^7$ samples) became entirely erroneous. The "error bars" for the IS estimator remained consistent even as probabilities dropped as low as $10^{-14}$.

Constant Complexity

For a fixed 5% relative error, the number of simulation runs required for the IS scheme remained almost constant as the threshold decreased. In contrast, the computational requirement for naive MC grows exponentially as the event becomes rarer, highlighting the practical utility of the BRE property.

Conclusion and Limitations

The proposed Importance Sampling estimator provides a robust and versatile framework for estimating the left tail of Gaussian quadratic forms across central, non-central, real, and complex settings. However, the authors note a significant hurdle: The Curse of Dimensionality. The theoretical upper bound for the relative error of the estimator increases exponentially with $N$ (the number of dimensions in the Gaussian vector). While the method is exceptionally efficient for dimensions typically found in wireless communication problems (e.g., $L=2, 3, 4$ branches), the performance gain may deteriorate as the problem size becomes very large. Future research may focus on refining the biased distribution for high-dimensional vectors or extending this framework to non-Gaussian quadratic forms.

Summary updated

Abstract

Estimating the left tail of quadratic forms in Gaussian random vectors is of major practical importance in many applications. In this paper, we propose an efficient and robust importance sampling estimator that is endowed with the bounded relative error property. This property significantly reduces the number of simulation runs required by the proposed estimator compared to naive Monte Carlo. Thus, our importance sampling estimator is especially useful when the probability of interest is very small. Selected simulation results are presented to illustrate the efficiency of our estimator compared to naive Monte Carlo in both central and non-central cases, as well as both real and complex settings.
BibTeX
@misc{issaid2019eficient,
  author = {Chaouki Ben Issaid and Mohamed‐Slim Alouini and Raúl Tempone},
  title = {{Eficient Monte Carlo Simulation of the Left Tail of Positive Gaussian Quadratic Forms}},
  year = {2019},
  eprint = {1901.09174},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1901.09174},
}
Figure