Tight Bounds on Expected Order Statistics

In this article, we study the problem of finding tight bounds on the expected value of the k th-order statistic E [ X k : n ] under first and second moment information on n real-valued random variables. Given means E [ X i ] = μ i and variances Var[ X i ] = σ i 2 , we show that the tight upper bound on the expected value of the highest-order statistic E [ X n : n ] can be computed with a bisection search algorithm. An extremal discrete distribution is identified that attains the bound, and two closed-form bounds are proposed. Under additional covariance information Cov[ X i , X j ] = Q ij , we show that the tight upper bound on the expected value of the highest-order statistic can be computed with semidefinite optimization. We generalize these results to find bounds on the expected value of the k th-order statistic under mean and variance information. For k < n , this bound is shown to be tight under identical means and variances. All of our results are distribution-free with no explicit assumption of independence made. Particularly, using optimization methods, we develop tractable approaches to compute bounds on the expected value of order statistics.