Fishburn–Shepp inequality

From HandWiki
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;-

[math]\displaystyle{ P(x\lt y)P(x\lt z) \leqslant P((x\lt y) \wedge (x\lt z)) }[/math]

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,

[math]\displaystyle{ P(x \lt z) \lt P(x \lt z \mid x \lt y). }[/math]

The proof uses the Ahlswede–Daykin inequality.

References