Tight Asymptotics of Extreme Order Statistics

A classic statistical problem is to study the asymptotic behavior of the order statistics of a large number of independent samples taken from a distribution with finite expectation. This behavior has implications for several core problems in machine learning and economics -including robust learning under adversarial noise, best-arm identification in bandit algorithms, revenue estimation in secondprice auctions, and the analysis of tail-sensitive statistics used in out-of-distribution detection. The research question we tackle in this paper is: How large can the expectation of the ℓ-th maximum of the n samples be? For ℓ = 1, i.e., the maximum, this expectation is known to grow as o(n), which can be shown to be tight. We show that there is a sharp contrast when considering any fixed ℓ > 1. Surprisingly, in this case, the largest possible growth rate for all fixed ℓ > 1 is O( and Ω( n log(n)(log log(n)) 1.01 ). Our result is actually finer than the latter and provides a sharp characterization of the largest achievable growth rate for the expectation of the ℓ-th maximum of n i.i.d. samples. Beyond the theoretical analysis, we support our findings with extensive simulations. These empirical results highlight a notable phenomenon: although the multiplicative gap between the maximum and the second maximum grows quickly with n, the ratio remains approximately constant in 99% of trials. This suggests that while worst-case growth is sharp and meaningful, typical-case behavior may be significantly more stable.