Variance of maximum of Gaussian random variables

by Devil   Last Updated May 25, 2019 00:19 AM

Given random variables $X_1,X_2, \cdots, X_n$ sampled iid from $\sim \mathcal{N}(0, \sigma^2)$, define $$Z = \max_{i \in \{1,2,\cdots, n \}} X_i$$

We have that $\mathbb{E}[Z] \le \sigma \sqrt{2 \log n}$. I was wondering if there are any upper/lower bounds on $\text{Var}(Z)$?



Answers 2


You can obtain upper bound by applying Talagrand inequality : look at Chatterjee's book (Superconcentration phenomenon for instance) .

It tells you that ${\rm Var}(f)\leq C\sum_{i=1}^n\frac{\|\partial_if\|_2^2}{1+\log( \|\partial_i f||_2/\|\partial_i f\|_1)}$.

For the maximum, you get $\partial_if=1_{X_i=max}$, then by integrating with respect to the Gaussian measure on $\mathbb{R}^n$ you get $\|\partial_if\|_2^2=\|\partial_if\|_1=\frac{1}{n}$ by symmetry. (Here I choose all my rv iid with variance one).

This the true order of the variance : since you have some upper bound on the expectation of the maximum, this article of Eldan-Ding Zhai (On Multiple peaks and moderate deviation of Gaussian supremum) tells you that
${\rm Var}(\max X_i)\geq C/(1+\mathbb{E}[\max X_i])^2$

It is also possible to obtain sharp concentration inequality reflecting these bound on the variance : you can look at http://www.wisdom.weizmann.ac.il/mathusers/gideon/papers/ranDv.pdf or, for more general gaussian process, at my paper https://perso.math.univ-toulouse.fr/ktanguy/files/2012/04/Article-3-brouillon.pdf

In full generality it is rather hard to find the right order of magnitude of the variance of a Gaussien supremum since the tools from concentration theory are always suboptimal for the maximum function.

Why do you need these kinds of estimates if I may ask ?

Tanguy Kevin
Tanguy Kevin
January 02, 2017 11:21 AM

More generally, the expectation and variance of the range depends on how fat the tail of your distribution is. For the variance, it is $O(n^{-B})$ where $B$ depends on your distribution ($B = 2$ for uniform, $B = 1$ for Gaussian, and $B = 0$ for exponential.) See here. The table below shows the order of magnitude for the range.

enter image description here

Vincent Granville
Vincent Granville
May 24, 2019 23:33 PM

Related Questions



Improving variable estimates by reducing uncertainty

Updated August 21, 2017 07:19 AM


I need help to show that $E(\sum x)=\sum E(x)$

Updated August 14, 2016 08:08 AM