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$

  • $\begingroup$ 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. $\endgroup$ – Matt F. Jun 6 '18 at 23:44
  • $\begingroup$ 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. $\endgroup$ – fedja Jun 7 '18 at 0:25

$\newcommand{\al}{\alpha} \newcommand{\de}{\delta} \newcommand{\De}{\Delta} \newcommand{\ep}{\varepsilon} \newcommand{\ga}{\gamma} \newcommand{\Ga}{\Gamma} \newcommand{\la}{\lambda} \newcommand{\Si}{\Sigma} \newcommand{\thh}{\theta} \newcommand{\om}{\omega} \newcommand{\R}{\mathbb{R}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\F}{\mathcal{F}} \newcommand{\E}{\operatorname{\mathsf E}} \newcommand{\Var}{\operatorname{\mathsf Var}} \renewcommand{\P}{\operatorname{\mathsf P}} \newcommand{\ii}[1]{\operatorname{\mathsf I}\{#1\}} \newcommand{\tf}{\widetilde{f}}$

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 \begin{equation} \E\De_n\asymp1 \end{equation} and \begin{equation} \P(\De_n > n^{\al}) \le \frac{\E\De_n}{n^{\al}}\to0 \end{equation} 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.

  • $\begingroup$ 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] $\endgroup$ – Gericault Jun 6 '18 at 18:08
  • 2
    $\begingroup$ @Gericault : You said "uniform density". $\endgroup$ – Iosif Pinelis Jun 6 '18 at 18:34
  • 1
    $\begingroup$ @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. $\endgroup$ – Iosif Pinelis Jun 6 '18 at 19:11
  • $\begingroup$ Yes I edited sorry ! $\endgroup$ – Gericault Jun 6 '18 at 21:13
  • $\begingroup$ @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$. $\endgroup$ – 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) $$


$$ \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. $$

  • $\begingroup$ 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 $\endgroup$ – Gericault Jun 11 '18 at 10:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.