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
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,
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
This article is issued from Wikipedia - version of the 9/24/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.