# Concentration and anti-concentration of gap between largest and second largest value in Gaussian iid sample

Let $$n \ge 3$$ be an integer and let $$X=(X_1,\ldots,X_n)$$ be random vector with iid coordinates from $$N(0,1)$$. For $$1 \le k \le n$$, let $$X_{(k)}$$ be the value of the $$k$$th largest coordinate of $$X$$.

Question. What are good (anti-)concentration inequalities for $$X_{(1)} - X_{(2)}$$ ?

References welcome!

## A crude concentration inequality

Note that $$X_{(1)} - X_{(2)} \le \Delta := \max_{i,j} X_i - X_j = X_{(1)} - X_{(n)}$$. Moreover, $$E[\Delta] \le 2\max_i X_i \le 2\sqrt{2\log n},$$ and so using the result from this post, we have

$$\begin{split} P(X_{(1)} - X_{(2)} &\ge 2\sqrt{2 \log n} + t) \le P(\Delta \ge E[\Delta] + t)\\ &\le 2 P(|\max_i X_i - \mathbb E[\max_i X_i]| \ge t/2) \le 2e^{-t^2/8}. \end{split}$$

I wonder if my above somewhat naive bounds can be improved.

## Edit: $$P(X_{(1)} - X_{(2)} > t)$$ when $$n \ge 3$$ and $$t \ge 4 \sqrt{2 \log n}$$

Inspired by the posted answers and the above Borell-TIS inequality, one may compute $$\begin{split} P(X_{(1)} - X_{(2)} > t) &\le P(X_{(1)} > E X_{(1)} + t/2) + P(X_{(2)} < E X_{(1)} - t/2)\\ &\le e^{-t^2/8} + P(X_{(2)} < \sqrt{2 \log n} - t/2)\\ &= e^{-t^2/8} + P(X_{(2)} \le -t/4), \text{ if }t \ge 4\sqrt{2 \log n}\\ &= e^{-t^2/8} + (\Phi(-t/2))^n + n(1 - \Phi(-t/4))\cdot (\Phi(-t/4))^{n-1}\\ &=e^{-t^2/8} + (\Phi^c(t/4))^n + n\Phi(-t/4)\cdot (\Phi^c(t/4))^{n-1} \\ &\le e^{-t^2/8} + (\Phi(t/4)+n\Phi(-t/4))\cdot e^{-(n-1)t^2/16}\\ &\le e^{-t^2/8}+(1+n/2)e^{-(n-1)t^2/16} \le 2e^{-t^2/8}, \text{ if }n \ge 3. \end{split}$$

We deduce that

If $$n \ge 3$$ and $$t \ge 4\sqrt{2 \log n}$$, then we have the concentration inequality $$P(X_{(1)} - X_{(2)} \ge t) \le 2e^{-Ct^2}.$$

• $X_{(k)}$ usually denotes the $k^{th}$-smallest coefficient, so it would help to standardize the notation.
– user44143
Commented Dec 24, 2020 at 16:29
• Not sure about that; I've seen the reverse notation (i.e the one I'm using) in quite a few standard places. For example arxiv.org/pdf/1207.7209.pdf. Anyways, I gave a self-contained explicit definition of 𝑋(𝑘), thus there should be not confusion whatsoever :) Commented Dec 24, 2020 at 16:40
• Typo: There are reversed inequalities in the first and second line of anti-concentration. Please proofread this part Commented Dec 24, 2020 at 17:26
• @YuvalPeres Indeed. Fixed. Thanks. Commented Dec 24, 2020 at 20:06
• Isn't the first line of the last part still in the wrong direction? I don't see why $X(1)−X(2) \geq X(1)−X(n)$, shouldn't it be the opposite? Commented Dec 24, 2020 at 21:06

Let us show that, after proper rescaling, $$X_{(1)}-X_{(2)}$$ has an asymptotically exponential distribution.

