6
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ For continuous non-negative IIDRVs $X_n$ with arbitrary common CDF $F(x)$ we cannot say much better than $\mathbb{E}(M)=\int_0^\infty (1-F(x)^n)dx$, where $M=\max\{X_1,\dotsc, X_n\}$, as written in the second link. The answer by zjm covers the general case. $\endgroup$ Jul 27, 2019 at 2:56

3 Answers 3

8
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ This is really nice. Do you have a book or article reference for it? $\endgroup$
    – mbiron
    Jun 28 at 15:44
7
$\begingroup$

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

$\endgroup$
-2
$\begingroup$

It seems the idea generalizes. Say $E(max(X_1,X_2,...,X_n))=M \iff (M \geq X_1 ,M >x_2,...,M >X_n); M \in \mathbb R $ Then(By assumed independence of the $X_i$) Let $f_i$ be the pdf. of $X_i$ :$$ P(M \geq X_1 ,M >X_2,..., M>X_n)= P(M >X_1)P(M > X_2).....P(M >X_n) = (\int_{- \infty}^{M} f_idx_i)^n$$ and then $f_x= \frac {d}{dt}(F_x)= $ ( By chain rule) $$(d/dxF(x))n( \int_{-\infty}^{\infty}f_idx_i)^{n-1} $$ , so that the expected value is $$n\int_{-\infty}^{\infty} x \int_{x_j}^{\infty} f_idx_i $$

I don't see how this is linear on $E(X_i):=\int _{-\infty}^{\infty}x_if_idx_i$

$\endgroup$
6
  • $\begingroup$ Please do explain nwhat's wrong in my post, so I may learn something or show you may be wrong. $\endgroup$
    – MSIS
    Feb 4, 2022 at 21:51
  • $\begingroup$ I thought this was a place to exchange knowledge. I was wrong. $\endgroup$
    – MSIS
    Feb 18, 2022 at 23:39
  • $\begingroup$ There is a problem starting in the first equation of this answer. E(\max(X_1, X_2, ... , X_n)) = X_j does not quite make sense - the left side is a number, while the right side is a random variable (a function from a sample space to the real-numbers). $\endgroup$
    – ttb
    Mar 30 at 18:29
  • $\begingroup$ @ttb : yes, I meant the value assumed by X_j, not the RV itself. $\endgroup$
    – MSIS
    Mar 31 at 23:31
  • $\begingroup$ Thanks for chiming in rather than anonimously downvoting. $\endgroup$
    – MSIS
    Mar 31 at 23:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .