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

Question

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}. $$

Answer 1

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 \begin{equation} 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}<y_n), \end{equation} where $F$ and $f$ denote, respectively, the cdf and pdf of $N(0,1)$. Hence, for any fixed real $c>0$, \begin{equation} x:=\frac c{\sqrt{2\ln n}}, \end{equation} \begin{equation} l:=\ln n, \end{equation} and all large enough $n$ we have \begin{equation} P(X_{(1)}-X_{(2)}>x)=P(V>x)=n(n-1)J, \end{equation} 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*} \begin{equation} h(u):=u^{n-2}G(x+Q(u)),\quad G:=1-F,\quad Q:=F^{-1}, \end{equation} \begin{equation} 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) \end{equation} (as $n\to\infty$), \begin{equation} 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), \end{equation} and \begin{equation} J_2:=\int_{1-l^2/n}^{1-1/(nl)} du\,u^{n-2}G(x+Q(u)). \end{equation}

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)]$, \begin{equation} 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}, \end{equation} and also \begin{equation} |\ln(1-u)|\sim\ln n \end{equation} and \begin{equation} w=Q(u)\iff u=F(w)\iff 1-u=G(w)\implies w\sim\sqrt{2|\ln(1-u)|}, \end{equation} 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$ \begin{equation} P\Big(X_{(1)}-X_{(2)}>\frac c{\sqrt{2\ln n}}\Big)\to e^{-c}, \end{equation} so that indeed, after proper rescaling, $X_{(1)}-X_{(2)}$ has an asymptotically exponential distribution.

Answer 2

Let $\Phi(r)=P(X_1>r)$. Then for $s<t$ we have $$P(X_{(1)}<t, \; X_{(2)}<s)=\Phi(s)^n+n(\Phi(t)-\Phi(s))\cdot \Phi(s)^{n-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/