Let $$Y_n:=X_{(1)}$$ and $$Y_{n-1}:=X_{(2)}$$. By the known formula for the joint pdf of two order statistics, the joint pdf of $$Y_{n-1}$$ and $$Y_n$$ is given by $$$$f_{n-1,n}(y_{n-1},y_n)=n(n-1)F(y_{n-1})^{n-2}f(y_{n-1})f(y_n)\,1(y_{n-1} where $$F$$ and $$f$$ denote, respectively, the cdf and pdf of $$N(0,1)$$. Hence, for any fixed real $$c>0$$, $$$$x:=\frac c{\sqrt{2\ln n}},$$$$ $$$$l:=\ln n,$$$$ and all large enough $$n$$ we have $$$$P(X_{(1)}-X_{(2)}>x)=P(V>x)=n(n-1)J,$$$$ where \begin{align*} J&:=\int_{-\infty}^\infty dw\,F(w)^{n-2}f(w)\int_x^\infty dv\, f(v+w) \\ & =\int_{-\infty}^\infty dw\,F(w)^{n-2}f(w)G(x+w) \\ & =\int_0^1 du\,h(u)=J_2+O(J_1+J_3), \end{align*} $$$$h(u):=u^{n-2}G(x+Q(u)),\quad G:=1-F,\quad Q:=F^{-1},$$$$ $$$$J_1:=\int_0^{1-l^2/n}du\,u^{n-2}\le(1-l^2/n)^{n-2}\le\exp\Big\{-\frac{n-2}n\,l^2\Big\} =o(1/n^2)$$$$ (as $$n\to\infty$$), $$$$J_3:=\int_{1-1/(nl)}^1du\,u^{n-2}G(Q(u))=\int_{1-1/(nl)}^1du\,u^{n-2}(1-u) \le\frac1{nl}\,\int_0^1 du\,u^{n-2}=o(1/n^2),$$$$ and $$$$J_2:=\int_{1-l^2/n}^{1-1/(nl)} du\,u^{n-2}G(x+Q(u)).$$$$

For $$u\in[1-l^2/n,1-1/(nl)]$$ and $$w:=Q(u)$$, we have $$u\uparrow1$$ and hence $$w\to\infty$$; therefore and because $$x\downarrow0$$, again for $$u\in[1-l^2/n,1-1/(nl)]$$, $$$$G(x+Q(u))=G(x+w)\sim\frac{f(x+w)}{x+w}\sim\frac{f(w)}{w}\,e^{-xw} \sim G(w)\,e^{-xw}=(1-u)e^{-xw},$$$$ and also $$$$|\ln(1-u)|\sim\ln n$$$$ and $$$$w=Q(u)\iff u=F(w)\iff 1-u=G(w)\implies w\sim\sqrt{2|\ln(1-u)|},$$$$ since $$G(w)=\exp\{-w^2/(2+o(1))\}$$ as $$w\to\infty$$. It follows that \begin{align*} J_2&\sim\int_{1-l^2/n}^{1-1/(nl)} du\,u^{n-2}(1-u)e^{-xQ(u)} \\ &=\int_{1-l^2/n}^{1-1/(nl)} du\,u^{n-2}(1-u)\exp\Big\{-\frac c{\sqrt{2\ln n}}\,\sqrt{2\ln n}\Big\} \\ &=\int_{1-l^2/n}^{1-1/(nl)} du\,u^{n-2}(1-u) e^{-c} \\ &=\int_0^1 du\,u^{n-2}(1-u) e^{-c}+O(J_1+J_3) \\ &=\frac{e^{-c}}{n(n-1)}+O(J_1+J_3)\sim\frac{e^{-c}}{n(n-1)}. \end{align*}

Collecting pieces, we conclude that for any fixed real $$c>0$$ $$$$P\Big(X_{(1)}-X_{(2)}>\frac c{\sqrt{2\ln n}}\Big)\to e^{-c},$$$$ so that indeed, after proper rescaling, $$X_{(1)}-X_{(2)}$$ has an asymptotically exponential distribution.

• Thanks. Upvoted. In an edit to my question, I've manage to get the non-asymptotic upper-bound $P(X_{(1)} - X_{(2)} \ge t) \le 2e^{-Ct^2}$ for all $n \ge 3$ and $t \ge 4\sqrt{2 \log n}$. Donno if (1) my bound is trivial, or (2) one can also get anti-concentration (i.e a lower-bound) under these conditions. Thanks in advance for any insights. Commented Dec 24, 2020 at 23:44
• @dohmatob : The asymptotic estimate tells us that, at least for large $n$, $X_{(1)}-X_{(2)}$ is small in probability ($\asymp_P\,1/\sqrt{\ln n}$) -- as it should be: imagine all the values of the order statistics put on the real line; they will naturally tend to be getting denser as $n$ increases. On the other hand, your bound only gives $O_P(\sqrt{\ln n})$. Commented Dec 25, 2020 at 1:36
• Sure. Your analysis of the asymptotic regime is very informative indeed. The thing is, the non-asymptotic / small $n$ regime (think of $n < 10$) is also very important to me. Commented Dec 25, 2020 at 12:12
• @dohmatob : I think it should not hard to extract a good nonasymptotic bound from this reasoning. It won't probably be as pretty, but I think it will still imply the essential property that $X_{(1)}-X_{(2)}$ is small for large $n$. Commented Dec 25, 2020 at 16:15

Let $$\Phi(r)=P(X_1>r)$$. Then for $$s we have $$P(X_{(1)} and from this one can obtain the exact distribution of $$X_{(1)}- X_{(2)}$$. For a simple but still suboptimal upper bound: $$\Psi(2t):=P(X_{(1)}- X_{(2)}>2t )\le P(X_{(1)}>\sqrt{2 \log n}+t)+P(X_{(2)}<\sqrt{2 \log n}-t)$$ so $$\Psi(2t) \le 1-[\Phi(\sqrt{2 \log n}+t)]^n + [\Phi(\sqrt{2 \log n}-t)]^{n}+n [ 1-\Phi(\sqrt{2 \log n}-t)] [\Phi(\sqrt{2 \log n}-t)]^{n-1} .$$ Now one can plug in the tail bounds for $$\Phi$$, see e.g. https://www.johndcook.com/blog/norm-dist-bounds/

• Thanks. Upvoted. Commented Dec 24, 2020 at 23:42