3
$\begingroup$

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

$\endgroup$
  • 1
    $\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 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 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 at 22:03
0
$\begingroup$

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.

$\endgroup$
  • $\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 at 21:01
  • $\begingroup$ Yes. But doesn't erf have nice tractable approximations? $\endgroup$ – Aryeh Kontorovich Nov 27 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 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 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 at 22:05

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.