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<br/>finite expectation. This behavior has implications for several core problems in machine learning and economics — including robust learning under adversarial<br/>noise, best-arm identification in bandit algorithms, revenue estimation in second price auctions, and the analysis of tail-sensitive statistics used in out-of-distribution detection.<br/>The research question we tackle in this paper is: How large can the expectation of the ℓ-th maximum of the <i>n</i> samples be? For ℓ = 1, i.e., the maximum, this expectation is known to grow as o(<i>n</i>), which can be shown to be tight. We show<br/>that there is a sharp contrast when considering any fixed ℓ &gt; 1. Surprisingly, in this case, the largest possible growth rate for all fixed ℓ &gt; 1 is O(n log(n) log log(n))<br/>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 <i>n</i> i.i.d. samples.<br/>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 <i>n</i>, the ratio remains approximately constant in 99% of trials. This suggests that<br/>while worst-case growth is sharp and meaningful, typical-case behavior may be<br/>significantly more stable