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 ![]() |
[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