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 that are referred to as correlation inequalities. They are often stated deterministically but usually have probabilistic interpretations. For example, suppose is the family of all subsets of a finite set , and let and be order ideals or down-sets in : implies , implies , with . Then, [a13], [a16], . When is the uniform probability measure (cf. also Probability measure) on , so that for every , and , one has . Hence, with respect to , and are correlated whenever both are down-sets.
As general definitions, one says with respect to a probability measure on an algebra of subsets of that are positively correlated if and non-negatively correlated if . Inequality reversals define negative correlation and non-positive correlation, respectively. The instances of these inequalities and generalizations described below assume that is a finite set partially ordered by so that is irreflexive (never ) and transitive: and imply .
Inequalities for distributive lattices.
Let be a distributive lattice with join and meet defined by
Distributivity says that for all . A mapping is non-decreasing if implies for all , and is defined as for , with . The join and meet and can be extended to subsets by
with the understanding that if or is empty.
The pre-eminent correlation inequality is the Ahlswede–Daykin inequality [a1], also called the four-functions inequality [a2]. It says that if satisfy
then
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 cards numbered through . For each order, . Let and . When is the uniform distribution on the orders, . 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 is log supermodular, i.e.,
and if and are non-decreasing, then
This can be written in terms of the mathematical expectation operation as , when is a Boolean algebra and is a log supermodular probability measure with and . Suitable definitions of and with co-domains show that are non-negatively correlated when both are up-sets or order filters, given log supermodularity.
Another notable result is the Holley inequality [a12]. Suppose and satisfy along with the following inequality that generalizes log supermodularity and is itself generalized by the four-function Ahlswede–Daykin hypothesis:
Then the Holley inequality says that for every non-decreasing ,
Simple proofs of the FKG and Holley inequalities follow from the Ahlswede–Daykin inequality by suitable choices of through . Also, when for all , log supermodularity on implies log supermodularity on the subsets of ; when for all , one obtains for all , which is equivalent to distributivity [a5] for an ordered lattice .
Systems of subsets.
Several inequalities for when is the family of subsets of have already been given. Log supermodularity for a probability measure on is defined as for all , and when this holds, the FKG inequality says that for non-decreasing and and implies that for all . In addition, if and are down-sets or up-sets, then . When is uniform, in which case log supermodularity is automatic, if is an up-set and is a down-set, so the two are non-positively correlated when the complementary orientations obtain.
Another inequality involves set differences [a14]. Let for . Then , and, in particular, .
The match set of a permutation on is defined as . Assuming that all permutations are equally likely, let for be the probability that . Note that when and hence that is not log supermodular. However, there still is an FKG-like inequality [a8], because whenever 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 is the set of linear extensions of a finite partially ordered set and all members of are equally likely. is a linear extension of if is a partially ordered set, and, for all distinct , or . Let be the number of linear extensions of , so the probability law for is . By additivity, for each subset of linear extensions.
A premier correlation inequality in this setting is the Fishburn–Shepp inequality [a6], [a18], also known as the inequality. One says that are incomparable if and neither nor , and denotes by the set of all linear extensions of that satisfy the relations. The Fishburn–Shepp inequality says that if , and are mutually incomparable in , then
so events and are positively correlated. Rewritten as , one sees that the probability of in a randomly chosen linear extension increases when it is true also that . Examples in [a10], [a17], [a18] show that other plausible positive or non-negative correlations need not be true.
Inequalities involving two-part partitions of are featured in [a11], [a17]. Suppose is a non-trivial partition of . Let and for and . If the restriction of in to each is a linear order (cf. also Order (on a set)), then and are non-negatively correlated, i.e. . The same is true if , where is a partial order on .
Other inequalities which use two ordering relations on a fixed that are associated with are in [a3], [a4], [a7], [a22], [a23]. One of these, [a3], shows that the plausible inequality
which is suggested by the non-strict rendering of the Fishburn–Shepp inequality, can be contradicted whenever .
An inequality from percolation theory.
A final inequality comes from percolation theory [a20], [a21] and provides a nice contrast to the FKG inequality version when and are up-sets in the family of subsets of . For convenience, the subsets of are written in characteristic vector form, so that . The cylinder set determined by and is defined as
and the disjoint intersection of is defined by
The inequality, conjectured in [a20], [a21] and proved in [a15], is
Thus, whereas some are positively correlated by the usual definition based on , all are "non-positively correlated" with respect to the disjoint intersection .
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 |
Correlation inequalities. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Correlation_inequalities&oldid=13617