Expectation of maximum of n i.i.d random variables

Question

I have $n$ i.i.d. random variables, $X_1,..., X_n$ which follow some arbitrary distribution. Based on experiments in Python with various distributions, it seems that $\mathbb{E}(\max(X_1,...,X_n))$ is a linear (or seemingly close to linear) function of $\mathbb{E}(X_i)$. It is indeed linear for some examples where it is possible to get a closed form solution for $\mathbb{E}(\max(X_1,...,X_n))$ or a good approximation.

Expected value of $\max\{X_1,\ldots,X_n\}$ where $X_i$ are iid uniform.

Expectation of the maximum of i.i.d. geometric random variables

I wonder if this is the case more generally? Is there some way to prove it?

Answer 1

This is question is related to something called order statistics in probability theory. You can read more about them here. For $n$ iid variables $X_1, …, X_n$ with cumulative density function $F$ and density function $f$, the density function of the maximum is:

$$f_{max}(x) = nf(x)F(x)^{n-1}$$

Then this implies the expected value would be:

$$E[X_{max}] = \int_{-\infty}^{\infty} nxf(x)F(x)^{n-1} dx$$

I don't see any linear relationship here in general between $E[X_{max}]$ and $E[X]$

Answer 2

A general technique to get a bound that is often pretty decent is to use the MGF if you have it: for all $t\geq 0$: \begin{align} \exp(t\mathbb{E}[\max_i X_i])&\leq \mathbb{E}[\exp(t\max_i X_i)]\\ &\leq\mathbb{E}[\sum_{i=1}^n \exp(t X_i)] \\ &= n\mathbb{E}[\exp(t X)], \end{align} so \begin{equation} \mathbb{E}[\max_i X_i]\leq \frac{\log(n\mathbb{E}[\exp(tX)])}{t}. \end{equation} You can then optimize in $t\geq 0$ to get a decent upper bound. For instance, doing this with Gaussians with variance $\sigma^2$ would show $\mathbb{E}[\max_i X_i]\leq \sigma\sqrt{2\log n}$, which turns out to be right up to a constant.

Answer 3

Note that it is not crucial to choose the exponential function in J.G.'s answer. The idea indeed generalizes.

Indeed let $f(x) = |x|^q$, with $q \geq 1$ arbitrary, and let $M = \max\{X_1, \dotsc, X_N\}$. By Jensen's inequality, it holds that $$ f \left( \mathbb E \bigl[ M \bigr] \right) \leq \mathbb E \Bigl[ f\bigl(M \bigr) \Bigr] \leq \mathbb E \left[ \sum_{n=1}^{N} f\bigl( X_n \bigr) \right] = N \mathbb E \Bigl[ f\bigl( X_1 \bigr) \Bigr], $$ and so we obtain, noting that the inverse function $f^{-1}$ is increasing, $$ \mathbb E \bigl[ M \bigr] = f^{-1} \Bigl( f \left(\mathbb E \bigl[ M \bigr]\right) \Bigr) \leq f^{-1} \left(N \mathbb E \Bigl[ f\bigl( X_1 \bigr) \Bigr]\right) = N^{\frac{1}{q}} \left(\mathbb E \Bigl[ |X_1|^{q} \Bigr] \right)^{\frac{1}{q}} $$ Thus, even if $X_1$ does not have an exponential moment, a good bound can be obtained. Furthermore, notice that the more moments $X_1$ has, the better the dependence on $N$ in the bound on $\mathbb E[M]$ is.

Note that, as in J.G.'s answer, this approach does not require independence, only that the random variables are identically distributed.