Correlation inequalities

Correlation between variables in multivariate statistics (cf. also Multi-dimensional statistical analysis) [a19] has motivated classes of inequalities on subsets of a base set $ S $ that are referred to as correlation inequalities. They are often stated deterministically but usually have probabilistic interpretations. For example, suppose $ S $ is the family of all subsets of a finite set $ \{ 1 \dots n \} $, and let $ A $ and $ B $ be order ideals or down-sets in $ ( S, \subset ) $: $ a \subset b \in A $ implies $ a \in A $, $ a \subset b \in B $ implies $ a \in B $, with $ A, B \subseteq S $. Then, [a13], [a16], $ 2 ^ {n} | {A \cap B } | \geq | A | \cdot | B | $. When $ \mu $ is the uniform probability measure (cf. also Probability measure) on $ 2 ^ {S} $, so that $ \mu ( a ) = \mu ( \{ a \} ) = 2 ^ {- n } $ for every $ a \in S $, and $ \mu ( A ) = | A | 2 ^ {- n } $, one has $ \mu ( A \cap B ) \geq \mu ( A ) \mu ( B ) $. Hence, with respect to $ \mu $, $ A $ and $ B $ are correlated whenever both are down-sets.

As general definitions, one says with respect to a probability measure $ \mu $ on an algebra $ {\mathcal E} $ of subsets of $ S $ that $ A, B \in {\mathcal E} $ are positively correlated if $ \mu ( A \cap B ) > \mu ( A ) \mu ( B ) $ and non-negatively correlated if $ \mu ( A \cap B ) \geq \mu ( A ) \mu ( B ) $. Inequality reversals define negative correlation and non-positive correlation, respectively. The instances of these inequalities and generalizations described below assume that $ S $ is a finite set partially ordered by $ \prec $ so that $ \prec $ is irreflexive (never $ a \prec a $) and transitive: $ a \prec b $ and $ b \prec c $ imply $ a \prec c $.

Inequalities for distributive lattices.

Let $ ( S, \prec ) $ be a distributive lattice with join $ a \lor b $ and meet $ a \wedge b $ defined by

$$ a \lor b = \min \left \{ {z \in S } : {a \cle z, b \cle z } \right \} , $$

$$ a \wedge b = \max \left \{ {z \in S } : {z \cle a, z \cle b } \right \} . $$

Distributivity says that $ a \wedge ( b \lor c ) = ( a \wedge b ) \lor ( a \wedge c ) $ for all $ a,b,c \in S $. A mapping $ f : S \rightarrow \mathbf R $ is non-decreasing if $ a \prec b $ implies $ f ( a ) \leq f ( b ) $ for all $ a,b \in S $, and $ f ( A ) $ is defined as $ \sum _ {a \in A } f ( a ) $ for $ A \subseteq S $, with $ f ( \emptyset ) = 0 $. The join and meet $ \lor $ and $ \wedge $ can be extended to subsets $ A, B \subseteq S $ by

$$ A \lor B = \left \{ {a \lor b } : {a \in A, b \in B } \right \} , $$

$$ A \wedge B = \left \{ {a \wedge b } : {a \in A, b \in B } \right \} , $$

with the understanding that $ A \lor B = A \wedge B = \emptyset $ if $ A $ or $ B $ is empty.

The pre-eminent correlation inequality is the Ahlswede–Daykin inequality [a1], also called the four-functions inequality [a2]. It says that if $ {f _ {1} , f _ {2} , f _ {3} , f _ {4} } : S \rightarrow {[ 0, \infty ) } $ satisfy

$$ f _ {1} ( a ) f _ {2} ( b ) \leq f _ {3} ( a \lor b ) f _ {4} ( a \wedge b ) \textrm{ for all } a, b \in S, $$

then

$$ f _ {1} ( A ) f _ {2} ( B ) \leq f _ {3} ( A \lor B ) f _ {4} ( A \wedge B ) \textrm{ for all } A, B \subseteq S . $$

This is a very powerful result that allows efficient proofs of many other correlation inequalities [a2], [a7], [a10], [a23]. One unusual application [a8] concerns match sets of orders of a deck of $ 52 $ cards numbered $ 1 $ through $ 52 $. For each order, $ M = \{ k : {\textrm{ card } k \textrm{ is the } k \textrm{ th card at the top of the deck } } \} $. Let $ A = \{ M : {\textrm{ an even } k \in M } \} $ and $ B = \{ M : {\textrm{ an odd } k \in M } \} $. When $ \mu $ is the uniform distribution on the $ 52! $ orders, $ \mu ( A \cap B ) \geq \mu ( A ) \mu ( B ) $. Hence, if the match set of a well-shuffled deck contains an odd number, this can only increase our confidence that it contains an even number.

