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|\ge |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)\ge \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)\ge \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.[edit]

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

$$a\vee b=min\{z\in S:a\text{cle}z,b\text{cle}z\},$$

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

Distributivity says that $a\wedge (b\vee c)=(a\wedge b)\vee (a\wedge c)$ for all $a,b,c\in S$. A mapping $f:S\to \mathbf{R}$ is non-decreasing if $a\prec b$ implies $f(a)\le 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(\mathrm{\varnothing })=0$. The join and meet $\vee$ and $\wedge$ can be extended to subsets $A,B\subseteq S$ by

$$A\vee B=\{a\vee b:a\in A,b\in B\},$$

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

with the understanding that $A\vee B=A\wedge B=\mathrm{\varnothing }$ 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\to [0,\mathrm{\infty })$ satisfy

$$f_1(a)f_2(b)\le f_3(a\vee b)f_4(a\wedge b)\text{ for all }a,b\in S,$$

then

$$f_1(A)f_2(B)\le f_3(A\vee B)f_4(A\wedge B)\text{ 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:\text{ card }k\text{ is the }k\text{ th card at the top of the deck }\}$. Let $A=\{M:\text{ an even }k\in M\}$ and $B=\{M:\text{ an odd }k\in M\}$. When $\mu$ is the uniform distribution on the $52!$ orders, $\mu (A\cap B)\ge \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\to [0,\mathrm{\infty })$ is log supermodular, i.e.,

$$\eta (a)\eta (b)\le \eta (a\vee b)\eta (a\wedge b)\text{ for all }a,b\in S,$$

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

$$[\sum _S\eta (a)f(a)][\sum _S\eta (a)g(a)]\le$$

$$\le [\sum _S\eta (a)][\sum _S\eta (a)f(a)g(a)].$$

This can be written in terms of the mathematical expectation operation ${\mathsf{E}}_{\eta }$ as ${\mathsf{E}}_{\eta }(f){\mathsf{E}}_{\eta }(g)\le {\mathsf{E}}_{\eta }(fg)$, when $S$ is a Boolean algebra and $\eta$ is a log supermodular probability measure with $\vee =\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\to [0,\mathrm{\infty })$ and ${\eta }_2:S\to [0,\mathrm{\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)\le {\eta }_1(a\vee b){\eta }_2(a\wedge b)\text{ for all }a,b\in S.$$

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

$$\sum _{S}f(a){\eta }_1(a)\ge \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|\le |A\vee 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.[edit]

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)\le \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)\le {\mathsf{E}}_{\mu }(fg)$ for non-decreasing $f:S\to \mathbf{R}$ and $g:S\to \mathbf{R}$ and implies that $\mu (A)\mu (B)\le \mu (A\vee 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)\ge \mu (A)\mu (B)$. When $\mu$ is uniform, in which case log supermodularity is automatic, $2^n|A\cap B|\le |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|\ge |A|\cdot |B|$, and, in particular, $|A-A|\ge |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)\ge \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.[edit]

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\ne 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)\ge \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)\le \mu (x{<}_{0}y{<}_{0}z)\mu (z{<}_{0}w),$$

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

An inequality from percolation theory.[edit]

A final inequality comes from percolation theory [a20], [a21] and provides a nice contrast to the FKG inequality version $|A|\cdot |B|\le 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)=\{y\in S:y_j=x_j\text{ for all }j\in K\},$$

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

$$A◻B=\{x\in S:c(x,K)\subseteq A,$$

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

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

$$2^n\left|A◻B\right|\le \left|A\right|\cdot \left|B\right|\text{ 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◻B$.

References[edit]