Skip to main content
5 of 19
added a reference
Chee
  • 984
  • 5
  • 18

Rate of convergence of uniform order statistics to their expectations

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}=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 Thanks for Henry's comment. I found this: https://projecteuclid.org/euclid.ecp/1465263184, Concentration inequalities for order statistics

Chee
  • 984
  • 5
  • 18