The most important correlation inequality historically is the FKG inequality [a9] (also known as the Fortuin–Kasteleyn–Ginibre inequality), which says that if $ \eta : S \rightarrow {[ 0, \infty ) } $ is log supermodular, i.e.,

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

and if $ f : S \rightarrow \mathbf R $ and $ g : S \rightarrow \mathbf R $ are non-decreasing, then

$$ \left [ \sum _ { S } \eta ( a ) f ( a ) \right ] \left [ \sum _ { S } \eta ( a ) g ( a ) \right ] \leq $$

$$ \leq \left [ \sum _ { S } \eta ( a ) \right ] \left [ \sum _ { S } \eta ( a ) f ( a ) g ( a ) \right ] . $$

This can be written in terms of the mathematical expectation operation $ {\mathsf E} _ \eta $ as $ {\mathsf E} _ \eta ( f ) {\mathsf E} _ \eta ( g ) \leq {\mathsf E} _ \eta ( fg ) $, when $ S $ is a Boolean algebra and $ \eta $ is a log supermodular probability measure with $ \lor = \cup $ and $ \wedge = \cap $. Suitable definitions of $ f $ and $ g $ with $ \{ 0,1 \} $ co-domains show that $ A, B \subseteq S $ are non-negatively correlated when both are up-sets or order filters, given log supermodularity.

Another notable result is the Holley inequality [a12]. Suppose $ {\eta _ {1} } : S \rightarrow {[ 0, \infty ) } $ and $ {\eta _ {2} } : S \rightarrow {[ 0, \infty ) } $ satisfy $ \sum _ {S} \eta _ {1} ( a ) = \sum _ {S} \eta _ {2} ( a ) $ along with the following inequality that generalizes log supermodularity and is itself generalized by the four-function Ahlswede–Daykin hypothesis:

$$ \eta _ {1} ( a ) \eta _ {2} ( b ) \leq \eta _ {1} ( a \lor b ) \eta _ {2} ( a \wedge b ) \textrm{ for all } a,b \in S . $$

Then the Holley inequality says that for every non-decreasing $ f : S \rightarrow \mathbf R $,

$$ \sum _ { S } f ( a ) \eta _ {1} ( a ) \geq \sum _ { S } f ( a ) \eta _ {2} ( a ) . $$

Simple proofs of the FKG and Holley inequalities follow from the Ahlswede–Daykin inequality by suitable choices of $ f _ {1} $ through $ f _ {4} $. Also, when $ f _ {i} = \eta $ for all $ i $, log supermodularity on $ S $ implies log supermodularity on the subsets of $ S $; when $ f _ {i} \equiv 1 $ for all $ i $, one obtains $ | A | \cdot | B | \leq | {A \lor B } | \cdot | {A \wedge B } | $ for all $ A,B \subseteq S $, which is equivalent to distributivity [a5] for an ordered lattice $ ( S, \prec ) $.

Systems of subsets.

Several inequalities for $ ( S, \subset ) $ when $ S $ is the family of subsets of $ \{ 1 \dots n \} $ have already been given. Log supermodularity for a probability measure $ \mu $ on $ 2 ^ {S} $ is defined as $ \mu ( a ) \mu ( b ) \leq \mu ( a \cup b ) \mu ( a \cap b ) $ for all $ a,b \in S $, and when this holds, the FKG inequality says that $ {\mathsf E} _ \mu ( f ) {\mathsf E} _ \mu ( g ) \leq {\mathsf E} _ \mu ( fg ) $ for non-decreasing $ f : S \rightarrow \mathbf R $ and $ g : S \rightarrow \mathbf R $ and implies that $ \mu ( A ) \mu ( B ) \leq \mu ( A \lor B ) \mu ( A \wedge B ) $ for all $ A,B \subseteq S $. In addition, if $ A $ and $ B $ are down-sets or up-sets, then $ \mu ( A \cap B ) \geq \mu ( A ) \mu ( B ) $. When $ \mu $ is uniform, in which case log supermodularity is automatic, $ 2 ^ {n} | {A \cap B } | \leq | A | \cdot | B | $ if $ A $ is an up-set and $ B $ is a down-set, so the two are non-positively correlated when the complementary orientations obtain.

Another inequality involves set differences [a14]. Let $ A - B = \{ {a \setminus b } : {a \in A, b \in B } \} $ for $ A, B \subseteq S $. Then $ | {A - B } | \cdot | {B - A } | \geq | A | \cdot | B | $, and, in particular, $ | {A - A } | \geq | A | $.

