<p>This is not a complete answer by any means, but just a quick estimate on <span class="math-container">$\mathbb{E}[\sum_{i=1}^k X_{[i]}]$</span> that is slightly better than the trivial bound of <span class="math-container">$O(k\sqrt{\log n})$</span>. If this is your goal, I would think it is easier to go directly for it than consider any given <span class="math-container">$X_{[k]}$</span>. Let <span class="math-container">$X_S=\sum_{i\in S} X_i$</span> for a subset <span class="math-container">$S\subseteq [n]$</span> and <span class="math-container">$Y_k=\sum_{i=1}^k X_{[i]}$</span>. Using the same technique as in the first link,
<span class="math-container">\begin{align}
\exp(t\mathbb{E}[Y_k])&amp;\leq \mathbb{E}[\exp(tY_k)]\\
&amp;=\mathbb{E}\bigg[\max_{S\subseteq [n]:\vert S\vert=k}\exp(tX_S)\bigg]\\
&amp;\leq \sum_{S\subseteq [n]:\vert S\vert=k}\mathbb{E}[\exp(tX_S)]\\
&amp;=\sum_{S\subseteq [n]:\vert S\vert=k}\exp\bigg(\frac{kt^2}{2}\bigg)\\
&amp;={n \choose k}\exp\bigg(\frac{kt^2}{2}\bigg).
\end{align}</span>
Taking (natural) logarithms, we find
<span class="math-container">$$
\mathbb{E}[Y_k]\leq \frac{\log{n \choose k}}{t}+\frac{kt}{2}.
$$</span>
Optimizing gives <span class="math-container">$t=\sqrt{\frac{2\log{n \choose k}}{k}}$</span> so we deduce
<span class="math-container">$$
\mathbb{E}[Y_k]\leq \sqrt{2k\log{n \choose k}}.
$$</span></p>

<p>For <span class="math-container">$k=o(n)$</span>, it is known that <span class="math-container">$\log{n \choose k}=(1+o(1))k\log(n/k)$</span>, so in this regime, we get
<span class="math-container">$$
\mathbb{E}[Y_k]\leq k\sqrt{2(1+o(1))\log(n/k)},
$$</span>
which for <span class="math-container">$k=\log n$</span>, say, is a bit better than the naive bound.</p>

<p>When <span class="math-container">$k=\alpha n$</span> for some constant <span class="math-container">$\alpha$</span>, one instead has <span class="math-container">$\log{n \choose k}=(1+o(1))H(\alpha)n$</span>, where <span class="math-container">$H(p)=-p\log p-(1-p)\log(1-p)$</span> is the entropy function. So in this regime, that would give
<span class="math-container">$$
\mathbb{E}[Y_k]\leq n\sqrt{2(1+o(1))\alpha H(\alpha)}.
$$</span></p>

<p><strong>Lower bounds added for completeness:</strong> for linear <span class="math-container">$k$</span>, one can get decent linear lower bounds that degrade as <span class="math-container">$\alpha\to 0$</span> but is tight at <span class="math-container">$\alpha=1/2$</span>. Let <span class="math-container">$\alpha&lt;1/2$</span>, then by the Chernoff bound, 
<span class="math-container">$$
\Pr(X_{\alpha n+1}\leq 0)\leq \exp\bigg(\frac{-(1/2-\alpha)^2n}{2}\bigg).
$$</span>
It is known that for <span class="math-container">$i&lt;j$</span>, the conditional distribution of <span class="math-container">$X_{[i]}$</span> given <span class="math-container">$X_{[j]}=x$</span> is the same as the unconditional distribution of <span class="math-container">$X_{[i]}$</span> taken from a sample of size <span class="math-container">$j-1$</span> conditioned to be larger than <span class="math-container">$x$</span>. As we are summing over all <span class="math-container">$i\leq \alpha n$</span> and taking expectations, we find that 
<span class="math-container">$$
\mathbb{E}[\sum_{i=1}^{\alpha n} X_{[i]}\vert X_{\alpha n+1}\geq 0]\geq \mathbb{E}[\sum_{i=1}^{\alpha n} Y_i],
$$</span>
where the <span class="math-container">$Y_i$</span> are normal random variables conditioned to be larger than <span class="math-container">$0$</span>, which are known to have expectation <span class="math-container">$\sqrt{2/\pi}$</span>. We also find that
<span class="math-container">$$
\mathbb{E}[\sum_{i=1}^{\alpha n} X_{[i]}\vert X_{\alpha n+1}\leq 0]\geq 0,
$$</span>
as for each <span class="math-container">$x&lt;0$</span>, conditioning on <span class="math-container">$X_{\alpha n}=x$</span>, by the same reasoning we are now taking expectations over a sample of size <span class="math-container">$\alpha n$</span> normal random variables conditioned to be at least <span class="math-container">$x$</span>, which by symmetry of the normal distribution is at least <span class="math-container">$0$</span> (formally, we are using that the sum over the whole sample makes the labelling of the order statistics irrelevant). We conclude that
<span class="math-container">$$
\mathbb{E}[\sum_{i=1}^{\alpha n} X_{[i]}]\geq \bigg(1-\exp\bigg(\frac{-(1/2-\alpha)^2n}{2}\bigg)\bigg)\alpha n\sqrt{2/\pi}=(1-o(1))\alpha n \sqrt{2/\pi}.
$$</span>
This holds for all <span class="math-container">$\alpha&lt;1/2$</span>, and by monotonicity of the left hand side in <span class="math-container">$\alpha$</span> for <span class="math-container">$\alpha&lt;1/2$</span> and taking limits, we can further conclude using the upper bound in the comments
<span class="math-container">$$
\mathbb{E}[\sum_{i=1}^{n/2} X_{[i]}]=(1-o(1))n\sqrt{1/(2\pi)}.
$$</span></p>

