On the Sum of Order Statistics and Applications to Wireless Communication Systems Performances

Nadhir Ben Rached, Zdravko I. Botev, Abla Kammoun, Mohamed‐Slim Alouini, Raúl Tempone

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 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 instead propose 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. A possible 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 for the Log-normal case. Finally, the efficiency of these estimators is compared via various numerical simulations.

Introduction

In modern wireless communication systems, diversity techniques are essential for mitigating the effects of fading and improving link reliability. One such technique is Generalized Selection Combining (GSC), where a receiver selects and combines the $L$ strongest signals from $N$ available diversity branches. Analyzing the performance of GSC systems—specifically calculating the Outage Probability (OP)—requires evaluating the Cumulative Distribution Function (CDF) of the sum of these $L$ largest order statistics.

However, this evaluation presents two significant hurdles. First, for many realistic fading models such as Log-normal, Weibull, and Generalized Gamma, closed-form expressions for the sum of order statistics do not exist. Second, high-performance systems often operate in "rare event" regimes where the OP is extremely small (e.g., $10^{-10}$). In these scenarios, standard (naive) Monte Carlo simulations become computationally prohibitive, requiring billions of samples to produce a single reliable estimate.

Proposed Methodologies

To overcome these challenges, this research introduces two high-efficiency variance reduction techniques designed to provide accurate estimates with minimal computational overhead.

1. Universal Importance Sampling (IS) Estimator

The Importance Sampling approach works by "biasing" the simulation to focus on the rare regions where outages actually occur. The authors propose a "universal" IS estimator that achieves Bounded Relative Error (BRE). This property is critical because it ensures that the number of samples required to maintain a specific accuracy level does not increase as the probability being estimated approaches zero. This estimator is further refined for specific distributions, such as Pareto and Weibull, by leveraging their unique convexity properties.

2. Conditional Monte Carlo (CMC) Estimator

Instead of simulating all variables, the CMC method uses analytical conditioning to solve part of the problem, thereby reducing the variance of the simulation.

  • Generalized Gamma: The authors utilize a specific representation involving Dirichlet and Gamma random variables to achieve BRE.
  • Log-normal: A spherical decomposition ($Y = R\Theta$) is employed, where the simulation conditions on the direction vector $\Theta$. This approach achieves logarithmic efficiency, a significant improvement over standard methods for shadowing environments.

3. Integration with Randomized Quasi-Monte Carlo (RQMC)

A notable advantage of the CMC estimator is its mathematical smoothness. The authors demonstrate that this smoothness allows the CMC estimator to be combined with Randomized Quasi-Monte Carlo (RQMC) methods. This combination improves the error convergence rate from the standard $O(M^{-1/2})$ to approximately $O(M^{-1})$, effectively doubling the efficiency of the simulation.

Numerical Results and Insights

The efficiency of these estimators was validated through rigorous simulations across various fading models:

  • Efficiency Gains: In a Weibull fading scenario with a threshold $\gamma_{th} = 0.005$, the IS estimator achieved a relative error of 0.11% using only $5 \times 10^5$ samples. A naive Monte Carlo approach would have required orders of magnitude more samples to achieve any level of confidence.
  • Stability in Rare Events: The estimators remained stable even as target probabilities dropped to $10^{-12}$, confirming the theoretical BRE property.
  • Method Selection: The research highlights a strategic trade-off: the CMC estimator is generally more efficient when $L$ (combined signals) is close to $N$ (total branches), whereas the IS estimator excels when $L$ is small.

Conclusion and Future Work

This paper provides a robust framework for calculating outage probabilities in GSC receivers where traditional analytical and numerical methods fail. By achieving Bounded Relative Error and Logarithmic Efficiency, the proposed IS and CMC estimators allow for the rapid design and analysis of high-reliability wireless systems.

Future research directions include extending these methods to correlated fading channels, as the current study primarily assumes independent and identically distributed (i.i.d.) branches. Additionally, while the CMC estimator is logarithmically efficient for Log-normal distributions, achieving the stricter BRE property for this specific case remains an open challenge in the field.

Summary updated

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 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 instead propose 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. A possible 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 for the Log-normal case. Finally, the efficiency of these estimators is compared via various numerical simulations.
BibTeX
@inproceedings{rached2019sum,
  author = {Nadhir Ben Rached and Zdravko I. Botev and Abla Kammoun and Mohamed‐Slim Alouini and Raúl Tempone},
  title = {{On the Sum of Order Statistics and Applications to Wireless Communication Systems Performances}},
  booktitle = {King},
  year = {2019},
  doi = {10.1109/twc.2018.2871201},
}
Figure