Rate of convergence of uniform order statistics to their expectations

Question

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.

Answer 1

For your first question, Rigollet has a series of notes(with minor typos) that dicusses basics of this kind of tail bounds. The result you mentioned in the "introduction" is actually the classic Hoeffding bound that mentioned by Rigollet in this set of notes.

High Dimensional Statistics, Philippe Rigollet (2015) http://www-math.mit.edu/~rigollet/PDFs/RigNotes15.pdf

If you are concerned with the order statistics, you usually want to restrict yourself to a narrower class of distributions, say the classic paper [2].

For a general distribution family, it is almost impossible to obtain a tail-bound on the order statistics due to the concentration of measures phenomenon. Another keyword you may want to look into is "U-statistics" because the (full) order statistic is an example of U-statistics, the following quote from [1] is the best description of the power of U-statistics

Theoretically, for these U-statistics we can study the whole spectrum of asymptotic problems which were investigated for independent variables. As a matter of fact, it is necessary to control the nature of dependence in order to obtain meaningful results. We restrict ourselves to exchangeable and weakly exchangeable variables, rank statistics, samplings from finite populations, weakly dependent random variables, bootstrap-variables, and to order statistics.[1]p.15

Concentration bounds on U-statistics is a research subject that involves many false claims and hardcore techniques, so I think it is not too hard to find one but never too careful to use one.

---

Update in response to update3. Why is the maximal uniform spacing so small in magnitude compared to the maximal oscillation in the empirical distribution? This is not something surprising. you can always have very large spacings but small Kolomogorov-Smirnov norm, which measures on the space of $\mathcal{M}(\mathbb{R})$ while the spacing is measuring $\mathbb{R}$. If you look into Luc's argument, you will see his comments on it.

For the simplest example, given a set of data $\{0,0.1,0.9\cdots,0.9\text{(n repeated 0.9)},1\}$ and $\{0,0.1\cdots,0.1\text{(n repeated 0.1)},0.9,1\}$, their empirical measures has completely different cdfs but they both have the same maximal spacing of $0.8$. as the number $n$ of repeated observation increase, the KS norm between these two cdfs can be arbitrarily close to 1.

Reference

[1]Korolyuk, Vladimir S., and Yu V. Borovskich. Theory of U-statistics. Vol. 273. Springer Science & Business Media, 2013.

[2] Gupta, S. Das, et al. "Inequalities on the probability content of convex regions for elliptically contoured distributions." Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability (Univ. California, Berkeley, Calif., 1970/1971). Vol. 2.1972.