[Math] Expectation of maximum of n i.i.d random variables

expected valueprobabilityprobability distributions

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?

Best Answer

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.

Related Solutions

[Math] Range of i.i.d. normal random variables

I think this paper may help. Someone may have expanded on this in the past 50 years, but it seems like a good place to start:

Tables of range and studentized range, HL Harter

http://www.jstor.org/stable/2237810

Edit: In case you're interested and familiar with R, here is some code that seems to work (for me, at least):

r<-function(x,n){
inner.int<-function(s){
exp(-s^2)*(pnorm(s+x/2)-pnorm(s-x/2))^(n-2)
}
return(n*(n-1)*exp(-x^2/4)/(2*pi)*integrate(inner.int,-Inf,Inf)$value)
}

[Math] Expectation of Minimum of $n$ i.i.d. uniform random variables.

To calculate the expected value, we're going to need the density function for $Y$. To get that, we're going to need the distribution function for $Y$. Let's start there.

By definition, $F(y) = P(Y \leq y) = 1 - P(Y > y) = 1 - P(\text{min}(X_1, \ldots, X_n) > y)$. Of course, $\text{min}(X_1, \ldots X_n) > y$ exactly when $X_i > y$ for all $i$. Since these variables are i.i.d., we have $F(y) = 1 - P(X_1 > y)P(X_2>y)\ldots P(X_n>y) = 1 - P(X_1 > y)^n$. Assuming the $X_i$ are uniformly distributed on $(a, b)$, this yields $$F(y) = \left\{ \begin{array}{ll} 1 - \left(\frac{b-y}{b-a}\right)^n & : y \in (a, b)\\ 0 & : y < a\\ 1 & : y > b \end{array} \right.$$ We take the derivative to get the density function. $$f(y) = \left\{ \begin{array}{ll} \frac{n}{b-a} \left(\frac{b-y}{b-a}\right)^{n-1} & : y \in (a, b)\\ 0 & : \text{otherwise} \end{array} \right.$$ Now $E(Y) = \int_{-\infty}^{\infty} y f(y) dy$. The integral is straightforward; I'll leave the details to you. I calculate $E(Y) = \frac{b+na}{n+1}$.

Best Answer

Related Solutions

[Math] Range of i.i.d. normal random variables

[Math] Expectation of Minimum of $n$ i.i.d. uniform random variables.

Related Question