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 upper bounded by $$\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$. Specifically, $$ P\left( \liminf\limits_{n\rightarrow\infty}\left( n {u}_{\ast}-\log n +\log_{\left( 3\right) }n\right) =-\log2\right) =1 $$

This means that the miminal spacing asympotitcally is no smaller than $$\tag{3} \frac{-\log 2 + \log n - \log_{(3)}n}{n} $$ With this piece of information, we can approximately locate all $X_{(r)}$, by first locating $X_{(n)}$, then $X_{(n-1)}$ and so on.

Question #2:

I am curious on the following: Look at the largest order statistic $X_{(n)}$ and the smallest $X_{(1)}$. Then each of them has two different rates of convergence, $(1)$ and $(2)$, respectively to $0$ and $1$. Since both rates are correct, we see that the extreme statistics converge much faster than non-extreme ones.

Why is the maximal uniform spacing so small in magnitude compared to the maximal oscillation in the empirical distribution? Which rate of convergence would you use to identify the locations of uinform order statistics? (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.)

Question #3 (April 16, 2017):

For the convergence of the order statistics to their classic locations, the first rate is based on deviation of empirical distribution, whereas the second based on uniform spacing.

This prompts me to think: is there a rate of convergence for uniform order statistics that is better than $(1)$ if we know that $F(t)=t$, i.e., is the rate in Chung's 1949 paper optimal for convergence of empirical distribution of uniform random variables? (Probably not since that result was obtained for the space of functions of totally bounded variation.)

Update (April 21, 2017): answer to question #3 The convergence rate of uniform order statistics to their expecations obtained from $(1)$ is NOT optimal for order statisic $X_{(k)}$ for which $k$ or $n-k$ is bounded. However, it is optimal for $X_{(k)}$ for which $k= c_n n$ with $$1 > \limsup c_n \ge \liminf c_n >0.$$ In other words, close to the edges 0 or 1, the optimal reate of convergence is proportional to $$\frac{\log n}{n},$$ whereas in other parts of the compact interval $[0,1]$ the optimal rate of convergence is $$\frac{\sqrt{2 \log_{(2)}n}}{\sqrt{n}}.$$ This can be seen from:

Lemma A2.1 on page 148 of "asymptotic expansions for the power of distribution free tests in the one-sample problem" by Albers, Bickel and Zwet.