The match set of a permutation $ \sigma $ on $ \{ 1 \dots n \} $ is defined as $ M ( \sigma ) = \{ {i \in \{ 1 \dots n \} } : {\sigma ( i ) = i } \} $. Assuming that all $ n! $ permutations are equally likely, let $ \mu ( a ) $ for $ a \subseteq \{ 1 \dots n \} $ be the probability that $ M ( \sigma ) = a $. Note that $ \mu ( a ) = 0 $ when $ | a | = n - 1 $ and hence that $ \mu $ is not log supermodular. However, there still is an FKG-like inequality [a8], because $ \mu ( A \cap B ) \geq \mu ( A ) \mu ( B ) $ whenever $ A,B \subseteq S $ are up-sets. This illustrates the non-necessity of log supermodularity in certain cases for a correlation inequality to hold.

Linear extensions.

Another class of correlation inequalities arises when $ S $ is the set of linear extensions of a finite partially ordered set $ ( X, \prec ) $ and all members of $ S $ are equally likely. $ ( X, < _ {0} ) $ is a linear extension of $ ( X, \prec ) $ if $ ( X, < _ {0} ) $ is a partially ordered set, $ \prec \subseteq < _ {0} $ and, for all distinct $ x,y \in X $, $ x < _ {0} y $ or $ y < _ {0} x $. Let $ N $ be the number of linear extensions of $ ( X, \prec ) $, so the probability law for $ S $ is $ \mu ( a ) = 1/N $. By additivity, $ \mu ( A ) = \sum _ {A} \mu ( a ) $ for each subset $ A $ of linear extensions.

A premier correlation inequality in this setting is the Fishburn–Shepp inequality [a6], [a18], also known as the $ xyz $ inequality. One says that $ x,y \in X $ are incomparable if $ x \neq y $ and neither $ x \prec y $ nor $ y \prec x $, and denotes by $ ( x _ {1} < _ {0} y _ {1} \dots x _ {m} < _ {0} y _ {m} ) $ the set of all linear extensions of $ ( X, \prec ) $ that satisfy the $ x _ {i} < _ {0} y _ {i} $ relations. The Fishburn–Shepp inequality says that if $ x $, $ y $ and $ z $ are mutually incomparable in $ ( X, \prec ) $, then

$$ \mu ( x < _ {0} y ) \mu ( x < _ {0} z ) < \mu ( x < _ {0} y, x < _ {0} z ) , $$

so events $ A = ( x < _ {0} y ) $ and $ B = ( x < _ {0} z ) $ are positively correlated. Rewritten as $ \mu ( A \cap B ) / \mu ( A ) > \mu ( B ) $, one sees that the probability of $ x < _ {0} z $ in a randomly chosen linear extension increases when it is true also that $ x < _ {0} y $. Examples in [a10], [a17], [a18] show that other plausible positive or non-negative correlations need not be true.

Inequalities involving two-part partitions of $ X $ are featured in [a11], [a17]. Suppose $ \{ X _ {1} , X _ {2} \} $ is a non-trivial partition of $ X $. Let $ A = ( a _ {1} < _ {0} b _ {1} \dots a _ {j} < _ {0} b _ {j} ) $ and $ B = ( c _ {1} < _ {0} d _ {1} \dots c _ {k} < _ {0} d _ {k} ) $ for $ a _ {i} , c _ {i} \in X _ {1} $ and $ b _ {i} , d _ {i} \in X _ {2} $. If the restriction of $ \prec $ in $ ( X, \prec ) $ to each $ X _ {i} $ is a linear order (cf. also Order (on a set)), then $ A $ and $ B $ are non-negatively correlated, i.e. $ \mu ( A \cap B ) \geq \mu ( A ) \mu ( B ) $. The same is true if $ \prec = \prec _ {1} \cup \prec _ {2} $, where $ \prec _ {i} $ is a partial order on $ X _ {i} $.

Other inequalities which use two ordering relations on a fixed $ Y \subseteq X $ that are associated with $ \prec $ are in [a3], [a4], [a7], [a22], [a23]. One of these, [a3], shows that the plausible inequality

$$ \mu ( x < _ {0} y < _ {0} z < _ {0} w ) \leq \mu ( x < _ {0} y < _ {0} z ) \mu ( z < _ {0} w ) , $$

which is suggested by the non-strict rendering $ \mu ( x < _ {0} y < _ {0} z ) \leq \mu ( x < _ {0} y ) \mu ( y < _ {0} z ) $ of the Fishburn–Shepp inequality, can be contradicted whenever $ n \geq 5 $.

An inequality from percolation theory.

