Fishburn–Shepp inequality

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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

 P(x<y)P(x<z) < 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,

 P(x < z) < P(x < z \mid x < y).\,

The proof uses the Ahlswede–Daykin inequality.

References[edit]