# Covariance of maxima

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.

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.

• Is there a simple modification to your example that has each X_i and Y_i as taking values in $\{0,1\}$? – Daniel Xiang Dec 18 '19 at 20:40
• Nothing simple comes to mind. The key trick to the above answer is finding dependent-but-uncorrelated $(X_i, Y_i)$ so the RHS $=0$. Note that $\{0,1\}$ both $\ge 0$ is not the issue - since covariance is invariant to shifts, we can just consider $\{-1,+1\}$ instead. However it seems to me if each variable is bi-valued, then they cannot be dependent-yet-uncorrelated. So any coin-based counter-examples (if they exist) would have to use a different trick. – antkam Dec 18 '19 at 20:55
• I feel that the following answer is mildly related to this discussion: stats.stackexchange.com/a/303798 – Abdullah Ali Sivas Dec 18 '19 at 21:14
• @AbdullahAliSivas - Indeed my $X_i$ is symmetric and my $|\cdot|$ function is even, hence we obtain a pair $(X_i, |X_i|)$ which is uncorrelated-yet-dependent. However, if every variable is bi-valued (Bernoulli), then (I have since proved) zero correlation implies independence. As a special case, an even function applied to a symmetric bi-valued $X = \pm a$ would result in a constant $Y = +a$, and constants are independent of any other r.v. – antkam Dec 18 '19 at 21:28
• @DanielXiang - sorry to disappoint you, but coin-based counter-example also exists, and indeed requires a different "trick". – antkam Dec 18 '19 at 21:42