XYZ inequality

Remarks

Shepp proved the inequality using the FKG inequality on a suitable distributive lattice of integer labellings of $P$. It says that the events "$x$ comes before $y$" and "$x$ comes before $z$" are positively correlated. This matches intuition: if $x$ comes early relative to $y$, it tends to come early in general.

Example: let $P$ be the antichain on $\set{x, y, z}$. All $6$ orderings are linear extensions, so $\Pr(x \prec y) = \Pr(x \prec z) = 1/2$, and $x$ comes first in $2$ of the $6$ orderings, so the left side is $1/3 \ge 1/4$.

Going deeper

For a student

The inequality belongs to the family of correlation inequalities for linear extensions, studied in connection with sorting and with the 1/3–2/3 conjecture. Its proof is a model use of the FKG inequality. One looks at order-preserving labellings of $P$ by a large chain, which form a distributive lattice. One applies FKG there and then lets the chain grow.