# Largest deviations for uniform order statistics

Let $$n >0$$.

Let $$X_1,\ldots,X_n$$ be i.i.d. uniform random variable on $$[0,1].$$ Denote by $$X^{(1)}\leq X^{(2)} \leq \cdots \leq X^{(n)}$$ their order statistics, and write $$\Delta^{(i)} = \vert X^{(i)} - EX^{(i)} \vert$$

It is classical than $$X^{(i)}$$ follows a beta, with parameters $$\beta(i, n-i+1)$$

I would like to show that :

$$\sup_{1 \leq i \leq n} \Delta^{(i)} \overset{\mathcal{P}}{\underset{n\to+\infty}{\longrightarrow}} 0$$

where the subscript "$$\mathcal{P}$$ " denote the convergence in probability.

If ones tries to be brutal, it goes like this :

$$P(\sup_{1 \leq i \leq n} \Delta^{(i)} \geq x) \leq \sum_{i=1\ldots n} P( \Delta^{(i)} \geq x)$$ $$\leq \frac{1}{x^2}\sum_{i=1 \ldots n} \operatorname{Var}(X^{(i)})$$

$$\leq \frac{1}{x^2}\sum_{i=1\ldots n} \frac{i(n-i+1)}{(n+1)^2(n+2)} = O(1)$$

But i need $$o(1)$$ hence, one has to do something a little more refined, but I can't make it work.. Any idea ?

PS : A dream would be to prove such property for a whole classe of rvs, say rvs admitting a "nice" density on $$[0,1]$$

• This seems closely related to the DKW inequality, which implies that the empirical CDF of $X_1,\dots,X_n$ approaches the uniform CDF at every point. – usul Jun 16 '18 at 16:30


It is easy to see (say, using the formulas for the variance and excess kurtosis for the beta distribution) that, if $Y$ has the beta distribution with parameters $\al,\be>0$, then $\mu_4(Y):=\E(Y-\E Y)^4\ll1/(\al+\be)^2$. So, if $X_1,\dots,X_n$ are iid uniformly distributed on $[0,1]$, then for any real $x>0$ $$\P(\sup_{1 \le i \le n} \De^{(i)} \ge x) \le \sum_1^n \P( \De^{(i)} \ge x) \le \frac{1}{x^4}\sum_1^n \mu_4(X^{(i)}) \ll \frac{1}{x^4}\sum_1^n \frac1{n^2} \to0, \tag{1}$$ as desired.

More generally, suppose now that $Y_1,\dots,Y_n$ are iid r.v.'s with values in a finite interval and a pdf bounded away from $0$. Then the function $\psi:=G^{-1}$ inverse to the cdf $G$ of $Y_1$ is Lipschitz. Also, we can write $Y_i=\psi(X_i)$ (see e.g. page 4) and $Y^{(i)}=\psi(X^{(i)})$, with $X_1,\dots,X_n$ as before. So, for $V:=X^{(i)}$, an independent copy $\tV$ of $V$, $W:=\psi(V)=Y^{(i)}$, and $\tW:=\psi(\tV)$, and some real constant $L>0$, we have the Lipschitz condition $|W-\tW|\le L|V-\tV|$ and hence \begin{multline*} \mu_4(Y^{(i)})=\E(W-\E\tW)^4=\E\E(W-\tW|W)^4 \le\E\E\big((W-\tW)^4|W\big) \\ =\E(W-\tW)^4\le L^4\E(V-\tV)^4\le16 L^4\mu_4(V)=16 L^4\mu_4(X^{(i)}); \end{multline*} here we used (a conditional version of) Jensen's inequality and the inequality $(a-b)^4\le8(a^4+b^4)$ with $a=V-\E V$ and $b=\tV-\E\tV=\tV-\E V$. So, for any real $x>0$, similarly to (1) we have
\begin{equation*} \P(\sup_{1 \le i \le n} |Y^{(i)} - \E Y^{(i)}| \ge x) \le \frac{1}{x^4}\sum_1^n \mu_4(Y^{(i)}) \le16 L^4\frac{1}{x^4}\sum_1^n \mu_4(X^{(i)}) \ll \frac{1}{x^4}\sum_1^n \frac1{n^2} \to0, \end{equation*} as desired.

The condition that the r.v.'s $Y_i$ take values in a finite interval and have a pdf bounded away from $0$ cannot be dropped. E.g., suppose that $\P(Y_i=0)= \P(Y_i=1)= 1/2$. Then for $m:=\lfloor n/2\rfloor$ we have $p_m:=\P(Y^{(m)}=0)=\P(B_{n,1/2}\ge m)\to1/2$ as $n\to\infty$, where $B_{n,1/2}$ is a binomial r.v. with parameters $n,1/2$. So, $\E Y^{(m)}=\P(Y^{(m)}=1)=1-p_m\to1/2$ and hence $|Y^{(m)}-\E Y^{(m)}|\to1/2\ne0$; the convergence here is in probability (and even almost surely).

Note also that this two-point distribution of $Y_i$ can be appropriately approximated, however closely, by an absolutely continuous distribution with pdf taking zero (or arbitrarily close to zero) values on a subinterval of the interval $[0,1]$ of length arbitrarily close to $1$.

