Tight bounds on expected order statistics

In this article, we study the problem of finding tight bounds on the expected value of the kth-order statistic E[X-k:n] under first and second moment information on it real-valued random variables. Given means E[X-i] = mu(i) and variances Var[X-i] = sigma(2)(i), 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(jj), 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 kth-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.