Suppose we have three random variables X,Y,XX,Y,X on the same discrete outcome space. What’s a maximal value mm such that P(X>Y)≥mP(X>Y) \geq m, P(Y>Z)≥mP(Y>Z) \geq m, P(Z>X)≥mP(Z>X) \geq m? There are no restrictions on the variables, so they can be independent.

I know mm can be 12\frac{1}{2}, setting X∈{3}X \in \{ 3 \}, Y∈{2,4}Y \in \{ 2,4 \}, Z∈{1,5}Z \in \{ 1, 5\}, where each outcome is equally likely. But can mm be bigger, and how to prove an upper bound on mm?

=================

Are they independent?

– Hurkyl

Oct 21 at 0:04

Thanks for the clarification – there are no restrictions on the variables.

– michbad

Oct 21 at 0:06

I was more worried about the opposite: allowing them to be dependent might give a different answer than the restricted problem where X,Y,ZX,Y,Z must be independent.

– Hurkyl

Oct 21 at 0:07

=================

1 Answer

1

=================

Here’s an easy upper bound: define

S=[X>Y]+[Y>Z]+[Z>X] S = [X>Y] + [Y>Z] + [Z>X]

where [.][.] is the Iverson bracket (11 if the argument is true, 00 otherwise).

It’s easy to see that S∈{0,1,2}S \in \{0, 1, 2\} and

E(S)=P(X>Y)+P(Y>Z)+P(Z>X) \mathbb{E}(S) = \mathbb{P}(X>Y) + \mathbb{P}(Y>Z) + \mathbb{P}(Z>X)

Since E(S)≤2\mathbb{E}(S) \leq 2, the three probabilities cannot all exceed 23\frac{2}{3}, so m≤23m \leq \frac{2}{3}.

Thank you! Would I achieve this bound by similar reasoning as in my example with 1/2?

– michbad

Oct 21 at 0:12

@michbad I think the bound is only achievable if the variables are not independent — specifically, I think you need P(X