Expectation of maxima of random functions

Question

I have a question regarded the expected maxima of random functions, but it seems easier to phrase using n-tuples of random variables:

Let $(X_{1}, X_{2}, ..., X_{n})$ and $(Y_{1}, ..., Y_{n})$ be identically distributed (as n-tuples) and independent of one another. (That is the two n-tuples are independent, there is no assumption that the $X_{i}$ are independent of one another, nor that they are equal in distribution to one another.) Fix a permutation, $\sigma \in S_{n}$.

I want to show that $$\mathbb{E}(\max\limits_{1 \leq i \leq n} \{ X_{i}+Y_{i} \}) \geq \mathbb{E}(\max\limits_{1 \leq i \leq n} \{ X_{i} + Y_{\sigma(i)} \})$$

The vague logic behing believing this is true is that if the $X_{i}$ have different expectations and $\sigma$ is not the identity, then the left hand side will kind of bias towards selecting so that both terms are big, while the right side might not.

I wasn't really sure how to google this so I'm posting here. I tried defining sets $$A_{k, j} := \{ k \text{ maximizes } (X_{i}+Y_{i} ), j \text{ maximizes } ( X_{i} + Y_{\sigma(i)} ) \}$$

With any consistent convention for distinguishing a single maximizer when there are multiple (e.g. take the one of the smallest index)

Then I tried computing:

$$\mathbb{E}(\max\limits_{1 \leq i \leq n} \{ X_{i}+Y_{i} \} - \max\limits_{1 \leq i \leq n} \{ X_{i}+Y_{\sigma(i)} \}) =$$ $$\sum\limits_{i=1}^{i=n}\sum\limits_{k=1}^{k=n} \int_{A_{k, j}} \left( (X_{k}+Y_{k})-(X_{j}+Y_{\sigma(j)})\right) d\mathbb{P}$$

And somehow use some properties of the set $A_{k, j}$, but I didn't know where to go and feel like this is probably the wrong approach. Is this statement even true, it seems like it should be? Also it seems like it should be easy to show but I'm not seeing how. Thanks

Answer 1

If I understand the setup right, the inequality is not generally true.

A small counterexample with $n=3$: Let $X=(X_1,X_2,X_3)$ take the values $(0,1,1)$ and $(1,0,0)$ with probabilities $1/2$ each. Let $Y=(Y_1,Y_2,Y_3)$ have the same distribution independently from $X$, and let $\sigma = 321$ (the permutation that swaps 1 and 3). Then the left-hand expectation is $1.5$ and the right-hand expectation is $1.75$.