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

  • 2
    $\begingroup$ I think this will depend a lot on the asymptotics of the $\mu_k$'s. In your simpler case, do you assume $\mu_n=O(1)$? Then it should be easy to see that the effect of $\mu_n$ is negligible. $\endgroup$ – Iosif Pinelis Nov 27 '19 at 19:25
  • $\begingroup$ @IosifPinelis I should be more explicit: yes, $\mu_n$ is $O(1)$, but I am interested in the second-order term of the asymptotics then. (My motivation, besides the question itself, is a testing one: what is the separation between all-standard and the non-zero-mean cases) $\endgroup$ – Clement C. Nov 27 '19 at 19:33
  • $\begingroup$ What do you mean by "second order term"? the maximum will be, as long as $\mu_n=O(1)$, $\sqrt{2\log n}-c\log\log n/\sqrt{\log n}+O(1/\sqrt{\log n})$ for $c$ a constant that I am too lazy to compute. In your general case, you can compute the right asymptotics from the asymptotics of $\sum P(X_i>x_n)$ and match $x_n$ so that the sum is of order $1$. $\endgroup$ – ofer zeitouni Dec 2 '19 at 22:03

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.

  • $\begingroup$ It doesn't look so easy to get a nice expectation from that CDF; the result is an integral of $\erf$'s that probably can't simplified much. $\endgroup$ – Matt F. Nov 27 '19 at 21:01
  • $\begingroup$ Yes. But doesn't erf have nice tractable approximations? $\endgroup$ – Aryeh Kontorovich Nov 27 '19 at 21:04
  • $\begingroup$ This may be useful to compute it numerically (given specific values), à la Ross (2003); not clear to me how to proceed to get the sought asymptotics as a function of $n$ and $\mu_n$, even in the simple case... is it obvious? $\endgroup$ – Clement C. Dec 2 '19 at 18:01
  • 1
    $\begingroup$ Whatever was obvious to me is already written in my answer. I figured working out the asymptotics was nontrivial but doable and was betting with 75% confidence that someone would do it by now. I’d love to give it a serious shot myself if I had time, which won’t be for a few weeks. $\endgroup$ – Aryeh Kontorovich Dec 2 '19 at 19:58
  • 1
    $\begingroup$ The Lip concentration gives you no better than Borell's inequality: the variance of the max is bounded by O(1). In truth, it is much smaller, unless $\mu_n$ is large... $\endgroup$ – ofer zeitouni Dec 2 '19 at 22:05

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.


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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