Namespaces
Variants
Actions

Difference between revisions of "Fishburn-Shepp inequality"

From Encyclopedia of Mathematics
Jump to: navigation, search
(TeX)
m (links)
 
Line 2: Line 2:
 
''$xyz$ inequality''
 
''$xyz$ inequality''
  
An inequality for linear extensions of a finite [[Partially ordered set|partially ordered set]] $(X,\prec)$. Elements $x,y\in X$ are incomparable if $x\neq y$ and neither $x\prec y$ nor $y\prec x$. Denote by $<_0$ a generic linear order extension of $\prec$ on $X$, let $N$ be the number of linear extensions $<_0$, and let $N(a_1<_0b_1,\ldots,a_n<_0b_n)$ be the number of linear extensions in which $a_i<_0b_i$ for $i=1,\ldots,n$.
+
An inequality for [[Linear order|linear]] extensions of a finite [[partially ordered set]] $(X,\prec)$. Elements $x,y\in X$ are incomparable if $x\neq y$ and neither $x\prec y$ nor $y\prec x$. Denote by $<_0$ a general linear [[Extension of an order|order extension]] of $\prec$ on $X$, let $N$ be the number of linear extensions $<_0$, and let $N(a_1<_0b_1,\ldots,a_n<_0b_n)$ be the number of linear extensions in which $a_i<_0b_i$ for $i=1,\ldots,n$.
  
 
The Fishburn–Shepp inequality says that if $x$, $y$ and $z$ are mutually incomparable members of $(X,\prec)$, then
 
The Fishburn–Shepp inequality says that if $x$, $y$ and $z$ are mutually incomparable members of $(X,\prec)$, then
Line 14: Line 14:
 
$$\mu(x<_0y)\mu(x<_0z)<\mu(x<_0y,x<_0z),$$
 
$$\mu(x<_0y)\mu(x<_0z)<\mu(x<_0y,x<_0z),$$
  
where $\mu(A)$ denotes the [[Probability|probability]] that a randomly chosen linear extension $<_0$ of $\prec$ satisfies $A$. When written as $\mu(x<_0y,x<_0z)/\mu(x<_0y)>\mu(x<_0z)$, one sees that the probability of $x<_0z$ increases when it is true that also $x<_0y$. Some plausible related inequalities are false [[#References|[a3]]].
+
where $\mu(A)$ denotes the [[probability]] that a randomly chosen linear extension $<_0$ of $\prec$ satisfies $A$. When written as $\mu(x<_0y,x<_0z)/\mu(x<_0y)>\mu(x<_0z)$, one sees that the probability of $x<_0z$ increases when it is true that also $x<_0y$. Some plausible related inequalities are false [[#References|[a3]]].
  
See also [[Correlation inequalities|Correlation inequalities]]; [[FKG inequality|FKG inequality]]; [[Holley inequality|Holley inequality]].
+
See also [[Correlation inequalities]]; [[FKG inequality]]; [[Holley inequality]].
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  R. Ahlswede,  D.E. Daykin,  "An inequality for the weights of two families, their unions and intersections"  ''Z. Wahrscheinlichkeitsth. verw. Gebiete'' , '''43'''  (1978)  pp. 183–185</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  P.C. Fishburn,  "A correlational inequality for linear extensions of a poset"  ''Order'' , '''1'''  (1984)  pp. 127–137</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  L.A. Shepp,  "The XYZ conjecture and the FKG inequality"  ''Ann. of Probab.'' , '''10'''  (1982)  pp. 824–827</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[a1]</TD> <TD valign="top">  R. Ahlswede,  D.E. Daykin,  "An inequality for the weights of two families, their unions and intersections"  ''Z. Wahrscheinlichkeitsth. verw. Gebiete'' , '''43'''  (1978)  pp. 183–185</TD></TR>
 +
<TR><TD valign="top">[a2]</TD> <TD valign="top">  P.C. Fishburn,  "A correlational inequality for linear extensions of a poset"  ''Order'' , '''1'''  (1984)  pp. 127–137</TD></TR>
 +
<TR><TD valign="top">[a3]</TD> <TD valign="top">  L.A. Shepp,  "The XYZ conjecture and the FKG inequality"  ''Ann. of Probab.'' , '''10'''  (1982)  pp. 824–827</TD></TR>
 +
</table>

Latest revision as of 17:05, 9 January 2016

$xyz$ inequality

An inequality for linear extensions of a finite partially ordered set $(X,\prec)$. Elements $x,y\in X$ are incomparable if $x\neq y$ and neither $x\prec y$ nor $y\prec x$. Denote by $<_0$ a general linear order extension of $\prec$ on $X$, let $N$ be the number of linear extensions $<_0$, and let $N(a_1<_0b_1,\ldots,a_n<_0b_n)$ be the number of linear extensions in which $a_i<_0b_i$ for $i=1,\ldots,n$.

The Fishburn–Shepp inequality says that if $x$, $y$ and $z$ are mutually incomparable members of $(X,\prec)$, then

$$N(x<_0 y)N(x<_0 z)<N(x<_0 y,x<_0 z)N.$$

This was first proved for $\leq$ in [a3], then for $<$ in [a2]. The Ahlswede–Daykin inequality [a1] plays a key role in the proof.

The inequality is also written as

$$\mu(x<_0y)\mu(x<_0z)<\mu(x<_0y,x<_0z),$$

where $\mu(A)$ denotes the probability that a randomly chosen linear extension $<_0$ of $\prec$ satisfies $A$. When written as $\mu(x<_0y,x<_0z)/\mu(x<_0y)>\mu(x<_0z)$, one sees that the probability of $x<_0z$ increases when it is true that also $x<_0y$. Some plausible related inequalities are false [a3].

See also Correlation inequalities; FKG inequality; Holley inequality.

References

[a1] R. Ahlswede, D.E. Daykin, "An inequality for the weights of two families, their unions and intersections" Z. Wahrscheinlichkeitsth. verw. Gebiete , 43 (1978) pp. 183–185
[a2] P.C. Fishburn, "A correlational inequality for linear extensions of a poset" Order , 1 (1984) pp. 127–137
[a3] L.A. Shepp, "The XYZ conjecture and the FKG inequality" Ann. of Probab. , 10 (1982) pp. 824–827
How to Cite This Entry:
Fishburn-Shepp inequality. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Fishburn-Shepp_inequality&oldid=37414
This article was adapted from an original article by P.C. FishburnL.A. Shepp (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article