Law of large numbers for partial sums of order statistics

Question

Let $X_1, X_2,\cdots$ be independent and identically distributed random variables supported on the nonnegative integers with finite mean $\mu$. Denote the $i$th order statistic of the sub-collection $X_1,\cdots, X_n$ by $X_{(i)}^n$ so that $X^n_{(1)} \leq X^n_{(2)} \cdots \leq X^n_{(n)}$ with ties broken in some arbitrary manner.

In a special application to the appearance of giant components in the configuration model from https://arxiv.org/abs/1601.03714, we are needing the lemma:

Given $\epsilon >0$, there exists $\delta >0$ such that \begin{align} \mathbf P \left( \frac 1n \sum_{i=1}^{\lfloor (1- \delta) n \rfloor } X_{(i)}^n \geq (1-\epsilon)\mu \right) \to 1 \text{ as $n \to \infty$. } \end{align}

As the Law of Large Numbers gives $n^{-1} \sum_1^n X^n_{(i)} \to \mu$, the displayed equation is the claim that the sum of a large enough proportion of the order statistics captures an arbitrarily large proportion of the complete sum.

This seems true and holds for continuous random variables; See Theorem 2.2 of Bruss and Robertson. "Wald's Lemma'for sums of order statistics of iid random variables."

However, we are struggling to adapt the proof or find a counterexample for the discrete random variable setting.

Answer 1

Let $X$ be a random variable with some CDF $F(x)=P[X\leq x]$ for all $x \in \mathbb{R}$.

Claim 1: Either there is an $M \in \mathbb{R}$ such that $P[X>M]=0$ and $P[X=M]>0$, or there is an increasing sequence of real numbers $\{M_i\}_{i=1}^{\infty}$ such that $P[X>M_i]>0$ for all $i \in \{1, 2, 3, ...\}$ and $\lim_{i\rightarrow\infty} P[X>M_i]=0$.

Proof: Define $$ M = \sup\{t \in \mathbb{R}: P[X>t]>0\}$$ If $M=\infty$ then we have $P[X>i]>0$ for all positive integers $i$, and we already know $\lim_{i\rightarrow\infty} P[X>i]=0$ from basic properties of a CDF, so we can define $M_i=i$ and we are done.

If $M$ is finite then we know $P[X>t]=0$ for all $t>M$. Since $\{X>M+1/n\}\nearrow \{X>M\}$, by continuity of probability we have $0=P[X>M+1/n]\nearrow P[X>M]$, and so $P[X>M]=0$. If $P[X=M]>0$ then we are done.

The remaining case is when $M$ is finite and $P[X=M]=0$. We already know $P[X>M]=0$. By definition of $M$ we have $P[X>M-1/i]>0$ for all $i \in \{1, 2, 3, ...\}$. Also $$\{M-1/i<X\leq M\} \searrow \{X=M\}$$ Thus by continuity of probability $$ P[M-1/i<X\leq M]\searrow P[X=M]=0$$ But $$P[X>M-1/i] = P[M-1/i<X\leq M] + P[X>M] = P[M-1/i<X\leq M]$$ and so $P[X>M-1/i]\rightarrow 0$. So we define $M_i = M-1/i$ and we are done. $\Box$

Claim 2: Assume $\{X_i\}_{i=1}^{\infty}$ are i.i.d. nonnegative random variables with CDF $F(x)$ and with finite mean $E[X]$. Then for any $\epsilon>0$ there is a $\delta>0$ such that
$$ P\left[\frac{1}{n}\sum_{i \in I_n(\delta)} X_i \geq E[X] - \epsilon\right]\rightarrow 1$$ where $I_n(\delta)$ is the set of the $\lfloor(1-\delta)n\rfloor$ smallest variables from $\{X_1, ..., X_n\}$.

Proof: Fix $\epsilon>0$. Let $X=X_1$.