<p>Obviously similar lower bounds hold for <span class="math-container">$k=o(n)$</span> but these aren't super useful as they are of vastly different order than the upper bound.</p>

<p><strong>Numerical Simulations:</strong> Numerical simulations suggest that these bounds are surprisingly decent in the two regimes mentioned in the post. Note that for any <span class="math-container">$k$</span>, the function <span class="math-container">$f(x_1,\ldots,x_n)=\sum_{i=1}^k x_{[i]}$</span> is Lipschitz, so by Gaussian concentration, one expects simulations to roughly approximate the expectation. For instance, for <span class="math-container">$k=\log(n)$</span>, here is a plot of the upper bound with that of simulation, with the top curve being the naive bound of <span class="math-container">$\sqrt{2}\log(n)^{3/2}$</span> and the lower curve the given bound:<a href="https://i.sstatic.net/UgeiE.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/UgeiE.png" alt="enter image description here"></a></p>

<p>In the linear <span class="math-container">$k$</span> regime, for the few values I tried, the constant of the upper bounds seems to be off by a factor of at most <span class="math-container">$3$</span> (at <span class="math-container">$\alpha=1/2$</span>, where we have computed the exact asymptotics). For instance, for <span class="math-container">$k=n/4$</span>, the plot with the bound looks like: <a href="https://i.sstatic.net/LFyoT.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/LFyoT.png" alt="enter image description here"></a></p>

<p>The upper bounds seem pretty good for small constant <span class="math-container">$\alpha$</span>, while the lower bounds degrade. For instance, here is <span class="math-container">$\alpha=.001$</span>:<a href="https://i.sstatic.net/b9GIz.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/b9GIz.png" alt="enter image description here"></a></p>

<p>Here's one more plot (because I can't resist) with <span class="math-container">$k=\sqrt{n}$</span>: <a href="https://i.sstatic.net/jSuWl.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/jSuWl.png" alt="enter image description here"></a>Hope this helps!</p>

