# expected difference of maxima

Let $$X_1,\dots,X_n$$ and $$Y_1,\dots,Y_n$$ be random variables for which $$X_i \geq Y_i$$ a.s. and the $$(Y_i)$$ are identically distributed. Is it true that \begin{align*} E(\max X_i - \max Y_j) \geq E(X_i-Y_i) \end{align*} for any $$i$$?

I tried reducing the problem to a question about the tail probabilities using \begin{align*} E(\max X_i - \max Y_j) = \int_0^\infty P(\max X_i - \max Y_i > t) dt, \end{align*} since $$\max X_i - \max Y_j \geq 0$$, but this doesn't appear to directly give the inequality. Can anyone provide a proof or counterexample?

• The tail integral only holds if all the random variables are a.s. positive. Nov 30, 2019 at 22:00
• $X_i \geq Y_i$ for all $i$ should imply that $\max X_i - \max Y_j \geq 0$, no? Nov 30, 2019 at 22:01
• Yes, it does. ${}{}{}$ Nov 30, 2019 at 22:06

## 1 Answer

Note that $$X_i - Y_i\geq 0$$ for all $$i$$. You do have $$\max_{1\leq i\leq n}\mathbb{E}[X_i - Y_i] \leq \mathbb{E}[\max_{1\leq i\leq n}(X_i - Y_i)] \tag{1}$$ but you don't have, in general, $$\max_{1\leq i\leq n}\mathbb{E}[X_i - Y_i] \leq \mathbb{E}[\max_{1\leq i\leq n}X_i - \max_{1\leq i\leq n}Y_i]\tag{2}$$ To see why (2) can fail to hold, consider $$Y_1,\dots,Y_n$$ i.i.d. Normal $$N(0,1)$$ r.v.'s, and $$X_i=\max_{1\leq j\leq n}Y_j$$ for all $$i$$. Then the RHS of (2) is $$0$$, but the LHS is $$\max_{1\leq i\leq n}\mathbb{E}[\max_{1\leq j\leq n} Y_j - Y_i]= \max_{1\leq i\leq n}(\mathbb{E}[\max_{1\leq j\leq n} Y_j] - \mathbb{E}[Y_i]) = \max_{1\leq i\leq n}(\mathbb{E}[\max_{1\leq j\leq n} Y_j] - 0) = \mathbb{E}[\max_{1\leq j\leq n} Y_j] \operatorname*{\sim}_{n\to\infty} \sqrt{2\log n}$$ which is strictly positive for any not-too-small $$n$$.