Sample Complexity for Order Statistics

Question

I have a sample complexity question which seems fairly basic, but for which I'm having trouble finding a reference.

Let $F$ be an unknown distribution over $[0,1]$. Denote by $X_{k:n}$ the $k$th of $n$ order statistic of $F$. That is, $X_{k:n}$ is a random variable distributed according to the $k$th highest of $n$ IID draws from $F$. Let $\mu_{k:n}=E[X_{k:n}]$ denote the mean of $X_{k:n}$.

For an arbitrary $k$ and $n$, I am interested in the number of samples required to estimate $\mu_{k:n}$. In other words, I'm interested in estimators that take $m$ (distinct from $k$ and $n$, probably much larger) IID samples from $F$ and output an estimator $\hat \mu_{k:n}$ that is as close to $\mu_{k:n}$ as possible. I would be happy with either a guarantee in terms of mean absolute deviation (i.e. minimizing $E[|\hat \mu_{k:n}-\mu_{k:n}|]$) or a PAC-style guarantee that $\text{Pr}[|\hat \mu_{k:n}-\mu_{k:n}|\geq \epsilon]\leq \delta$.

One naïve approach would be to divide your $m$ samples into $m/n$ blocks of $n$ samples, and average the $k$th sample from each block. The performance of this estimator could be analyzed fairly easily using Chernoff bounds. I'm wondering if there's something smarter one can do. Lower bounds would also be of interest.

Answer 1

One way to approach this problem is via the CDF transformation. Consider $Z=F(X)$. We know $Z$ is uniformly distributed in $[0,1]$. Let $Z_{(1)},...,Z_{(m)}$ be the order statistics of these $m$ samples (after transforming to Z).

It can be shown that $Z_{(t)}\sim \text{Beta}(t,m+1-t)$. Using this, $Z_{(m\cdot k/n)}=F(X_{(m\cdot k/n)})$ is a consistent estimator for $F(\mu_{k:n})$.

As to the rates, since the exact distribution of $Z_{(t)}$ is known, it can be shown that ${E}[|F(X_{(m\cdot k/n)})-F(\mu_{k:n})|]\approx \sqrt{\frac{2}{\pi}}\sqrt{\frac{\min\{k/n,1-k/n\}}{m}}$. Now if you have some kind of constraint on $F$, say $F$ is Lipschitz with constant $c$, ${E}[|X_{(m\cdot k/n)}-\mu_{k:n}|]\le \frac{1}{c}\cdot {E}[|F(X_{(m\cdot k/n)})-F(\mu_{k:n})|]\approx \frac{1}{c}\sqrt{\frac{2}{\pi}}\sqrt{\frac{\min\{k/n,1-k/n\}}{m}}$. Therefore $X_{(m\cdot k/n)}$ is a reasonable estimator for $\mu_{k:n}$.

On the other hand, if there is no constraint on $F$ whatsoever, there is no way one can estimate $\mu_{k:n}$ consistently even with $m\rightarrow \infty$.