18
$\begingroup$

I'm looking for bounds on the variance of the maximum of a set of random variables. In other words, I'm looking for closed-form formulas for $B$, such that $$ \mbox{Var}(\max_i X_i) \leq B \enspace, $$ where $X = \{ X_1, \ldots, X_M \}$ is a fixed set of $M$ random variables with finite means $\mu_1, \ldots, \mu_M$ and variances $\sigma_1^2, \ldots, \sigma_M^2$.

I can deduce that $$ \mbox{Var}(\max_i X_i) \leq \sum_i \sigma_i^2 \enspace, $$ but this bound seems very loose. A numerical test seems to indicate that $B = \max_i \sigma_i^2$ might be a possibility, but I have not been able to prove this. Any help is appreciated.

Improve this question
$\endgroup$
4
  • 4
    $\begingroup$ (Do you want to assume the $X_i$ are independent?) The conjecture is plausible but appears to be false. For instance, do some trials where the $X_i$ are iid with CDF $1-x^{1-s}$, $1\le x\le \infty$, $s\gt 3$. The variance of their maximum, relative to their common variance, increases without bound as $M$ grows. $\endgroup$
    – whuber ♦
    Commented Sep 23, 2011 at 15:38
  • $\begingroup$ @whuber Thanks, that explains why I wasn't able to prove that conjecture :) I'm indeed interested in the case where the $X_i$ are independent. Just to clarify, I'm mostly interested in general bounds that use only the first two moments. I'm not sure whether sharper general bounds even exist than the common variance. $\endgroup$
    – Peter
    Commented Sep 23, 2011 at 17:03
  • 1
    $\begingroup$ I should point out that your sum bound (assuming it is correct--it would be nice to see a sketch of the proof) is tight. For instance, let $X_2,\ldots,X_M$ be supported on the interval $[-\infty, a]$ with variances not exceeding $\varepsilon^2$ and let $X_1$ be supported on $[a,\infty]$. Then $\max_i{X_i}=X_1$ a.s., with variance $\sigma_1^2\le\sigma_1^2+(M-1)\varepsilon^2$, but the inequality can be tightened as much as you like by shrinking $\varepsilon^2$. $\endgroup$
    – whuber ♦
    Commented Sep 23, 2011 at 17:57
  • 1
    $\begingroup$ For i.i.d. data, extreme value theory provides the classes of distributions to which the sample maximum converges, with certain conditions on the tails of the original distributions giving different classes of the asymptotic distributions. So I doubt that you will be able to derive a good bound based on the two moments only, although I am only tangentially familiar with the theory. $\endgroup$
    – StasK
    Commented Sep 23, 2011 at 18:28

2 Answers 2

Reset to default
18
$\begingroup$

For any $n$ random variables $X_i$ , the best general bound is $\newcommand{\Var}{\mathrm{Var}}\Var(\max X_i) \le \sum_i \Var(X_i)$ as stated in the original question. Here is a proof sketch: If X,Y are IID then $E[(X-Y)^2] =2\Var(X)$. Given a vector of possibly dependent variables $(X_1,\ldots ,X_n)$, let $(Y_1,\ldots ,Y_n)$ be an independent vector with the same joint distribution. For any $r>0$, we have by the union bound that $P[ |\max_i X_i-\max_i Y_i|^2 >r] \le \sum_i P[ | X_i-Y_i|^2 >r]$, and integrating this $dr$ from $0$ to $\infty$ yields the claimed inequality.

If $X_i$ are IID indicators of events of probability $\epsilon$, then $\max X_i$ is an indicator of an event of probability $n\epsilon+O(n^2 \epsilon^2)$. Fixing $n$ and letting $\epsilon$ tend to zero, we get $\Var(X_i)=\epsilon-\epsilon^2$ and $\Var(\max_i X_i)= n\epsilon +O(n^2\epsilon^2)$.

Improve this answer
$\endgroup$
0
7
$\begingroup$

A question on MathOverflow is related to this question.

For IID random variables, the $k$th highest is called an order statistic.

Even for IID Bernoulli random variables, the variance of any order statistic other than the median can be greater than the variance of the population. For example, if $X_i$ is $1$ with probability $1/10$ and $0$ with probability $9/10$ and $M=10$, then the maximum is $1$ with probability $\approx 1- 1/e$, so the variance of the population is $0.09$ while the variance of the maximum is about $0.23$.

Here are two papers on the variances of order statistics:

Yang, H. (1982) "On the variances of median and some other order statistics." Bull. Inst. Math. Acad. Sinica, 10(2) pp. 197-204

Papadatos, N. (1995) "Maximum variance of order statistics." Ann. Inst. Statist. Math., 47(1) pp. 185-193

I believe the upper bound on the variance of the maximum in the second paper is $M\sigma^2$. They point out that equality can't occur, but any lower value can occur for IID Bernoulli random variables.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.