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

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

<p>As to the rates, since the exact distribution of <span class="math-container">$Z_{(t)}$</span> is known, it can be shown that <span class="math-container">${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}}$</span>. Now if you have some kind of constraint on <span class="math-container">$F$</span>, say <span class="math-container">$F$</span> is Lipschitz with constant <span class="math-container">$c$</span>, <span class="math-container">${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}}$</span>. Therefore <span class="math-container">$X_{(m\cdot k/n)}$</span> is a reasonable estimator for <span class="math-container">$\mu_{k:n}$</span>.</p>

<p>On the other hand, if there is no constraint on <span class="math-container">$F$</span> whatsoever, there is no way one can estimate <span class="math-container">$\mu_{k:n}$</span> consistently even with <span class="math-container">$m\rightarrow \infty$</span>.</p>

CC BY-SA 4.0
2018-11-29T23:23:43.420Z
2018-11-29T23:23:43.420Z
Vaishakh Ravi
<p>I have a sample complexity question which seems fairly basic, but for which I'm having trouble finding a reference.</p>

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

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

<p>One naïve approach would be to divide your <span class="math-container">$m$</span> samples into <span class="math-container">$m/n$</span> blocks of <span class="math-container">$n$</span> samples, and average the <span class="math-container">$k$</span>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.</p>

CC BY-SA 4.0
2018-10-22T21:37:22.030Z
What do you get using the Chernoff bound and sub-samples, as you suggested? An alternative is bounded differences and McDiarmid’s inequality, but the bounds it gives aren’t great.
Aryeh
<pr.probability><st.statistics><sample-complexity><chernoff-bound><pac-learning>
Sample Complexity for Order Statistics
Lemke
# Sample Complexity for Order Statistics

(Asked by: username_0 on 2018-10-22)

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.

**Tags:** pr.probability, st.statistics, sample-complexity, chernoff-bound, pac-learning

> **Comments:**
> **username_1**: What do you get using the Chernoff bound and sub-samples, as you suggested? An alternative is bounded differences and McDiarmid’s inequality, but the bounds it gives aren’t great.  

---

## 1 answers

### Answer by username_2 on 2018-11-29. Score: 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$.


---

