Covariance of maxima

Question

Let $X_1,\dots,X_n$ and $Y_1,\dots,Y_n$ be random variables. Is it true that \begin{align*} \text{Cov}(\max_i X_i, \max_j Y_j) \leq \sum_{i, j}|\text{Cov}(X_i,Y_j)| \end{align*}

My intuition as to why this may be true is from the previous question: variance of maximum

I believe the identity $2\text{Cov}(X,Y)=E(X-X')(Y-Y')$ should be relevant, where $(X',Y')$ is an independent copy of the couple $(X,Y)$, but I'm not sure how to proceed, since we can no longer write the expected value as an integral of the tail probability (since $(X-X')(Y-Y')$ is not necessarily positive). If needed, we may also assume that all variables are positively correlated with each other, and that they are each marginally distributed as bernoulli coin flips. But hopefully the more general statement above is true on its own.

Answer 1

The general form of the conjecture is false, due to the (often forgotten?) fact that dependent variables can be uncorrelated (i.e. zero covariance). This makes the RHS $=0$ and the rest is not difficult. Here is a simple counter-example:

• $n=2$ and $X_1, X_2$ i.i.d. uniform $\in \{-1, 0, 1\}$ with prob $\frac13$ for each choice.

• $Y_i = |X_i|$

• $E[X_i Y_i] = \frac13 ( -1 + 0 + 1) = 0 = E[X_i]E[Y_i]$ so $Cov(X_i, Y_i) = 0$ i.e. they are uncorrelated. Thus RHS $=0$ because each term in the sum is either independent or uncorrelated.

Meanwhile these tables show $\max X_i$ (top table) and $\max Y_i$ (bottom table) for each of the $9$ equi-probable choices of $(X_1, X_2)$:

maxX  -1   0   1
 -1   -1   0   1
  0    0   0   1
  1    1   1   1

maxY  -1   0   1
 -1    1   1   1
  0    1   0   1
  1    1   1   1

From these tables:

• $E[\max X_i] = \frac19 (5 - 1) = \frac49$

• $E[\max Y_i] = \frac89$

• $E[\max X_i \cdot \max Y_i] = E[\max X_i] = \frac49$

• so $Cov(\max X_i, \max Y_i) = \frac49 - \frac49 \frac89 = \frac{4}{81} > 0 = $ RHS.

Further guess: I think adding "each variable positively correlated with each other" won't help, because a very small perturbation to above can (my guess) make the positive covariances on the RHS arbitrarily small, not enough to overwhelm the $\frac{4}{81}$ covariance on the LHS.

---

UPDATE: Here is a coin-based counter-example. The trick we now exploit is that pairwise independence does not equal mutual independence. And pairwise independence is sufficient to make RHS $= 0$.

• $n = 2$ and $X_1, X_2$ i.i.d. uniform $\in \{0,1\}$ with prob $\frac12$ for each choice.

• $Y_1 = Y_2 = \max Y_j = (X_1 \neq X_2)$, i.e. $(X_1 ~~~\text{xor}~~~ X_2)$

• As is well known, $\forall (i,j) \in \{1,2\}^2: X_i, Y_j$ are (pairwise) independent, so $Cov(X_i, Y_j) = 0$ and RHS $=0$.

Here are all four possibilities:

X1  X2  maxX  Y1=Y2=maxY
 0   0    0           0
 0   1    1           1
 1   0    1           1
 1   1    1           0

• $E[\max X_i] = \frac34$

• $E[\max Y_i] = \frac12$

• $E[\max X_i \cdot \max Y_i] = \frac12$

• $Cov(\max X_i, \max Y_i) = \frac12 - \frac12 \frac34 = \frac18 > 0 =$ RHS.