Order statistics of bounded variable : L2 concentration?

Let n >0

Let $X_1,...,X_n$ be i.i.d. random variable with a density (say $f(x)$) on [a,b]. Denote by $X_{(1)}\leq X_{(2)} \leq \ldots \leq X_{(n)}$ their order statistics.

I'm interested in controlling the following quantity : $$\Delta_n = \sum_{i=1}^n \vert X_{(i)} - EX_{(i)} \vert^2$$ One can write :

$$P(\Delta_n > n^{\alpha}) \leq \frac{E\Delta_n}{n^{\alpha}} \leq \frac{1}{n^{\alpha}} \sum_i^n Var(X_{(i)})$$

Unfortunately, after a bit of research I did not find non-asymptotic satisfactory control of such quantities.

If more hypothesis is required on the law of X, it might not be a problem for me. The overall objective is to show that $\frac{\Delta_n}{n^{\alpha}} \rightarrow 0$ in probability (at least), and for some (as low as possible) $\alpha < 0$

• Will you revert the question to the way it stood before the answers? You can always ask your new question in a new post, but it is rude to edit in a way that invalidates previously given answers. – Matt F. Jun 6 '18 at 23:44
• You can get the upper bound $E\Delta_n\le C(b-a)^2\sqrt n$ following the discussion at mathoverflow.net/questions/301135/… (it is good for any distribution with or without density). The existence of density won't help at all if you have a symmetric distribution with a gap near the middle of the interval. So $\alpha=\frac 12+$ is the best you can hope for in the generality you suggested. – fedja Jun 7 '18 at 0:25


By shifting and rescaling, without loss of generality $[a,b]=[0,1]$. Then $X_{(i)}$ has the beta distribution with parameters $i,n-i+1$, so that $$\Var X_{(i)}=\frac{i(n-i+1)}{(n+1)^2(n+2)},$$ and hence $$\E\De_n\asymp1$$ and $$\P(\De_n > n^{\al}) \le \frac{\E\De_n}{n^{\al}}\to0$$ if $\al>0$.

This also shows to be highly unlikely that $\P(\De_n > n^{\al}) \to0$ for $\al\le0$. To show this, one can use e.g. the Paley–Zygmund inequality, which will involve a straightforward but lengthy (and I think rather pointless) calculation of (pure and mixed) moments of the $X_{(i)}$'s of up to the $4$th order.

• Ok for shift/rescale but $X_{(i)}$ only has Beta distribution if X is uniform on [0,1], my question is about general continous law, i.e $X \approx f\lambda$ where $\lambda$ is the Lebesgues measure on [0,1] – Gericault Jun 6 '18 at 18:08
• @Gericault : You said "uniform density". – Iosif Pinelis Jun 6 '18 at 18:34
• @Gericault : Also, you did not even mention "general continous law" in your question. Further, writing now $X\approx f\lambda$, you apparently mean an absolutely continuous, rather than just continuous, distribution. However, even the absolute continuity is not any real restriction, because any distribution on $[a,b]$ can be appropriately approximated by absolutely continuous ones. – Iosif Pinelis Jun 6 '18 at 19:11
• Yes I edited sorry ! – Gericault Jun 6 '18 at 21:13
• @IosifPinelis 's answer is perfect, just one more comment, if you want that $P(\Delta n>n\alpha)\rightarrow0$ for $\alpha\leq 0$ then it may be helpful to assume dependent samples instead of independent samples and put bounding conditions on the correlation of $f$. – Henry.L Jun 18 '18 at 16:24

Suppose that $X_1,\dotsc , X_n$ are independent random variables uniformly distributed in $[0,1]$. Denote by $Y_i=X_{(i)}$ its order statistics.

The random vector $(Y_1,\dotsc, Y_n)$ has distribution

$$p(y_1,\dotsc, y_n)=\begin{cases} n!, & 0\leq y_1\leq \cdots \leq y_n\leq 1, \\ 0, & {\rm otherwise}. \end{cases}$$

The random variable $Y_k$ has distribution

