Namespaces
Variants
Actions

Difference between revisions of "FKG inequality"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (tex encoded by computer)
(details)
 
(One intermediate revision by the same user not shown)
Line 13: Line 13:
 
''Fortuin–Kasteleyn–Ginibre inequality''
 
''Fortuin–Kasteleyn–Ginibre inequality''
  
An inequality [[#References|[a3]]] that began a series of [[Correlation inequalities|correlation inequalities]] for finite partially ordered sets. Let  $ \Gamma $
+
An inequality [[#References|[a3]]] that began a series of [[correlation inequalities]] for finite partially ordered sets. Let  $\Gamma$
be a finite [[Partially ordered set|partially ordered set]] ordered by  $ \prec $(
+
be a finite [[partially ordered set]] ordered by  $\prec$ (irreflexive, transitive) with  $  ( \Gamma, \prec ) $
irreflexive, transitive) with  $  ( \Gamma, \prec ) $
+
a [[distributive lattice]]:  $  a \lor b =  \min  \{ {z \in \Gamma } : {a \preceq z, b \preceq z } \} $,  
a [[Distributive lattice|distributive lattice]]:  $  a \lor b =  \min  \{ {z \in \Gamma } : {a \cle z, b \cle z } \} $,  
+
$  a \wedge b =  \max  \{ {z \in \Gamma } : {z \preceq a, z \preceq b } \} $,  
$  a \wedge b =  \max  \{ {z \in \Gamma } : {z \cle a, z \cle b } \} $,  
 
 
and  $  a \wedge ( b \lor c ) = ( a \wedge b ) \lor ( a \wedge c ) $
 
and  $  a \wedge ( b \lor c ) = ( a \wedge b ) \lor ( a \wedge c ) $
 
for all  $  a,b, c \in \Gamma $.  
 
for all  $  a,b, c \in \Gamma $.  
 +
 
Suppose  $  \mu : \Gamma \rightarrow {[ 0, \infty ) } $
 
Suppose  $  \mu : \Gamma \rightarrow {[ 0, \infty ) } $
 
is log supermodular:
 
is log supermodular:
Line 38: Line 38:
  
 
$$  
 
$$  
\left [ \sum _ {a \in \Gamma } \mu ( a ) f ( a ) \right ] \left [ \sum _ {a \in \Gamma } \mu ( a ) g ( a ) \right ] \leq
+
\left [ \sum _ {a \in \Gamma } \mu ( a ) f ( a ) \right ] \left [ \sum _ {a \in \Gamma } \mu ( a ) g ( a ) \right ] \leq   
$$
 
 
 
$$
 
\leq   
 
 
\left [ \sum _ {a \in \Gamma } \mu ( a ) \right ] \left [ \sum _ {a \in \Gamma } \mu ( a ) f ( a ) g ( a ) \right ] .
 
\left [ \sum _ {a \in \Gamma } \mu ( a ) \right ] \left [ \sum _ {a \in \Gamma } \mu ( a ) f ( a ) g ( a ) \right ] .
 
$$
 
$$
  
 
If  $  \Gamma $
 
If  $  \Gamma $
is a [[Boolean algebra|Boolean algebra]] and  $  \mu $
+
is a [[Boolean algebra]] and  $  \mu $
is a [[Probability measure|probability measure]] on  $  \Gamma $,  
+
is a [[probability measure]] on  $  \Gamma $,  
 
the inequality is  $  {\mathsf E} _  \mu  ( f ) {\mathsf E} _  \mu  ( g ) \leq  {\mathsf E} _  \mu  ( fg ) $,  
 
the inequality is  $  {\mathsf E} _  \mu  ( f ) {\mathsf E} _  \mu  ( g ) \leq  {\mathsf E} _  \mu  ( fg ) $,  
 
where  $  {\mathsf E} _  \mu  $
 
where  $  {\mathsf E} _  \mu  $
denotes [[Mathematical expectation|mathematical expectation]].
+
denotes [[mathematical expectation]].
  
 
Related inequalities are discussed in [[#References|[a1]]], [[#References|[a2]]], [[#References|[a4]]], [[#References|[a5]]], [[#References|[a6]]], [[#References|[a7]]], [[#References|[a8]]], [[#References|[a9]]].
 
Related inequalities are discussed in [[#References|[a1]]], [[#References|[a2]]], [[#References|[a4]]], [[#References|[a5]]], [[#References|[a6]]], [[#References|[a7]]], [[#References|[a8]]], [[#References|[a9]]].
  
See also [[Ahlswede–Daykin inequality|Ahlswede–Daykin inequality]]; [[Fishburn–Shepp inequality|Fishburn–Shepp inequality]]; [[Holley inequality|Holley inequality]].
+
See also [[Ahlswede–Daykin inequality]]; [[Fishburn–Shepp inequality|Fishburn–Shepp inequality]]; [[Holley inequality|Holley inequality]].
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  B. Bollobás,   "Combinatorics" , Cambridge Univ. Press  (1986)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  P.C. Fishburn,   "Correlation in partially ordered sets"  ''Discrete Appl. Math.'' , '''39'''  (1992)  pp. 173–191</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  C.M. Fortuin,   P.N. Kasteleyn,   J. Ginibre,   "Correlation inequalities for some partially ordered sets"  ''Comm. Math. Phys.'' , '''22'''  (1971)  pp. 89–103</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  R.L. Graham,  "Linear extensions of partial orders and the FKG inequality"  I. Rival (ed.) , ''Ordered sets'' , Reidel  (1982)  pp. 213–236</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  R.L. Graham,  "Applications of the FKG inequality and its relatives" , ''Proc. 12th Internat. Symp. Math. Programming'' , Springer  (1983)  pp. 115–131</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  R. Holley,  "Remarks on the FKG inequalities"  ''Comm. Math. Phys.'' , '''36'''  (1974)  pp. 227–231</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  K. Joag-Dev,  L.A. Shepp,  R.A. Vitale,  "Remarks and open problems in the area of the FKG inequality" , ''Inequalities Stat. Probab.'' , ''IMS Lecture Notes'' , '''5'''  (1984)  pp. 121–126</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  L.A. Shepp,  "The XYZ conjecture and the FKG inequality"  ''Ann. of Probab.'' , '''10'''  (1982)  pp. 824–827</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  P M. Winkler,  "Correlation and order"  ''Contemp. Math.'' , '''57'''  (1986)  pp. 151–174</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[a1]</TD> <TD valign="top">  B. Bollobás, "Combinatorics" , Cambridge Univ. Press  (1986)</TD></TR><TR>
 +
<TD valign="top">[a2]</TD> <TD valign="top">  P.C. Fishburn, "Correlation in partially ordered sets"  ''Discrete Appl. Math.'' , '''39'''  (1992)  pp. 173–191</TD></TR>
 +
<TR><TD valign="top">[a3]</TD> <TD valign="top">  C.M. Fortuin, P.N. Kasteleyn, J. Ginibre, "Correlation inequalities for some partially ordered sets"  ''Comm. Math. Phys.'' , '''22'''  (1971)  pp. 89–103</TD></TR>
 +
<TR><TD valign="top">[a4]</TD> <TD valign="top">  R.L. Graham,  "Linear extensions of partial orders and the FKG inequality"  I. Rival (ed.) , ''Ordered sets'' , Reidel  (1982)  pp. 213–236</TD></TR>
 +
<TR><TD valign="top">[a5]</TD> <TD valign="top">  R.L. Graham,  "Applications of the FKG inequality and its relatives" , ''Proc. 12th Internat. Symp. Math. Programming'' , Springer  (1983)  pp. 115–131</TD></TR>
 +
<TR><TD valign="top">[a6]</TD> <TD valign="top">  R. Holley,  "Remarks on the FKG inequalities"  ''Comm. Math. Phys.'' , '''36'''  (1974)  pp. 227–231</TD></TR>
 +
<TR><TD valign="top">[a7]</TD> <TD valign="top">  K. Joag-Dev,  L.A. Shepp,  R.A. Vitale,  "Remarks and open problems in the area of the FKG inequality" , ''Inequalities Stat. Probab.'' , ''IMS Lecture Notes'' , '''5'''  (1984)  pp. 121–126</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  L.A. Shepp,  "The XYZ conjecture and the FKG inequality"  ''Ann. of Probab.'' , '''10'''  (1982)  pp. 824–827</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  P M. Winkler,  "Correlation and order"  ''Contemp. Math.'' , '''57'''  (1986)  pp. 151–174</TD></TR>
 +
</table>

Latest revision as of 19:26, 13 April 2024


Fortuin–Kasteleyn–Ginibre inequality

An inequality [a3] that began a series of correlation inequalities for finite partially ordered sets. Let $\Gamma$ be a finite partially ordered set ordered by $\prec$ (irreflexive, transitive) with $ ( \Gamma, \prec ) $ a distributive lattice: $ a \lor b = \min \{ {z \in \Gamma } : {a \preceq z, b \preceq z } \} $, $ a \wedge b = \max \{ {z \in \Gamma } : {z \preceq a, z \preceq b } \} $, and $ a \wedge ( b \lor c ) = ( a \wedge b ) \lor ( a \wedge c ) $ for all $ a,b, c \in \Gamma $.

Suppose $ \mu : \Gamma \rightarrow {[ 0, \infty ) } $ is log supermodular:

$$ \mu ( a ) \mu ( b ) \leq \mu ( a \lor b ) \mu ( a \wedge b ) \textrm{ for all } a, b \in \Gamma, $$

and that $ f : \Gamma \rightarrow \mathbf R $ and $ g : \Gamma \rightarrow \mathbf R $ are non-decreasing:

$$ a \prec b \Rightarrow \{ f ( a ) \leq f ( b ) , g ( a ) \leq g ( b ) \} \textrm{ for all } a,b \in \Gamma . $$

The FKG inequality is:

$$ \left [ \sum _ {a \in \Gamma } \mu ( a ) f ( a ) \right ] \left [ \sum _ {a \in \Gamma } \mu ( a ) g ( a ) \right ] \leq \left [ \sum _ {a \in \Gamma } \mu ( a ) \right ] \left [ \sum _ {a \in \Gamma } \mu ( a ) f ( a ) g ( a ) \right ] . $$

If $ \Gamma $ is a Boolean algebra and $ \mu $ is a probability measure on $ \Gamma $, the inequality is $ {\mathsf E} _ \mu ( f ) {\mathsf E} _ \mu ( g ) \leq {\mathsf E} _ \mu ( fg ) $, where $ {\mathsf E} _ \mu $ denotes mathematical expectation.

Related inequalities are discussed in [a1], [a2], [a4], [a5], [a6], [a7], [a8], [a9].

See also Ahlswede–Daykin inequality; Fishburn–Shepp inequality; Holley inequality.

References

[a1] B. Bollobás, "Combinatorics" , Cambridge Univ. Press (1986)
[a2] P.C. Fishburn, "Correlation in partially ordered sets" Discrete Appl. Math. , 39 (1992) pp. 173–191
[a3] C.M. Fortuin, P.N. Kasteleyn, J. Ginibre, "Correlation inequalities for some partially ordered sets" Comm. Math. Phys. , 22 (1971) pp. 89–103
[a4] R.L. Graham, "Linear extensions of partial orders and the FKG inequality" I. Rival (ed.) , Ordered sets , Reidel (1982) pp. 213–236
[a5] R.L. Graham, "Applications of the FKG inequality and its relatives" , Proc. 12th Internat. Symp. Math. Programming , Springer (1983) pp. 115–131
[a6] R. Holley, "Remarks on the FKG inequalities" Comm. Math. Phys. , 36 (1974) pp. 227–231
[a7] K. Joag-Dev, L.A. Shepp, R.A. Vitale, "Remarks and open problems in the area of the FKG inequality" , Inequalities Stat. Probab. , IMS Lecture Notes , 5 (1984) pp. 121–126
[a8] L.A. Shepp, "The XYZ conjecture and the FKG inequality" Ann. of Probab. , 10 (1982) pp. 824–827
[a9] P M. Winkler, "Correlation and order" Contemp. Math. , 57 (1986) pp. 151–174
How to Cite This Entry:
FKG inequality. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=FKG_inequality&oldid=46896
This article was adapted from an original article by P.C. Fishburn (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article