Fishburn–Shepp inequality

In combinatorial mathematics, the Fishburn–Shepp inequality is an inequality for the number of extensions of partial orders to linear orders, found by Fishburn (1984) and Shepp (1982).

It states that if x, y, and z are incomparable elements of a finite poset, then

${\displaystyle P(x<y)P(x<z)\leqslant P((x<y)\wedge (x<z))\,}$

where P(*) is the probability that a linear order < extending the partial order has the property *.

In other words the probability that x < z strictly increases if one adds the condition that x < y. In the language of conditional probability,

${\displaystyle P(x<z)<P(x<z\mid x<y).\,}$

The proof uses the Ahlswede–Daykin inequality.

References

• Fishburn, Peter C. (1984), "A correlational inequality for linear extensions of a poset", Order, 1 (2): 127–137, doi:10.1007/BF00565648, ISSN 0167-8094, MR 764320
• Fishburn, P.C.; Shepp, L.A. (2001), "f/f110080", in Hazewinkel, Michiel, Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4
• Shepp, L. A. (1982), "The XYZ conjecture and the FKG inequality", The Annals of Probability, Institute of Mathematical Statistics, 10 (3): 824–827, doi:10.1214/aop/1176993791, ISSN 0091-1798, JSTOR 2243391, MR 659563