$$p_k(y_k)=n!\int_{\substack{0\leq y_1\cdots \leq y_k\\ y_k\leq y_{k+1}\leq \cdots \leq y_n\leq 1}}dy_1\cdots dy_{k-1}dy_{k+1}\cdots dy_{n}$$ $$= n!\left(\int_{0\leq y_1\leq \cdots \leq y_{k-1} \leq y_k} dy_1\cdots dy_{k-1}\right)\left(\int_{y_k\leq y_{k+1}\leq \cdots \leq y_{n} \leq 1} dy_{k+1}\cdots dy_{n}\right)$$

$$= \frac{n!}{(k-1)!(n-k)!} y_k^{k-1}(1-y_k)^{n-k}$$

Thus $p_k$ is a $B(k,n+1-k)$-distribution. $\newcommand{\bE}{\mathbb{E}}$ We have

$$\bE[Y_k]=\frac{n!}{(k-1)!(n-k)!}\int_0^1 y^k(1-y)^{n-k} dy=\frac{n!}{(k-1)!(n-k)!}\frac{\Gamma(k+1)\Gamma(n-k+1)}{\Gamma(n+2)}$$

$$= \frac{n!}{(k-1)!(n-k)!}\frac{k!(n-k!)}{(n+1)!}=\frac{k}{n+1}.$$

$$\bE[Y_k^2]=\frac{n!}{(k-1)!(n-k)!}\int_0^1 y^{k+1}(1-y)^{n-k} dy= \frac{n!}{(k-1)!(n-k)!}\frac{\Gamma(k+2)\Gamma(n-k+1)}{\Gamma(n+3)}$$

$$=\frac{n!}{(k-1)!(n-k)!}\frac{(k+1)!(n-k)!}{(n+2)!}=\frac{k(k+1)}{(n+1)(n+2)}.$$

$\DeclareMathOperator{\Var}{Var}$. Hence

$$\Var[Y_k]= \frac{k(k+1)}{(n+1)(n+2)}-\left(\frac{k}{n+1}\right)^2=\frac{k}{n+1}\left(\frac{k+1}{n+2}-\frac{k}{n+1}\right)=\frac{k(n+1-k)}{(n+1)^2(n+2)}.$$

We deduce

$$\bE[\Delta_n]=\sum_{k=1}^n \Var[Y_k]=\frac{1}{(n+1)^2(n+2)}\sum_{k=1}^n k(n+1-k).$$

We have

$$\sum_{k=1}^nk(n+1-k)= (n+1)\sum_{k=1}^n kn-\sum_{k=1}^n k(k-1)$$

$$= \frac{n^2(n+1)}{2}-\sum_{k=1}^nk(k-1).$$

Now we write

$$k(k-1)=\frac{1}{3}\Big(\; k^3-(k-1)^3-1\;\Big)$$

so

$$\sum_{k=1}^n k(k-1)=\frac{1}{3}\Big(\; n^3 -n\;\Big)=\frac{n(n+1)(n-1)}{3}.$$

We deduce

$$\bE[\Delta_n]= \frac{1}{(n+1)^2(n+2)}\left(\;\frac{n^2(n+1)}{2}-\frac{n(n+1)(n-1)}{3}\;\right)=\frac{n(n+1)(n+2)}{6(n+1)^2(n+2)}=\frac{n}{6(n+1)}.$$ Suppose now that $X_1,\dotsc, X_n$ are i.i.d. with common distribution $p(x)dx$ To compute $\bE[\Delta_n^]$ the following alternate description of $\Delta_n$ could help.

$$\Delta_n= \sum_{k=1}^n Y_k^2-2\sum_{k=1}^n \bE[Y_k]Y_k+\sum_{k=1}^N\bE[Y_k]^2$$ $$=\sum_{k=1}^n X_k^2-\sum_{k=1}^n \bE[Y_k]Y_k+\sum_{k=1}^N\bE[Y_k]^2.$$

Hence $$\bE[\Delta_n]=\bE\left(\sum_{k=1}^n X_k^2\right)-\sum_{k=1}^n \bE[Y_k]^2 =n\bE[X_1^2]-\sum_{k=1}^n \bE[Y_k]^2.$$

• Thanks, indeed i'm interested in the case where $X_1,...,X_n$ are iid with distribution $p(x)dx$. I agree with your decomposition, but to my knowledge there is no expression for $E[Y_k]$ right ? It's strange we can't find a way to show $E[\Delta_n] = O(1)$ without exact computations – Gericault Jun 11 '18 at 10:36