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 \|z\|_\infty \geq 2 \mathbb{E} \|g\|_\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)$?