Case 1: Suppose there is an increasing sequence $\{M_n\}_{n=1}^{\infty}$ with $P[X>M_n]>0$ and $P[X>M_n]\rightarrow 0$. So we can find a sufficiently large value $M$ (where $M=M_n$ for some $n$) such that $P[X>M]>0$ and $E[X1\{X\leq M\}]\geq E[X]-\epsilon/2$. The fraction of $\{X_i\}$ that are larger than $M$ converges with prob 1 to $P[X>M]$. Define $\delta = P[X>M]/2$. Then for sufficiently large $n$, the largest $\delta$ fraction of the $\{X_1, ..., X_n\}$ values are all larger than $M$, so $$ \sum_{i \in I_n(\delta)} X_i \geq \sum_{i=1}^n X_i1\{X_i\leq M\}$$ So $$ \frac{1}{n}\sum_{i \in I_n(\delta)} X_i \geq \frac{1}{n}\sum_{i=1}^n X_i1\{X_i\leq M\}$$ The right-hand-side converges to $E[X1\{X\leq M\}]$ with prob 1, so with some additional steps we are done. $\Box$

Case 2: There is an $M$ such that $P[X=M]>0$ and $P[X>M]=0$.

In this case, with $\delta \leq P[X=M]/2$, the largest $\delta$ fraction of $\{X_1, ..., X_n\}$ will all eventually take the value $M$ itself. I believe with some additional steps we are done.

Answer 2

Throughout the argument we let $n_\delta = \lfloor (1- \delta) n \rfloor$.

First we assume that $\mathbb P(X_1 > x) >0$ for all $x\geq 0$ so that $X_1$ has unbounded positive support. Set $$M := \min \{ x \colon \mathbb E [X_1 \mathbf 1\{X_1 \leq x\}] \geq (1- \epsilon/2) \mu \},$$ which exists by the hypothesis that $\mathbb E X_1 = \mu$. Let $0< p := P(X_1 > M)$. The law of large numbers ensures that $$\frac 1n \sum_1^n \mathbf1\{X_i \leq M\} \leq 1- \frac p 2 >0 \text{ and } \frac 1n \sum_1^n X_i \mathbf 1\{X_i \leq M\} \geq (1- \epsilon ) \mu $$ with high probability. Setting $\delta = p/2$, we then have \begin{align} \frac 1n \sum_{i =1}^{n_\delta} X_{(i)}^n \geq \frac 1n \sum_{i=1}^n X_i \mathbf\{ X_i \leq M\} \geq (1- \epsilon) \mu \label{eq:ub} \end{align} with high probability. This is the claimed relation for the unbounded case.

Next, suppose that $M = \min \{ x \colon \mathbb P(X_1 \leq M) = 1\}$ exists for some finite $M$ so that the positive support of $X_1$ is bounded. Let $p = \mathbb P(X_1 = M) >0$. Note that if $p=1$, then the $X_i$ are deterministic and the desired claim is trivial. So, suppose that $0<p<1$ and set $\delta = \epsilon p \mu / M$. Since the mean $\mu$ of $X_1$ is bounded by the maximum value $M$ in the support of $X_1$ we have $\mu /M \leq 1$. This, along with the assumption that $\epsilon <1$, implies that $\delta < p$. Thus, the law of large numbers ensures that $X_{(i)}^n = M$ for all $i > n_\delta$ with high probability. It follows that $$\frac 1n \sum_{i=n_\delta +1}^{n} X_{(i)}^n = \frac 1 n (n - (n_\delta +1) ) M \leq \delta M = \epsilon p \mu \qquad (*) $$ with high probability. The claimed bound on $\sum_1^{n_\delta} X_{(i)}^n$ follows from combining $(*)$ with the following consequence of the law of large numbers \begin{align} \frac 1n \sum_{i=1}^{n_\delta} X_{(i)}^n + \frac 1n \sum_{i =n_\delta+1}^n X_{(i)}^n = \frac 1n \sum_{i=1}^n X_i \geq (1- \epsilon p) \mu \label{eq:end2} \end{align} with high probability.