• Great, thanks ! Indeed, I was thinking about a good assumption on the density of $X_1$, I think the bounded from below can be relaxed, still ensuring the inverse of the cumulative is Lipschitz (allowing the density to go to 0 at the edges of [a,b] for instance). PS : it does not matter but I think after using $(a-b)^4 \leq 8(a^4 + b^4)$, you get $\mu_4(Y^{(i)}) \leq 16L^4\mu_4(X^{(i)})$, right ? – Gericault Jun 17 '18 at 16:10
• @Gericault : Indeed, 8 needed to be changed to 16 (done now). Also, added a paragraph at the end. – Iosif Pinelis Jun 17 '18 at 16:32
• @Gericault The necessary and sufficient condition seems to be that there should be no gaps (intervals of $0$ probability) in the distribution. – fedja Jun 18 '18 at 16:37
• @fedja : I suspected that something like this should be true. It seems that the argument in the above "binary" counterexample can be rather easily modified to show that, with any gap in the distribution, the probability in question will not go to $0$. In the other direction, the matter seems significantly more difficult. – Iosif Pinelis Jun 18 '18 at 20:55

Iosif Pinelis provided a very nice answer, however, I would like to provide a more comprehensive answer to this question. I think the title is a bit misleading because we do not actually need the order statistics to satisfy any kind of large deviation principle, I would rather call it a limiting result if you let $n\rightarrow \infty$ (Then Hoeffding limiting theorem [1] will kick in and you can derive associated distributional properties for the limiting Gaussian distribution, say study the extremes [2]); and a concentration bound if you want $n$ fixed.

As for this question and OP's "PS" comment, I wanted to point our that a more general result can be obtained from Efron-Stein inequality, by Boucheron [3], and it is sharp:

[3] Theorem 2.9 (Exponential Efron-Stein inequality).

Let $X_{1},\cdots,X_{n}$ be independently distributed according to $F$, let $X_{(1)}\geq\cdots\geq X_{(n)}$ be the order statistics and let $\Delta_k=X_{(k)}-X_{(k+1)}$ be the k-th spacing. Let $V_{k}=k\Delta_{k}^{2}$ denote the Efron-Stein estimate of the variance of $X_{(k)}$ (for k = 1, . . . , n/2). If $F$ has a non-decreasing hazard rate $h$, then for 1\leq k\leq n/2$, $$Var[X_{(k)}]\leq\boldsymbol{E}V_{k}\leq\frac{2}{k}\boldsymbol{E}\left[\left(\frac{1}{h(X_{(k+1)})}\right)^{2}\right]$$ for$\lambda\geq0,1\leq k\leq n/2$$$\log\boldsymbol{E}\exp\left[\lambda\left(X_{(k)}-\boldsymbol{E}X_{(k)}\right)\right]\leq\lambda\frac{k}{2}\boldsymbol{E}\Delta_{k}\left(\exp\left(\lambda\Delta_{k}-1\right)\right)=\frac{\lambda k}{2}\boldsymbol{E}\left[\sqrt{\frac{V_{k}}{k}}\left(e^{\lambda\sqrt{\frac{V_{k}}{k}}}-1\right)\right].$$ With this result we can actually apply the OP's argument $$P(\sup_{1 \leq i \leq n} \Delta^{(i)} \geq x) \leq \sum_{i=1..n} P( \Delta^{(i)} \geq x)\leq \frac{1}{x^2}\sum_{i=1..n} Var(X_{(i)})$$ on a wider class of densities with a mild assumption on Stein estimates$V_k$, which is known to behave well and well studied. The resulting inequality will still be sharp because every inequality is sharp. And following this line, Iosif's "uniformly bounded below from zero" assumption is no longer needed and hence a more general result can be obtained. One more comment on Iosif's answer. The reason why "uniformly bounded" condition (say even the density is not compactly supported, Iosif's arguments still hold with a slight modification, but as long as "$f$is uniformly bounded from zero" does not hold, his arguments collapse as noted.) cannot be dropped is exactly the reason why I commented in the beginning this is not a "LDP" type result, which does not assume such a condition. Reference [1]Randles, Ronald H., and Douglas A. Wolfe. "Introduction to the theory of nonparametric statistics." Introduction to the theory of nonparametric statistics, by Randles, Ronald H.; Wolfe, Douglas A. New York: Wiley, c1979. Wiley series in probability and mathematical statistics (1979). [2]DasGupta, Anirban, S. N. Lahiri, and Jordan Stoyanov. "Sharp fixed n bounds and asymptotic expansions for the mean and the median of a Gaussian sample maximum, and applications to the Donoho–Jin model." Statistical Methodology 20 (2014): 40-62. [3]Boucheron, Stéphane, and Maud Thomas. "Concentration inequalities for order statistics." Electronic Communications in Probability 17 (2012). • I think the argument with the variances will not work here. Indeed, as noted by the OP, even for uniformly distributed$X_i$'s, where the variances of the order statistics have an explicit and very simple expression, using the variances gives only the trivial bound$O(1)$on the probability in question. That is why I used 4th moments in my answer. Also, the non-decreasing hazard rate condition does not seem relevant here. As for the exponential moments, the bound on them that you cited appears to hold only for the right tails, with$\lambda\ge0\$. – Iosif Pinelis Jun 18 '18 at 20:41
• @IosifPinelis You are right! Let me try to fix it later thanks! – Henry.L Jun 18 '18 at 21:27