Abstract
We consider the problem of evaluating the cumulative distribution function (CDF) of the sum of order statistics, which serves to compute outage probability (OP) values at the output of generalized selection combining (GSC) receivers. Generally, closed-form expressions of the CDF of the sum of order statistics are unavailable for many practical distributions. Moreover, the naive Monte Carlo (MC) method requires a substantial computational effort when the probability of interest is sufficiently small. In the region of small OP values, we propose instead two effective variance reduction techniques that yield a reliable estimate of the CDF with small computing cost. The first estimator, which can be viewed as an importance sampling estimator, has bounded relative error under a certain assumption that is shown to hold for most of the challenging distributions. An improvement of this estimator is then proposed for the Pareto and the Weibull cases. The second is a conditional MC estimator that achieves the bounded relative error property for the Generalized Gamma case and the logarithmic efficiency in the Log-normal case. Finally, the efficiency of these estimators is compared via various numerical experiments.
Introduction
In modern wireless communication systems, diversity techniques are essential for mitigating the adverse effects of fading—the random fluctuations in signal strength caused by multipath propagation and shadowing. One of the most sophisticated diversity schemes is Generalized Selection Combining (GSC). A GSC receiver monitors $N$ available diversity channels and selects the $L$ strongest branches to combine. This approach offers a strategic balance between the high performance of Maximal Ratio Combining (MRC) and the lower hardware complexity of Selection Combining (SC).
To analyze the performance of these systems, engineers must calculate the Outage Probability (OP): the chance that the combined signal-to-noise ratio (SNR) falls below a specific threshold. Mathematically, this requires evaluating the Cumulative Distribution Function (CDF) of the sum of the $L$ largest order statistics. However, for many realistic fading models—such as Log-normal, Weibull, or Generalized Gamma—closed-form expressions for this sum are non-existent, making performance evaluation a significant computational challenge.
The Challenge of Rare-Event Simulation
When designing high-reliability wireless systems, researchers often target extremely low outage probabilities (e.g., $10^{-9}$ to $10^{-15}$). Estimating these values using standard "naive" Monte Carlo (MC) simulations is computationally prohibitive. In a naive MC approach, the number of samples required to achieve a specific relative error is inversely proportional to the probability being estimated. For an outage probability of $10^{-12}$, one might need trillions of simulation runs to produce a statistically significant result. This paper addresses this "rare-event" simulation bottleneck by developing high-efficiency variance reduction techniques.
Proposed Methodology
The authors propose two primary strategies designed to maintain accuracy while drastically reducing the number of required samples.
1. Importance Sampling (IS)
The first approach is a Universal Importance Sampling estimator. Instead of sampling from the original distribution, the simulation draws from a "truncated" distribution where the signals are constrained to be below the threshold of interest. The authors prove that this estimator possesses the bounded relative error property, meaning the computational effort required to maintain a certain level of precision remains stable even as the probability of interest approaches zero. For specific distributions like Pareto and Weibull, the authors further refine this by leveraging the mathematical property of convexity to create more efficient sampling sets.
2. Conditional Monte Carlo (CMC)
The second approach involves Conditional Monte Carlo simulation. This technique reduces variance by analytically integrating out a portion of the system's randomness. For the Log-normal distribution, the authors employ a geometric decomposition, splitting the signal vector into a "distance" and a "direction" on an $N$-dimensional hypersphere. By conditioning the simulation on the direction, they achieve logarithmic efficiency. This method is particularly effective for distributions where the "left tail" (the region of low power) is the primary concern.
3. Randomized Quasi-Monte Carlo (RQMC)
To further accelerate convergence, the authors apply Randomized Quasi-Monte Carlo methods to the CMC estimator. By replacing purely random points with "low-discrepancy" sequences, they improve the convergence rate from the standard $O(M^{-1/2})$ to approximately $O(M^{-1})$. In practical terms, this means that increasing the sample size yields a much greater improvement in precision than it would in a standard simulation.
Key Insights and Results
The research highlights a significant "L vs N" tradeoff in estimator selection. The choice of the most efficient algorithm depends heavily on the receiver configuration:
- Small $L$: When the receiver selects only a few branches ($L$ is small relative to $N$), Importance Sampling is generally the superior method.
- Large $L$: When the receiver combines most or all available branches ($L \approx N$), the Conditional Monte Carlo approach becomes significantly more efficient.
Numerical experiments demonstrate massive speedups. For instance, in a Pareto distribution scenario, the improved IS estimator achieved a relative error of only $0.0179\%$ for a probability of $1.29 \times 10^{-12}$ using just $5 \times 10^5$ samples. A naive simulation would have required trillions of samples to reach the same level of confidence. Furthermore, the Universal IS estimator was shown to be robust across a wide range of challenging distributions, including the $\kappa-\mu$ and Rice distributions.
Conclusion
This work provides a robust framework for the efficient simulation of GSC receivers across a wide range of fading environments. By establishing the bounded relative error property for several challenging distributions, the authors enable the accurate analysis of ultra-reliable wireless systems that were previously too computationally expensive to simulate. While the current study assumes independent and identically distributed (i.i.d.) channels, the underlying principles of Universal IS and CMC offer a clear path forward for analyzing more complex, correlated fading environments in future research.
Summary updated