CC BY-SA 4.0
2019-06-28T17:06:48.687Z
Wow, these bounds are actually perfect for my application!! I really appreciate the graphs too showing that they're tight haha. Your strategy of bounding the sum directly, instead of each of the individual terms, is much smarter. Thank you!!
Uthsav Chitra
CC BY-SA 4.0
2019-06-28T21:37:13.963Z
You're welcome! By the way, for the specific case of $k=n/2$, one has $\mathbb{E}[\sum_{i=1}^{n/2} X_{[i]}]=\frac{1}{2}\mathbb{E}[\sum_{i=1}^{n/2} X_{[i]}-\sum_{i=1}^{n/2} X_{[n-i]}]$, so by TI, $\mathbb{E}[\sum_{i=1}^{n/2} X_{[i]}]\leq \frac{1}{2}\mathbb{E}[\sum_{i=1}^n \vert X_{[i]}\vert]=n\sqrt{1/(2\pi)}$. Simulations suggests this is essentially exact; there's probably a way to get a lower bound for $k=\alpha n$, $\alpha<1/2$ of $(1-o(1))\alpha n\sqrt{2/\pi}$ (the intuition is the top $\alpha n$ will be positive w.h.p. and so should be at least the expected absolute value of a Gaussian).
Jason Gaitonde
CC BY-SA 4.0
2019-06-28T23:49:37.033Z
@UthsavChitra in case you're interested, I've added a proof of the linear lower bound that is tight at $\alpha=1/2$. Hope this is helpful!
Jason Gaitonde
CC BY-SA 4.0
2019-06-29T17:15:19.337Z
Note that using these bounds you can derive asymptotic bounds on $\mathbb{E} X_{[k]}$, since deterministically $kX_{[k]} \leq \sum_{i=1}^k X_{[k]}$. Thus $\mathbb{E} X_{[k]} \leq \tfrac{1}{k}\mathbb{E} Y_k \leq \sqrt{\tfrac{2}{k}\log\tfrac{n}{k}}$. For example, if $k = o(n)$ as above, this gives $\mathbb{E} X_{[k]} \leq  \sqrt{(2+o(1))\log \tfrac{n}{k}}$.
cdipaolo
CC BY-SA 4.0
2019-06-28T01:24:49.360Z
2019-06-28T23:48:30.390Z
2019-06-28T23:48:30.390Z
Jason Gaitonde
<p>I'm interested in the following problem. Let <span class="math-container">$X_1, \dots, X_n$</span> be iid samples with a <span class="math-container">$N(0,1)$</span> distribution. Let <span class="math-container">$X_{[k]}$</span> be the <span class="math-container">$k$</span>-th largest element of <span class="math-container">$\{X_1, \dots, X_n\}$</span>, so e.g. <span class="math-container">$X_{[1]} = \max_i X_i$</span>. </p>

<p>Are there simple big-O bounds on <span class="math-container">$X_{[k]}$</span> for, say, all <span class="math-container">$k &lt; n/2$</span>? I know that <span class="math-container">$X_{[1]} = O(\sqrt{\log{n}})$</span> (see <a href="http://www.gautamkamath.com/writings/gaussian_max.pdf" rel="noreferrer">here</a>), and more generally, <span class="math-container">$X_{[c]} = O(\sqrt{\log{n}})$</span> for constant <span class="math-container">$c$</span> (see <a href="https://cstheory.stackexchange.com/questions/14530/balls-and-bins-analysis-in-the-m-gg-n-regime-gaps">here</a>). But what about <span class="math-container">$X_{[\log{n}]}$</span> or <span class="math-container">$X_{[n/4]}$</span>, for example?</p>

<p>My motivation is that I want to calculate <span class="math-container">$\sum_{i=1}^k E[X_{[i]}]$</span> for various values of <span class="math-container">$k$</span>.</p>

<p>Thanks!</p>

