Largest deviations for uniform order statistics

Question

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]$

Answer 1

$\newcommand{\al}{\alpha} \newcommand{\be}{\beta} \newcommand{\de}{\delta} \newcommand{\De}{\Delta} \newcommand{\ep}{\varepsilon} \newcommand{\ga}{\gamma} \newcommand{\Ga}{\Gamma} \newcommand{\la}{\lambda} \newcommand{\si}{\sigma} \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}} \newcommand{\tV}{\tilde{V}} \newcommand{\tW}{\tilde{W}}$

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$ \begin{equation} \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} \end{equation} 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$.

Answer 2

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).

[4]http://www.stat.purdue.edu/~dasgupta/orderstats.pdf