Negatively correlated random variables have a lower min than independent ones.

Let's say I have two random variables, $$X_1$$ and $$X_2$$ that are negatively correlated. Further, let's define $$X=\min(X_1,X_2)$$. Also, $$Y_1$$ is iid to $$X_1$$ and $$Y_2$$ is iid to $$X_2$$, but $$Y_1$$ and $$Y_2$$ are independent. Similarly, $$Y=\min(Y_1,Y_2)$$.

It's quite clear that we should have $$E(Y)>E(X)$$. We should also have $$P(Y>X)>\frac 1 2$$. More generally, maybe we can even say:

$$P(Y>n) > P(X>n) \; \forall \; n$$

The reason is that anytime one of $$X_1$$ or $$X_2$$ is pushed up, the other is pushed down. I've validated this for many particular cases. However, I'm looking at a general proof.

Validation on Coupon collector's problem.

Let's say there are $$m$$ coupons and each time I collect a coupon, it could be the $$j$$th coupon with probability $$p_j$$. Of course, $$\sum p_j = 1$$.

Let $$N_j$$ be the number of coupons we need to collect before seeing the first coupon of $$j$$th kind. $$N_1$$ and $$N_2$$ are geometric random variables with parameters $$p_1$$ and $$p_2$$.

It's clear that $$N_1$$ and $$N_2$$ are negatively correlated since if $$p_1$$ is high, it takes away some probability mass from $$p_2$$. So, if $$N_1$$ is low, we can expect $$N_2$$ to be high.

Let $$N = \min(N_1,N_2)$$. This makes $$N$$ the coupons needed to collect either a type-1 or type-2 coupon. It is clear that $$N$$ is geometric with parameter $$p_1+p_2$$. So, $$S_a = P(N>n) = (1-p_1-p_2)^n$$.

If they were independent, we would have $$S_\bar{a} = P(N>n)=P(N_1>n \;\&\; N_2>n)=P(N_1>n)P(N_2>n) = (1-p_1)^n(1-p_2)^n$$.

We need to show $$S_\bar{a} \geq S_a$$, which is the same as: $$(1-p_1)(1-p_2) \geq 1-p_1-p_2$$.

$$1-p_1-p_2+p_1p_2 \geq 1-p_1-p_2$$ This is obviously true.

Covariance and correlation are very tricky. They often suggest things that sound true, and are indeed often true, but are not universally true. E.g. in your context, here is a counter-example where $$E[X] > E[Y]$$.

(BTW, you conjectured that $$E[Y] > E[X]$$ but that has no hope to begin with. Say all possible values of $$Y_1 <$$ all possible values of $$Y_2$$, then $$X = X_1, Y=Y_1$$ and clearly $$E[Y] = E[X]$$. So the most you can hope for is $$E[Y] \ge E[X]$$. But as the following counter-example shows, even that can be violated.)

• $$Y_1, Y_2$$ are i.i.d. and take values $$\{0, 1, 2\}$$ with equal prob $$1/3$$ each.

• $$E[Y_i] = 1$$

• $$E[Y] = \frac19 ( 1 + 1 + 1 + 2) = \frac59$$

• $$(X_1, X_2)$$ are jointly distributed as follows, for some $$0 < p < \frac12 < q < 1$$ with $$p+q=1$$:

• $$(0,0)$$ with prob $$p/3$$
• $$(0,2)$$ with prob $$q/3$$

• $$(1,1)$$ with prob $$1/3$$

• $$(2,0)$$ with prob $$q/3$$

• $$(2,2)$$ with prob $$p/3$$

• It is easy to verify that $$X_i$$ has the same (marginal) distribution as $$Y_i$$

• $$Cov(X_1,X_2) = E[X_1 X_2] - E[X_1]E[X_2] = \frac13 (1 + 4p) - 1 < 0$$ since $$p < \frac12$$

So the precondition (negative correlation) is satisfied. It remains to calculate:

• $$E[X] = \frac13 ( 1 + 2p)$$

Now for any $$p \in (\frac13, \frac12), E[X] = \frac13 (1+2p) > \frac13 (1 + \frac23) = \frac59 = E[Y]$$. QED

Further thoughts: Since $$E[X_i] = E[Y_i]$$ and $$Y_1,Y_2$$ are independent, the requirement that $$Cov(X_1, X_2) < 0$$ is equivalent to:

$$E[X_1 X_2] < E[X_1]E[X_2] = E[Y_1]E[Y_2] = E[Y_1 Y_2]$$

So you are basically conjecturing that

$$E[X_1 X_2] < E[Y_1 Y_2]\implies E[\min(X_1,X_2)] \le E[\min(Y_1, Y_2)]$$

But viewed this way, it hardly seems like a reasonable conjecture at all. The product of two variables has not much to do with the minimum of the same two variables. In a sense, there should be a lot of "freedom" to choose pairs of variables (even constrained as you described) so that one pair has the higher $$E[\text{product}]$$ while the other pair has the higher $$E[\text{minimum}]$$. And this ultimately points to the fact that covariance, while suggestive, leaves a lot of freedom between the two variables.