Order of $\mathbb{E}[ \max_i |x_i + z_i| - \max_i |z_i|]$

Question

Let $z_1, \dots, z_n$ be iid standard Normal, and let $x \in \mathbb{R}^n$. Put $\|u\|_\infty = \max_i |u_i|$.

Define $$ F(x) = \mathbb{E}\Big[\|x + z\|_\infty - \|z\|_\infty\Big] $$ If $\|x\|_\infty \geq 2 \mathbb{E} \|z\|_\infty = \Theta(\sqrt{\log n})$, then we clearly have $F(x) = \Theta(\|x\|_\infty)$. In fact, we easily see: $$ \frac{1}{2}\|x\|_\infty \leq F(x) \leq \|x\|_\infty \quad \mbox{if} \quad \|x\|_\infty \geq 2 \mathbb{E} \|z\|_\infty. $$ Thus, the question is now what happens when $\|x\|_\infty \ll \mathbb{E} \|z\|_\infty$. In this case, can one develop a sharp, up to multiplicative constants independent of dimension, approximation to $F(x)$?

Answer 1

Since we know that $E|Z|_\infty\sim \sqrt{\log n}$, the first easy case is if $|x|_\infty=o( \sqrt{\log n})$. In that case, $E |x+z|_\infty \sim E|z|_\infty$ in the sense that the ratio goes to $1$ asymptotically. This follows from the bounds $$ |z|_\infty-|x|_\infty\leq |z+x|_\infty\leq |z|_\infty+|x|_\infty.$$ In particular, trivially $\Omega(|x|_\infty/n)\leq |F(x)|\leq|x|_\infty$, which can’t be improved (consider the case of all coordinates constant for the upper bound, and of $x$ possessing a single non-zero coordinate for the lower bound).

So the only interesting regime (which maybe you do not care about) is when $|x|_\infty\sim c\sqrt{\log n}$ where $c\in (0,\infty)$. In that case, $F(x)/E|z|_\infty$ depends on the empirical measure $n^{-1}\sum_{i=1}^n \delta_{x_i/\sqrt{\log n}}$: If it is close to a non-degenerate probability measure, say $\mu$, then the ratio may be non-zero asymptotically. One can write a reasonably accurate expression as function of $\mu$. On the other hand if $\mu=\delta_0$ then only the infinity norm of $x$ enters in the ratio, and only if it larger than $E|z|_\infty$.

If one wants more accurate bounds on $F$, one needs to make assumptions on the empirical measure of the entries of $x$, with appropriate scaling.