Maximum of independent, unit-variance Gaussians with non-zero means

Question

Suppose $X_1,\dots,X_n$ are independent Gaussians, where $X_k \sim N(\mu_k,1)$. I am interested in $$ Z \stackrel{\rm def}{=} \max_{1\leq k\leq n} X_k $$ and specifically on the asymptotics of $\mathbb{E}[Z]$ (as a function of $n$ and $(\mu_k)_k$), and the concentration around this expected value.

The case where all $\mu_i$'s are equal is of course well-understood (equivalent to all $X_i$'s being $N(0,1)$); but the proofs I know do not seem to generalize to yield anything usable.

As a maybe simpler case, what about having $\mu_1=\dots=\mu_{n-1}=0$ and $\mu_n \neq 0$? (where $\mu_n$ may or may not depend on $n$, depending on what one can prove; I am thinking of it as a small constant)

Following a comment below: even in the "simpler" case, what I would like is to understand the gap between the above and the standard "all means are zero" cases (even only for the expected value, setting aside the concentration around it). That will be in the second-order term (or even lower?) of the asymptotics, since the leading term should still be $\sqrt{2\log n}$ for constant $\mu_n$.

Answer 1

Concentration is easy: the max function is 1-Lipschitz w.r.t. $\ell_2$, so the standard sub-gaussian dimension-free inequality holds (see Vershynin's book, or Boucheron et al., or many others).

The expectation can be trickier, but one simplifying fact is that you can compute the CDF (and hence the density) exactly. Let's consider your simpler case. Let $F_0$ be the CDF of the $N(0,1)$ Gaussian and $F_1$ the CDF of the $N(\mu,1)$ Gaussian. Then $$ P(Z\le t) = \prod_{k=1}^n(X_k\le t)=F_0(t)^{n-1}F_1(t), $$ which is the CDF of $Z$. From here, you can compute the density and hence the expectation.

I know this answer is missing some details, which I presume others will fill in -- and if not, I'll try to come back to it later.

Answer 2

The revised problem asks for $\mathbb{E}[\max(X,\mu+Y)-\max(X,Y)]$, where $X$ is the maximum of $n$ iid copies of $Y$, and $Y$ is normal.

If we replace normal variables by Laplace variables (whose pdf is $e^{-|y|}/2$), then the analysis turns out nicely.

The cdf for $X$, at least when $x\ge 0$, is $$\left(1-\frac{e^{-x}}{2}\right)^n$$ This is well approximated by the extreme value distribution with cdf of $$\exp\left(\frac{-ne^{-x}}{2}\right)$$ which has mean $\gamma + \log(n/2)$.

Now if $f_X$ is the pdf for this approximation, and $f_Y$ is the pdf for $Y$, the desired expectation is $$\int_{-\infty}^\infty \int_{-\infty}^\infty \big(\!\max(x,\mu+y)-\max(x,y)\big)f_X(x) f_Y(y)\, dx\, dy$$

The region with $x<\mu$ has an integral bounded by $$\int_{-\infty}^\mu \mu f_X(x) dx = \mu e^{-n/2e^\mu}$$

The region with $x>\mu$ has an integral which can be computed exactly as $$\frac{e^\mu-1}{n}\left(1 - (1+n/2e^\mu)e^{-n/2e^\mu}\right)$$

Putting these together, we have $$\mathbb{E}[\max(X,\mu+Y)-\max(X,Y)] = \frac{e^\mu-1}{n}+k$$ with $|k| <(\mu+2)e^{-n/2e^{\mu}}$. Numerical experimentation with Laplace variables confirms that $(e^\mu-1)/n$ is a good approximation to the desired difference.

Answer 3

Here is an answer $-$ this time actually about normal variables $-$ to the revised problem about $\mathbb{E}[\max(X,\mu+Y)-\max(X,Y)]$, where $X$ is the maximum of $n$ iid copies of $Y$, and $Y$ is normal. We use $\phi$ and $\Phi$ for the normal pdf and cdf.

The desired expectation is $$\mathbb{E}_X\left[ \int_{-\infty}^\infty \big(\!\max(x,\mu+y)-\max(x,y)\big) \phi(y)\, dy\right]$$ We break this into expectations of three integrals: a bottom region, middle region, and top region divided by $y=x-\mu$ and $y=x$.

The bottom region with $y<x-\mu$ has integral and expectation 0.

The top region with $y>x$ has expectation $$\mathbb{E}_X\left[\int_x^\infty \mu\, \phi(y)\, dy\right] = \frac{\mu}{n+1}$$ which is calculated using the cdf for $X$ of $\Phi(x)^n$. This expectation is negligible by comparison with the middle region for sufficiently large $n$.

The middle region with $x-\mu<y<x$ is therefore our focus; it has integral of $$\mathbb{E}_X\left[ \int_{x-\mu}^x \big(\mu+y-x\big) \phi(y)\, dy\right] = \mathbb{E}_X\left[\big((\mu - x)\Phi(y) - \phi(y)\big)\Big|_{x-\mu}^x\right]$$

Let $g(\mu,x)$ be the expression inside the expectation. According to Mathematica, $g(\mu,x)$ satisfies $$\lim_{x\to\infty}\frac{g(\mu,m_n)}{\phi(x-\mu)/x^2}=1.$$

So now we approximate $\mathbb{E}_X[g(\mu,x)]$ in three ways: first as $g(\mu,\mathbb{E}[X])$, then using the above approximation for $g$, and then using the estimate for the mean of $X$ as $$\mathbb{E}[X]\sim\sqrt{\log\frac{n^2}{4\pi\log n}}+\frac{\gamma}{\sqrt{2\log n}}$$ (One source for this formula is section 9.3 of Herbert David's Order Statistics; the $\gamma$ is the Euler-Mascheroni constant.)

So our final estimate for the overall expectation is $$\frac{\phi(\mathbb{E}[X]-\mu)}{\mathbb{E}[X]^2}$$ with the above expression for $\mathbb{E}[X]$. It may be possible to estimate the integral more accurately, but this seems to have the right order of magnitude, and the expression is odd enough to be worth writing down.

For the values of $\mu=1/2$ or $\mu=1$ and $n=300$ or $n=1000$, testing shows that this expression is accurate to within a factor of $2$.