A final inequality comes from percolation theory [a20], [a21] and provides a nice contrast to the FKG inequality version $ | A | \cdot | B | \leq 2 ^ {n} | {A \cap B } | $ when $ A $ and $ B $ are up-sets in the family of subsets of $ \{ 1 \dots n \} $. For convenience, the subsets of $ \{ 1 \dots n \} $ are written in characteristic vector form, so that $ S = \{ 0, 1 \} ^ {n} $. The cylinder set determined by $ x \in S $ and $ K \subseteq \{ 1 \dots n \} $ is defined as

$$ c ( x, K ) = \left \{ {y \in S } : {y _ {j} = x _ {j} \textrm{ for all } j \in K } \right \} , $$

and the disjoint intersection of $ A, B \subseteq S $ is defined by

$$ A \square B = \left \{ {x \in S } : c ( x, K ) \subseteq A,\right . $$

$$ \left . c ( x, \{ 1 \dots n \} \setminus K ) \subseteq B \textrm{ for some } K \right \} . $$

The inequality, conjectured in [a20], [a21] and proved in [a15], is

$$ 2 ^ {n} \left | {A \square B } \right | \leq \left | A \right | \cdot \left | B \right | \textrm{ for all } A, B \subseteq S . $$

Thus, whereas some $ A, B \subseteq S $ are positively correlated by the usual definition based on $ A \cap B $, all $ A, B \subseteq S $ are "non-positively correlated" with respect to the disjoint intersection $ A \square B $.

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]	B. Bollobás, "Combinatorics" , Cambridge Univ. Press (1986)
[a3]	G.R. Brightwell, "Universal correlations in finite posets" Order , 2 (1985) pp. 129–144
[a4]	G.R. Brightwell, "Some correlation inequalities in finite posets" Order , 2 (1986) pp. 387–402
[a5]	D.E. Daykin, "A lattice is distributive if and only if " Nanta Math. , 10 (1977) pp. 58–60
[a6]	P.C. Fishburn, "A correlational inequality for linear extensions of a poset" Order , 1 (1984) pp. 127–137
[a7]	P.C. Fishburn, "Correlation in partially ordered sets" Discrete Appl. Math. , 39 (1992) pp. 173–191
[a8]	P.C. Fishburn, P.G. Doyle, L.A. Shepp, "The match set of a random permutation has the FKG property" Ann. of Probab. , 16 (1988) pp. 1194–1214
[a9]	C.M. Fortuin, P.N. Kasteleyn, J. Ginibre, "Correlation inequalities for some partially ordered sets" Comm. Math. Phys. , 22 (1971) pp. 89–103
[a10]	R.L. Graham, "Applications of the FKG inequality and its relatives" , Proc. 12th Internat. Symp. Math. Programming , Springer (1983) pp. 115–131
[a11]	R.L Graham, A.C. Yao, F.F. Yao, "Some monotonicity properties of partial orders" SIAM J. Alg. Discrete Methods , 1 (1980) pp. 251–258
[a12]	R. Holley, "Remarks on the FKG inequalities" Comm. Math. Phys. , 36 (1974) pp. 227–231
[a13]	D.J. Kleitman, "Families of non-disjoint sets" J. Combin. Th. , 1 (1966) pp. 153–155
[a14]	J. Marica, J. Schönheim, "Differences of sets and a problem of Graham" Canad. Math. Bull. , 12 (1969) pp. 635–637
[a15]	D. Reimer, in preparation (to appear)
[a16]	P.D. Seymour, "On incomparable collections of sets" Mathematika , 20 (1973) pp. 208–209
[a17]	L.A. Shepp, "The FKG property and some monotonicity properties of partial orders" SIAM J. Alg. Discrete Methods , 1 (1980) pp. 295–299
[a18]	L.A. Shepp, "The XYZ conjecture and the FKG inequality" Ann. of Probab. , 10 (1982) pp. 824–827
[a19]	R.F. Tate, "Correlation methods" W.H. Kruskal (ed.) J.M. Tanur (ed.) , Internat. Encycl. Stat. , 1 , Free Press (1978) pp. 615–628
[a20]	J. van der Berg, U. Fiebig, "On a combinatorial conjecture concerning disjoint occurrences of events" Ann. of Probab. , 15 (1987) pp. 354–374
[a21]	J. van der Berg, H. Kesten, "Inequalities with applications to percolation and reliability" J. Appl. Probab. , 22 (1985) pp. 556–569
[a22]	P.M. Winkler, "Correlation among partial orders" SIAM J. Alg. Discrete Methods , 4 (1983) pp. 1–7
[a23]	P M. Winkler, "Correlation and order" Contemp. Math. , 57 (1986) pp. 151–174