I came across this probability question today:
Let $X_1$, $X_2$ and $X_3$ be discrete random variables. Denote $a_{ij}=\mathbb{P}(X_i>X_j)$, show that $\text{min}\{a_{12},a_{23},a_{31}\}\leq\frac23$.
I’m not sure where to begin — is this an order statistics question? My intuition is that this is similar to the stick breaking problem, although I doubt this is of use since they are discrete random variables. Additionally, is there a generalisation for $n$ variables? Cheers!
Best Answer
Assume the converse, that the min is strictly greater than $2/3$
Then $P(X_1 > X_3) \ge P(X_1 >X_2 > X_3) >1/3$, which is absurd given that $P(X_3 > X_1) >2/3$ by assumption.
To see the lower bound on $P(X_1 >X_2 > X_3)$, observe that \begin{align*}P(X_1 > X_2 >X_3)& =P(\{X_1 > X_2\} \cap \{X_2>X_3\}) \\ &= P(X_1 > X_2)+P(X_2>X_3)-P(\{X_1 > X_2\} \cup \{X_2>X_3\}) \\ & > 4/3-1=1/3\end{align*}
As for the generalisation to $n$ events, it will be the same statement with $(n-1)/(n)$ replacing $2/3$.