Namespaces
Variants
Actions

Correlation inequalities

From Encyclopedia of Mathematics
Jump to: navigation, search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.


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 $|A||B|\leq|A \wedge B||A \vee B|$" 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, "Proof of the van den Berg-Kesten conjecture". Comb. Probab. Comput. 9, No. 1, pp. 27-32 (2000). Zbl 0947.60093
[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
How to Cite This Entry:
Correlation inequalities. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Correlation_inequalities&oldid=54764
This article was adapted from an original article by P.C. Fishburn (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article