Skip to main content
2 of 2
edited title
kodlu
  • 10.4k
  • 2
  • 36
  • 55

Concentration for sum of order statistics

Assume we draw $n$ numbers uniform i.i.d. from $[0,1]$, and let the least $k$ of them be $x_1,\dots,x_k$. It is well-known that their expectations are $\frac{1}{n+1},\dots,\frac{k}{n+1}$, so the expectation of their sum is $\frac{k(k+1)}{2(n+1)}$. But is there a concentration bound saying that, with high probability as $n\rightarrow\infty$, this sum doesn't exceed $\alpha\cdot\frac{k(k+1)}{2(n+1)}$ for some given parameter $\alpha$?

These $k$ variables are not independent, so we cannot apply Chernoff bound. I found a paper with a related title, but it is not easy to tell if something in there answers this question.