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)$?

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 ?

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.

- ServerfaultXchanger
- SuperuserXchanger
- UbuntuXchanger
- WebappsXchanger
- WebmastersXchanger
- ProgrammersXchanger
- DbaXchanger
- DrupalXchanger
- WordpressXchanger
- MagentoXchanger
- JoomlaXchanger
- AndroidXchanger
- AppleXchanger
- GameXchanger
- GamingXchanger
- BlenderXchanger
- UxXchanger
- CookingXchanger
- PhotoXchanger
- StatsXchanger
- MathXchanger
- DiyXchanger
- GisXchanger
- TexXchanger
- MetaXchanger
- ElectronicsXchanger
- StackoverflowXchanger
- BitcoinXchanger
- EthereumXcanger