CC BY-SA 4.0
2019-06-28T08:07:01.257Z
It's addressed at https://stats.stackexchange.com/questions/9001/approximate-order-statistics-for-normal-random-variables
Bjørn Kjos-Hanssen
CC BY-SA 4.0
2019-06-28T16:04:21.517Z
@BjørnKjos-Hanssen These are not very nice-looking "simple big-O bounds" however (which I assume is the main point of the OP's question).
Clement C.
CC BY-SA 4.0
2019-06-28T18:13:21.647Z
@ClementC. is correct, I saw that answer but those are not big-O bounds
Uthsav Chitra
<lower-bounds><pr.probability><upper-bounds>
Big-O bounds on the k-th largest element of iid Gaussians
Uthsav Chitra
# Big-O bounds on the k-th largest element of iid Gaussians

(Asked by: username_0 on 2019-06-27)

I'm interested in the following problem. Let $X\_1, \dots, X\_n$ be iid samples with a $N(0,1)$ distribution. Let $X\_{[k]}$ be the $k$-th largest element of $\{X\_1, \dots, X\_n\}$, so e.g. $X\_{[1]} = \max\_i X\_i$.

Are there simple big-O bounds on $X\_{[k]}$ for, say, all $k < n/2$? I know that $X\_{[1]} = O(\sqrt{\log{n}})$ (see [here](http://www.gautamkamath.com/writings/gaussian_max.pdf)), and more generally, $X\_{[c]} = O(\sqrt{\log{n}})$ for constant $c$ (see [here](https://cstheory.stackexchange.com/questions/14530/balls-and-bins-analysis-in-the-m-gg-n-regime-gaps)). But what about $X\_{[\log{n}]}$ or $X\_{[n/4]}$, for example?

My motivation is that I want to calculate $\sum\_{i=1}^k E[X\_{[i]}]$ for various values of $k$.

Thanks!

**Tags:** lower-bounds, pr.probability, upper-bounds

> **Comments:**
> **username_1**: It's addressed at https://stats.stackexchange.com/questions/9001/approximate-order-statistics-for-normal-random-variables  
> **username_2**: @BjørnKjos-Hanssen These are not very nice-looking "simple big-O bounds" however (which I assume is the main point of the OP's question).  
> **username_0**: @ClementC. is correct, I saw that answer but those are not big-O bounds  

---

## 1 answers

### Answer by username_3 on 2019-06-28. Score: 6 | Accepted answer

This is not a complete answer by any means, but just a quick estimate on $\mathbb{E}[\sum\_{i=1}^k X\_{[i]}]$ that is slightly better than the trivial bound of $O(k\sqrt{\log n})$. If this is your goal, I would think it is easier to go directly for it than consider any given $X\_{[k]}$. Let $X\_S=\sum\_{i\in S} X\_i$ for a subset $S\subseteq [n]$ and $Y\_k=\sum\_{i=1}^k X\_{[i]}$. Using the same technique as in the first link,
\begin{align}
\exp(t\mathbb{E}[Y\_k])&\leq \mathbb{E}[\exp(tY\_k)]\\
&=\mathbb{E}\bigg[\max\_{S\subseteq [n]:\vert S\vert=k}\exp(tX\_S)\bigg]\\
&\leq \sum\_{S\subseteq [n]:\vert S\vert=k}\mathbb{E}[\exp(tX\_S)]\\
&=\sum\_{S\subseteq [n]:\vert S\vert=k}\exp\bigg(\frac{kt^2}{2}\bigg)\\
&={n \choose k}\exp\bigg(\frac{kt^2}{2}\bigg).
\end{align}
Taking (natural) logarithms, we find
$$
\mathbb{E}[Y\_k]\leq \frac{\log{n \choose k}}{t}+\frac{kt}{2}.
$$
Optimizing gives $t=\sqrt{\frac{2\log{n \choose k}}{k}}$ so we deduce
$$
\mathbb{E}[Y\_k]\leq \sqrt{2k\log{n \choose k}}.
$$

For $k=o(n)$, it is known that $\log{n \choose k}=(1+o(1))k\log(n/k)$, so in this regime, we get
$$
\mathbb{E}[Y\_k]\leq k\sqrt{2(1+o(1))\log(n/k)},
$$
which for $k=\log n$, say, is a bit better than the naive bound.

When $k=\alpha n$ for some constant $\alpha$, one instead has $\log{n \choose k}=(1+o(1))H(\alpha)n$, where $H(p)=-p\log p-(1-p)\log(1-p)$ is the entropy function. So in this regime, that would give
$$
\mathbb{E}[Y\_k]\leq n\sqrt{2(1+o(1))\alpha H(\alpha)}.
$$

**Lower bounds added for completeness:** for linear $k$, one can get decent linear lower bounds that degrade as $\alpha\to 0$ but is tight at $\alpha=1/2$. Let $\alpha<1/2$, then by the Chernoff bound,
$$
\Pr(X\_{\alpha n+1}\leq 0)\leq \exp\bigg(\frac{-(1/2-\alpha)^2n}{2}\bigg).
$$
It is known that for $i, the conditional distribution of $X\_{[i]}$ given $X\_{[j]}=x$ is the same as the unconditional distribution of $X\_{[i]}$ taken from a sample of size $j-1$ conditioned to be larger than $x$. As we are summing over all $i\leq \alpha n$ and taking expectations, we find that
$$
\mathbb{E}[\sum\_{i=1}^{\alpha n} X\_{[i]}\vert X\_{\alpha n+1}\geq 0]\geq \mathbb{E}[\sum\_{i=1}^{\alpha n} Y\_i],
$$
where the $Y\_i$ are normal random variables conditioned to be larger than $0$, which are known to have expectation $\sqrt{2/\pi}$. We also find that
$$
\mathbb{E}[\sum\_{i=1}^{\alpha n} X\_{[i]}\vert X\_{\alpha n+1}\leq 0]\geq 0,
$$
as for each $x<0$, conditioning on $X\_{\alpha n}=x$, by the same reasoning we are now taking expectations over a sample of size $\alpha n$ normal random variables conditioned to be at least $x$, which by symmetry of the normal distribution is at least $0$ (formally, we are using that the sum over the whole sample makes the labelling of the order statistics irrelevant). We conclude that
$$
\mathbb{E}[\sum\_{i=1}^{\alpha n} X\_{[i]}]\geq \bigg(1-\exp\bigg(\frac{-(1/2-\alpha)^2n}{2}\bigg)\bigg)\alpha n\sqrt{2/\pi}=(1-o(1))\alpha n \sqrt{2/\pi}.
$$
This holds for all $\alpha<1/2$, and by monotonicity of the left hand side in $\alpha$ for $\alpha<1/2$ and taking limits, we can further conclude using the upper bound in the comments
$$
\mathbb{E}[\sum\_{i=1}^{n/2} X\_{[i]}]=(1-o(1))n\sqrt{1/(2\pi)}.
$$

Obviously similar lower bounds hold for $k=o(n)$ but these aren't super useful as they are of vastly different order than the upper bound.

**Numerical Simulations:** Numerical simulations suggest that these bounds are surprisingly decent in the two regimes mentioned in the post. Note that for any $k$, the function $f(x\_1,\ldots,x\_n)=\sum\_{i=1}^k x\_{[i]}$ is Lipschitz, so by Gaussian concentration, one expects simulations to roughly approximate the expectation. For instance, for $k=\log(n)$, here is a plot of the upper bound with that of simulation, with the top curve being the naive bound of $\sqrt{2}\log(n)^{3/2}$ and the lower curve the given bound:[![enter image description here](https://i.sstatic.net/UgeiE.png)](https://i.sstatic.net/UgeiE.png)

In the linear $k$ regime, for the few values I tried, the constant of the upper bounds seems to be off by a factor of at most $3$ (at $\alpha=1/2$, where we have computed the exact asymptotics). For instance, for $k=n/4$, the plot with the bound looks like: [![enter image description here](https://i.sstatic.net/LFyoT.png)](https://i.sstatic.net/LFyoT.png)

The upper bounds seem pretty good for small constant $\alpha$, while the lower bounds degrade. For instance, here is $\alpha=.001$:[![enter image description here](https://i.sstatic.net/b9GIz.png)](https://i.sstatic.net/b9GIz.png)

Here's one more plot (because I can't resist) with $k=\sqrt{n}$: [![enter image description here](https://i.sstatic.net/jSuWl.png)](https://i.sstatic.net/jSuWl.png)Hope this helps!

> **Comments:**
> **username_0**: Wow, these bounds are actually perfect for my application!! I really appreciate the graphs too showing that they're tight haha. Your strategy of bounding the sum directly, instead of each of the individual terms, is much smarter. Thank you!!  
> **username_3**: You're welcome! By the way, for the specific case of $k=n/2$, one has $\mathbb{E}[\sum_{i=1}^{n/2} X_{[i]}]=\frac{1}{2}\mathbb{E}[\sum_{i=1}^{n/2} X_{[i]}-\sum_{i=1}^{n/2} X_{[n-i]}]$, so by TI, $\mathbb{E}[\sum_{i=1}^{n/2} X_{[i]}]\leq \frac{1}{2}\mathbb{E}[\sum_{i=1}^n \vert X_{[i]}\vert]=n\sqrt{1/(2\pi)}$. Simulations suggests this is essentially exact; there's probably a way to get a lower bound for $k=\alpha n$, $\alpha<1/2$ of $(1-o(1))\alpha n\sqrt{2/\pi}$ (the intuition is the top $\alpha n$ will be positive w.h.p. and so should be at least the expected absolute value of a Gaussian).  
> **username_3**: @UthsavChitra in case you're interested, I've added a proof of the linear lower bound that is tight at $\alpha=1/2$. Hope this is helpful!  
> **username_4**: Note that using these bounds you can derive asymptotic bounds on $\mathbb{E} X_{[k]}$, since deterministically $kX_{[k]} \leq \sum_{i=1}^k X_{[k]}$. Thus $\mathbb{E} X_{[k]} \leq \tfrac{1}{k}\mathbb{E} Y_k \leq \sqrt{\tfrac{2}{k}\log\tfrac{n}{k}}$. For example, if $k = o(n)$ as above, this gives $\mathbb{E} X_{[k]} \leq  \sqrt{(2+o(1))\log \tfrac{n}{k}}$.  

---

