6
$\begingroup$

Let $(X_i)_{i\leq n}$ be random variables, which may be dependent. Is it true that \begin{align*} \text{Var}(\max X_i) \leq \sum_{i=1}^n \text{Var}(X_i). \end{align*}

I have tried integrating the tail probability, \begin{align*} \text{Var}(\max X_i) &= E\left( \max X_i - E \max X_i \right)^2 \\ &= \int_0^\infty P\left((\max X_i - E \max X_j)^2 > t \right) dt \\ &\leq \int_0^\infty P\left(\bigcup_{i=1}^n \{(X_i - E \max X_j)^2 > t\} \right) dt \\ &\leq \sum_{i=1}^n \int_0^\infty P((X_i-E \max X_j)^2 > t) dt \\ &= \sum_{i=1}^n E (X_i - E \max X_j)^2, \end{align*} but this is not quite what we need. It seems that if the $X_i$ are independent, then I shouldn't have lost anything in the union bound. Does anyone know of a counter example or a proof?

$\endgroup$
4
$\begingroup$

Your solution looks good. One can get the same bound using the Efron-Stein inequality. Using the notation in your answer, \begin{align} \operatorname{Var}(\max_i X_i) &\le \frac{1}{2}\sum_{k=1}^n E[(\max_i X_i - \max\{X_1,\ldots, X_{k-1}, Y_k, X_{k+1}, \ldots, X_n\})^2] \\ &\le \frac{1}{2} \sum_{k=1}^n E[(X_k - Y_k)^2]. \end{align} To justify the last inequality, note that

  • if $\max_i X_i > \max\{X_1,\ldots, X_{k-1}, Y_k, X_{k+1}, \ldots, X_n\}$ then $k = i^*$ (where $X_{i^*} = \max_i X_i$) and thus $X_k = \max_i X_i > \max\{X_1,\ldots, X_{k-1}, Y_k, X_{k+1}, \ldots, X_n\} \ge Y_k$
  • if $\max_i X_i < \max\{X_1,\ldots, X_{k-1}, Y_k, X_{k+1}, \ldots, X_n\}$ then $Y_k = \max\{X_1,\ldots, X_{k-1}, Y_k, X_{k+1}, \ldots, X_n\} \ge \max_i X_i \ge X_k$.
| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

Here is the trick. Let $(Y_1,\dots,Y_n)$ be an independent copy. Then \begin{align*} 2\text{Var}(\max X_i) = E(\max X_i - \max Y_i)^2 = \int_0^\infty P((\max X_i - \max Y_i)^2>t)dt. \end{align*} If $X_{i^*} = \max X_i$ and $Y_{j^*} = \max Y_j$, then since $Y_{j^*} \geq Y_{i^*}$ and $X_{i^*} \geq X_{j^*}$, we have that $|X_{i^*}-Y_{j^*}| > \sqrt{t}$ implies either \begin{align*} X_{i^*}-Y_{i^*}>\sqrt{t} \hspace{1em}\text{ or } \hspace{1em}Y_{j^*}-X_{j^*} > \sqrt{t}. \end{align*} Hence \begin{align*} \int_0^\infty P((\max X_i - \max Y_i)^2 > t) dt &\leq \int_0^\infty P\left(\bigcup_{i=1}^n \{(X_i - Y_i)^2 > t\}\right) dt \\ &\leq \sum_{i=1}^n \int_0^\infty P((X_i-Y_i)^2>t)dt \\ &= \sum_{i=1}^n E(X_i-Y_i)^2 \\ &= 2\sum_{i=1}^n \text{Var}(X_i). \end{align*}

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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