2
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ $X_{(k)}$ usually denotes the $k^{th}$-smallest coefficient, so it would help to standardize the notation. $\endgroup$
    – user44143
    Commented Dec 24, 2020 at 16:29
  • $\begingroup$ 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 :) $\endgroup$
    – dohmatob
    Commented Dec 24, 2020 at 16:40
  • $\begingroup$ Typo: There are reversed inequalities in the first and second line of anti-concentration. Please proofread this part $\endgroup$ Commented Dec 24, 2020 at 17:26
  • $\begingroup$ @YuvalPeres Indeed. Fixed. Thanks. $\endgroup$
    – dohmatob
    Commented Dec 24, 2020 at 20:06
  • $\begingroup$ 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? $\endgroup$
    – Clement C.
    Commented Dec 24, 2020 at 21:06

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – dohmatob
    Commented Dec 24, 2020 at 23:44
  • $\begingroup$ @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})$. $\endgroup$ Commented Dec 25, 2020 at 1:36
  • $\begingroup$ 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. $\endgroup$
    – dohmatob
    Commented Dec 25, 2020 at 12:12
  • $\begingroup$ @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$. $\endgroup$ Commented Dec 25, 2020 at 16:15
3
$\begingroup$

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/

$\endgroup$
1
  • $\begingroup$ Thanks. Upvoted. $\endgroup$
    – dohmatob
    Commented Dec 24, 2020 at 23:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.