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