Good concentration inequality for $\max_{i,j} X_j- X_i$ where $X_1,\ldots,X_n \overset{iid}{\sim} N(0,1)$.

Question

Let $n$ be a large positive integer and define $\Delta:\mathbb R^n \to \mathbb R$ by $\Delta(x) := \max_{i,j} x_j - x_i$. Let $X_1,\ldots,X_n$ be iid from $N(0,1)$

Question. What is a good concentration inequality for $\Delta(X)$ ?

Observation

Let $x'$ and $x$ be vectors in $\mathbb R^n$ which only dependend on their $k$th coordinate. Then

$$ \begin{split} |\Delta(x') - \Delta(x)| &= |(|\max_{i,j} x'_j-x'_i|) - (|\max_{i,j} x'_j-x'_i)| \le \max_{i,j} \left||x'_j-x'_i|-|x_j-x_i|\right|\\ &\le \max_{i,j}|(x_j'-x_j)-(x_i'-x_i)| = \begin{cases}0, &\mbox{ if }k \not\in\{i,j\},\\ |x'_i-x_i|,&\mbox{ if }i = k \ne j,\\ |x'_j-x_j|,&\mbox{ if }j = k \ne i.\end{cases} \end{split} $$ Therefore $|\Delta(x') - \Delta(x)| \le |x'_k-x_k|$, and so $\Delta$ is $1$-Lipschitz in every coordinate and it follows from Corollary 2.1 of this monograph that

$$ \mathbb P(|\Delta(X) - \mathbb E[\Delta(X)]| \ge t) \le 2e^{-t^2/(2n)}. $$

I hope for an inequality with a better dependence on the dimension $n$.

Answer 1

The functions $v \mapsto \max_i v_i$ and $v \mapsto \min_i v_i$ are $1$-Lipschitz with respect to the Euclidean metric. Indeed, take any $x,y \in \mathbb{R}^n.$ In the case that $\max_i x_i > \max_j y_j,$ $$ | \max_i x_i - \max_j y_j| = \max_i x_i - \max_j y_j \le \max_i (x_i - y_i) \le \max_i |x_i - y_i| \le \|x-y\|,$$ and the same argument reversed works if $\max_i y_i > \max_i x_i.$ The claim follows for $\min$ because $\min_i v_i = - \max_i (-v_i).$

The upshot of this is that $\max_{i \neq j} x_i -x_j = \max_i x_i - \min_j x_j $ is $2$-Lipschitz with respect to the Euclidean metric. Now using theorem 2.2 from the notes linked to in the question gives a concentration radius independent of $n$.

Answer 2

A quick and dirty way to get a dimension-independent bound without using the nice observation of stochasticboy321:

$$\begin{align} \mathbb{P}\{ |\max_{i,j} (X_i- X_j) &- \mathbb{E}\max_{i,j} (X_i- X_j) |\geq t \}\\ &= \mathbb{P}\{ |(\max_i X_i- \mathbb{E} \max_{i} X_i)- (\min_j X_j - \mathbb{E} \min_{i} X_i)| \geq t \} \\ &\leq\mathbb{P}\{ |\max_i X_i- \mathbb{E} \max_{i} X_i|\geq t/2 \} + \mathbb{P}\{ |\min_i X_i- \mathbb{E} \min_{i} X_i|\geq t/2 \} \\ &=2\mathbb{P}\{ |\max_i X_i- \mathbb{E} \max_{i} X_i|\geq t/2 \}\\ \end{align}$$ and we have a dimension-independent bound for the concentration of the max of $n$ i.i.d. Gaussians, so $$\begin{align} \mathbb{P}\{ |\max_{i,j} (X_i- X_j) - \mathbb{E}\max_{i,j} (X_i- X_j) |\geq t \} &\leq Ce^{-C't^2} \end{align}$$ for some explicit constants $C,C'>0$ I don't recall at the moment.