This is a problem that I encountered in my research and have no clues to fully
resolve it. Basically, I need large (or moderate) deviation bounds on the
difference between an order statistic of independent and identically
distributed (i.i.d.) random variables on the compact interval $\left[
0,1\right] $ and the expectation of this order statistic.
Let $X_{1}%
,...,X_{n}$, $n\in\mathbb{N}$ be i.i.d. and uniformly distributed on $\left[
0,1\right] $. Let their order statistics be $X_{\left( 1\right) }\leq
X_{\left( 2\right) }\leq...\leq X_{\left( n\right) }$, where we can ignore
the zero probability event that any two order statistics are equal. Let $E$
and $V$ denote respectively the expectation operator and variance operator.
Then each $X_{\left( r\right) }$ follows a Beta distribution,
$$
E\left[ X_{\left( r\right) }\right] =\frac{r}{n+1},r=1,...,n
$$
and
$$
V\left[ X_{\left( r\right) }\right] =\frac{r\left( n-r+1\right)
}{\left( n+1\right) ^{2}\left( n+2\right) },r=1,...,n
$$
This implies two things:
(a) when $r=o\left( n\right) $ where the small $o$ notation means that
$\lim_{n\rightarrow\infty}\frac{r}{n}=0$, for any $\varepsilon>0,$
\begin{equation}
P\left( \left\vert X_{\left( r\right) }-\frac{r}{n+1}\right\vert
>\varepsilon\right) \leq\frac{o\left( 1\right) }{n
\varepsilon^{2}},\label{eq1}%
\end{equation}
where $o\left( 1\right) $ denotes a nonnegative sequence that converges to
$0$ as $n\rightarrow\infty$; in this case, $\varepsilon=n^{-\alpha}$ with $0 \le \alpha < \frac{1}{2}$ can be
set, such that
\begin{equation}
P\left( \left\vert X_{\left( r\right) }-\frac{r}{n+1}\right\vert >\frac
{1}{n^{\alpha}}\right) \le \frac{o(1)}{n^{1-2\alpha}}\rightarrow0,\label{eq3}%
\end{equation}
where the $o\left( 1\right) $ can be set to be no smaller in order than rate
$\frac{r}{n}$.
(b) when $r=O\left( n\right) $ where the big $O$ notation here means that
$\liminf_{n\rightarrow\infty}\frac{r}{n}>0$, for any $\varepsilon>0$,
\begin{equation}
P\left( \left\vert X_{\left( r\right) }-\frac{r}{n+1}\right\vert
>\varepsilon\right) \leq C\frac{1}{\left( n+2\right) \varepsilon^{2}%
}\label{eq2}%
\end{equation}
from some constant $C\leq2$; in this case $\varepsilon=o\left( \sqrt
{n}\right) $ can be set such that
\begin{equation}
P\left( \left\vert X_{\left( r\right) }-\frac{r}{n+1}\right\vert >\frac
{1}{n^{\alpha}}\right) \leq\frac{2}{n^{1-2\alpha}}\rightarrow0\label{eq4}%
\end{equation}
for any $0\leq\alpha<\frac{1}{2}$.
**Observation**:
A simple conclusion from the above discussion is that, regardless of the value
of $r$, we have that $X_{\left( r\right) }$ for each $r$ converges to
$E\left[ X_{\left( r\right) }\right] $ in probability as $n\rightarrow
\infty$. **Further, we know the rate of convergence is $n^{-\alpha}$ for any $0 \le \alpha < 1/2$.** My question is "**are the deviation bounds given above
the best**?" **Very likely NOT**.
**Question**:
Let $a_{n,r}$ be a positive sequence
that depends on $n$ and $r$ such that
$$
\lim_{n\rightarrow\infty}a_{n,r}=0
$$
for each $r=1,...,n$, what is the best result available on
$$
\beta_{n,r} \ge P\left( \left\vert X_{\left( r\right) }-\frac{r}{n+1}%
\right\vert >a_{n,r}\right)
$$
where $\beta_{n,r} \to 0$ as $n \to \infty$?
By this I mean, what is the bound $\beta_{n,r}$ corresponding to the sequence $a_{n,r}$ that converges to $0$ at relatively and possibly the fastest speed?
Any pointers or hints would be greatly appreciated! Thanks!
**Update 1:** (see update 3 below)
Thanks for Henry's comment. I found this: https://projecteuclid.org/euclid.ecp/1465263184, Concentration inequalities for order statistics. But this paper is mainly about concentration of order statistics of i.i.d. standard Gaussian random variables. The second paragraph in the Introduction of this paper quotes without a proof a general concentration of measure phenomenon for i.i.d. standard Gaussian random variables. **If someone can point out to me a reference on how this result is obtained, that will be great. Since I guess I can reverse engineer this result from its proof to get a result for i.i.d. standard uniform random variables.**
**Update 3 (April 14, 2017):**
By Theorem 2 of Chung 1949 "An estimate concerning the Kolmogoroff limit distribution, Trans. Amer. Math. Soc. 67: 36–50", we see
$$
P\left( \limsup\limits_{n\rightarrow\infty}\dfrac{n\sup\limits_{t\in\mathbb{R}%
}\left\vert \mathbb{S}_{n}\left( t\right) -S_{\ast}\left( t\right) \right\vert
}{\left( 2^{-1}n\log_{\left( 2\right) }n\right) ^{1/2}}=1\right)
=1
$$
for any continuous CDF $S_{\ast}$ on $\mathbb{R}$ with $\mathbb{S}_{n}\ $ as its empirical CDF (ECDF), where $\log_{(s)}$ means the natural logarithm composed by itself $s$ times. Therefore, these order statistics converges at a rate as per the iterated logrithm. In other words, when $n$ is very large, the classic location of each $X_{(r)}$ is $r/n$, with asymptotic deviation as
$$\tag{1}
\frac{\sqrt{2 \log_{(2)}n}}{\sqrt{n}}
$$
Basically, we know where these order statistics are.
However, this raises an interesting question as follows. Let $u_1 = X_{(1)}$, $u_2 = X_{(2)}-X_{(1)}$, $\ldots$, $u_k = X_{(k)}-X_{(k-1)}$, $\ldots$ , $u_n = X_{(n)}-X_{(n-1)}$, and $u_{n+1}=1-X_{(n)}$ be the uniform spacings. Further, let
$$
u^{\ast} = \max_{1 \le k \le n+1} u_{k}
$$
be the maximal uniform spacing.
Then by Devroye (1981, 1982) "Laws of the iterated logarithm for order statistics of uniform spacings" and "A log log law for maximal uniform spacings", we know
$$
P\left( \limsup\limits_{n\rightarrow\infty}\frac{n{u}
^{\ast}-\log n}{2\log_{\left( 2\right) }n}=1\right) =1,
$$
Namely, the maximal spacing is asymptotically no larger than
$$\tag{2}
\frac{\log n + 2 \log_{(2)} n}{n}
$$
Devroye (1981, 1982) also provide the law of the iterative logarithm for the minimal uniform spacing $u_{\ast} = \min_{1 \le k \le n+1} u_k$.
With this piece of information, we can **approxately** locate all $X_{(r)}$, by first locating $X_{(n)}$, then $X_{(n-1)}$ and so on.
I am curious on the following: **why is the maximal uniform spacing so small in magnitude compared to the maximal oscillation in the empirical distribution?** (I am aware of one quick and intuitive answer, which is "on average the individual spacing should be around $n^{-1}$ and for the empirical distribution central limit theorem plays a role to give $n^{-1/2}$". But this does not seems to be somewhat convincing.)