# variance of maximum

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?

## 2 Answers

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

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*}