Sequence of order statistic converges to median?

Question

Suppose that $(X_1,...,X_N)$ be $N$ iid samples from uniform distribution. Let $X_{(n)}$ be $n$-th order statistic. It sounds natural that $X_{N/2}$ converges to the median, $1/2$. (interpret $N/2$ as the largest integer which does not exceed $N/2$). More generally, given continuous distribution $F$ with support $[a,b]$ and $\alpha\in (0,1)$, can we show that $X_{(\alpha N)}$ converges to $F^{-1}(\alpha)$ in probability, or distribution, or almost sure?

Answer 1

Let $U_i\sim \mathcal{U}(0,1)$

The distribution of the $N\alpha$ order statistic from a uniform distribution has a standard beta distribution (link). Specifically:

$U_{(\alpha N)}\sim B(N\alpha,N-N\alpha+1)$

For reference, if $T\sim B(a,b)$ then $E[T]=\frac{a}{a+b}\;\; Var[T]=\frac{ab}{(a+b)^2(a+b-1)}$

Therefore, $E[U_{(\alpha N)}]=\mu_{\alpha,N}=\frac{\alpha N}{N+1}$ and $Var[U_{(\alpha N)}]=\frac{\alpha N(N-\alpha N +1)}{N(N+1)^2} = \sigma^2_{\alpha,N}$

Using Chebyshev's Inequality:

$P(|U_{(\alpha N)}-\mu_{\alpha,N}]\geq \epsilon|\leq \frac{\sigma^2_{\alpha,N}}{\epsilon^2}$

and the fact that $\lim\limits_{N\to \infty} \mu_{\alpha,N} = \alpha$ and $\lim\limits_{N\to \infty}\sigma^2_{\alpha,N} = 0 $

That $\forall \epsilon \exists N: P(|U_{(\alpha N)}-\mu_{\alpha,N}]\geq \epsilon|\leq \frac{\sigma^2_{\alpha,N}}{\epsilon^2}$, hence $U_{(\alpha N)} \xrightarrow{p} \alpha$

Can we show something stronger? To show almost sure convergence, we need to demonstrate that excursions of size $\epsilon>0$ from $\alpha$ do not occur infinitely often (via Borel-Cantelli lemma) and that this holds for arbitrarily small $\epsilon$.

Specifically, we need to define a sequence of events $A_n$ such that $\sum P(A_n)<\infty$, which implies that only finitely many of the $A_n$ occur. If we define $A_N(\epsilon_N,\alpha):= |U_{\alpha N}-\alpha|>\epsilon_N$ where $\epsilon_N>0$ and $\epsilon_N \to 0$ monotonically, what is the probability that this occurs infinitely often?

Let $P(A_N(\epsilon_N,\alpha))=P_{B(N\alpha,N-N\alpha+1)}(\{\alpha-\epsilon_N>U_{N\alpha}\}\cup\{U_{N\alpha}>\alpha+\epsilon_N\})$, where $P_{B(N\alpha,N-N\alpha+1)}(\cdot)$ is the cdf of a standard beta distribution.

The trick is to define a sequence of decreasing errors such that the limit of the errors is 0 and $\sum P(A_N(\epsilon_N,\alpha)) <\infty$

I played around with various exponentially decreasing errors (to avoid the high errors in the beginning) but didn't have much luck. You'll need some heavier theory than I know to prove one way or the other.

New Info

I thought of trying a different approach by examining the convergence of the empirical distribution function to the true distribution function. It turns out that the ECDF converges almost surely to the CDF, therefore, sample percentiles converge almost surely to their true percentiles. See here.

Answer 2

This is an old question but here is a complete answer to it.

Actually this is true for any distribution and not necessarily for uniform distribution. Assume that $F^{-1}(\alpha)$ is well defined. That is, in a sufficiently small neighbourhood of $\alpha$, $F$ is strictly increasing and $F^{-1}(\alpha)$ is uniquely defined. But one also needs to be careful and say $X_{(\lfloor \alpha N\rfloor)}$.

Define the empirical cdf $\displaystyle F_{n}(x)=\frac{1}{n}\sum_{k=1}^{n}\mathbf{1}_{\{X_{n}\leq x\}}$ .

Now notice that $nF_{n}(x)\geq k\iff x_{(k)}\leq x $

\begin{align}P(X_{(\lfloor \alpha N\rfloor)}-F^{-1}(\alpha)>\epsilon)&= 1-P(X_{(\lfloor \alpha N\rfloor)}-F^{-1}(\alpha)\leq \epsilon)\\ &=1-P(X_{(\lfloor \alpha N\rfloor)}\leq F^{-1}(\alpha)+\epsilon)\\ &=1-P\bigg(NF_{N}(F^{-1}(\alpha)+\epsilon)\geq \lfloor \alpha N\rfloor\bigg)\\ &=1-P\bigg(F_{N}(F^{-1}(\alpha)+\epsilon)\geq\frac{\lfloor \alpha N\rfloor}{N}\bigg)\\ &=P\bigg(F_{N}(F^{-1}(\alpha)+\epsilon)<\frac{\lfloor \alpha N\rfloor}{N}\bigg)\end{align}

Now $F_{N}(x)$ converges to $F(x)$ by Strong Law of Large Numbers almost surely for all $x\in\Bbb{R}$

Now $F_{N}(F^{-1}(\alpha)+\epsilon)\xrightarrow{P} F(F^{-1}(\alpha)+\epsilon)$ and so $F_{N}(F^{-1}(\alpha)+\epsilon)-F(F^{-1}(\alpha)+\epsilon)\xrightarrow{P}0$

Now \begin{align}&P\bigg(F_{N}(F^{-1}(\alpha)+\epsilon)<\frac{\lfloor \alpha N\rfloor}{N}\bigg)\\&=P\bigg(F_{N}(F^{-1}(\alpha)+\epsilon)-F(F^{-1}(\alpha)+\epsilon)<\frac{\lfloor \alpha N\rfloor}{N}-F(F^{-1}(\alpha)+\epsilon)\bigg)\end{align}

But we have that $\frac{\lfloor \alpha N\rfloor}{N}\to \alpha$ and due to the strictly increasing assumption, $F^{-1}(F(\alpha)+\epsilon)>F^{-1}(F(\alpha))=\alpha$. Thus for all $N$ large enough $\frac{\lfloor \alpha N\rfloor}{N}-F(F^{-1}(\alpha)+\epsilon)<-\delta$ for some $\delta>0$

Hence, \begin{align}&P\bigg(F_{N}(F^{-1}(\alpha)+\epsilon)-F(F^{-1}(\alpha)+\epsilon)<\frac{\lfloor \alpha N\rfloor}{N}-F(F^{-1}(\alpha)+\epsilon)\bigg)\\&\leq P\bigg(F_{N}(F^{-1}(\alpha)+\epsilon)-F(F^{-1}(\alpha)+\epsilon)<-\delta\bigg)\xrightarrow{N\to \infty} 0\end{align}

Similarly, one shows that $P(X_{(\lfloor \alpha N\rfloor)}-F^{-1}(\alpha)\leq-\epsilon)\xrightarrow{N\to\infty}0$.

This proves that $X_{(\lfloor \alpha N\rfloor)}\xrightarrow{P}F^{-1}(\alpha)$

Now $X_{(\lfloor \alpha N\rfloor)}$ has a subsequence that converges almost surely to $F^{-1}(\alpha)$ . But then, as $X_{(\lfloor \alpha N\rfloor)}$ is an non-decreasing sequence, we have that $X_{(\lfloor \alpha N\rfloor)}\xrightarrow{a.s.}F^{-1}(\alpha)$