Correlation inequality

As Korrelationsungleichungen a group of mathematical be inequalities referred to which the concept of positive correlation on partially ordered sets (Posets) and distributive associations transmitted. They also have a probabilistic interpretation and touch the mathematical sub-area of ​​the theory of stochastic orders .

The development was initiated by the FKG inequality from 1971, named after CM Fortuin, Jean Ginibre and PW Kasteleyn, which was used in a wide variety of areas, including statistical mechanics , particle systems , combinatorics and percolation theory . An earlier version of this inequality for independent and identically distributed random variables was proven by Theodore Edward Harris in 1960, but was initially not received by mathematicians from other disciplines and only became known through the publication of Fortuin, Kasteleyn and Ginibre. In this context, the term associated measure (also measure with positive correlations ) plays a role.

Based on the FKG inequalities, other similar inequalities were found, for example the Holley inequality according to Richard Holley in 1974, or the very general four-function inequality by Rudolf Ahlswede and David E. Daykin from 1978, from which the others named Inequalities follow.

Associated dimensions

The term associated measure was introduced in 1967 by JD Esary, Frank Proschan and DW Walkup. Because of the analogy to positive correlations of random variables, some authors also use the term measure with positive correlations.

A finite measure on , where a semi-ordered topological space is, is called associated , if ${\displaystyle \mu }$ ${\displaystyle (X,{\mathfrak {B}})}$ ${\displaystyle X}$

${\displaystyle \int fg\;\mathrm {d} \mu \geq \int f\mathrm {d} \mu \cdot \int g\mathrm {d} \mu }$

holds for all bounded, continuous, monotonically increasing functions from to . ${\displaystyle f,g}$ ${\displaystyle X}$ ${\displaystyle \mathbb {R} }$

The FKG inequality

The FKG inequality , named after CM Fortuin, J. Ginibre and PW Kasteleyn (1971), is originally a correlation inequality on distributive lattices . It is a fundamental tool in the fields of statistical mechanics and probabilistic combinatorics (especially in the field of random graphs .) Applied to a probabilistic setting, it says roughly that growing events are positively correlated with one another.

Formulation for finite distributive associations

Let be a finite distributive lattice, and a measure on which ${\displaystyle X}$ ${\displaystyle \mu }$ ${\displaystyle X}$

${\displaystyle \mu (\{x\wedge y\})\mu (\{x\vee y\})\geq \mu (\{x\})\mu (\{y\})}$

for everyone , fulfilled in association . This property is also called log supermodularity . ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle X}$

The FKG inequality says then that the measure is associated, so that for any two terms of induced by the lattice operations partially ordered continuous, monotonic, square integrable functions and of after valid that they are positively correlated: ${\displaystyle \mu }$ ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle X}$ ${\displaystyle \mathbb {R} }$

${\displaystyle \int fg\;\mathrm {d} \mu \geq \int f\mathrm {d} \mu \cdot \int g\mathrm {d} \mu }$.

There are also positive correlations between two functions and if the condition “monotonically increasing” is replaced by “monotonically decreasing”. If one function increases monotonically and the other decreases monotonically, then they are negatively correlated . Evidence can be found in the original work. ${\displaystyle f}$ ${\displaystyle g}$

A similar statement applies in the more general case that is a countable compact metric space. In this case, there must be a strictly positive finite measure and the log supermodularity must be defined via boundary events (cylinder sets). ${\displaystyle X}$ ${\displaystyle \mu }$

Further formulations

In Rinott, Saks there is the proof for a form of the FKG inequality for -finite measures on the (uncountable) set . In this case, the log supermodularity of a measure is defined via the density function (with respect to any product measure ), which must satisfy for all : ${\displaystyle \sigma }$ ${\displaystyle \mathbb {R} ^{d}}$ ${\displaystyle \varphi }$ ${\displaystyle \mathbb {R} ^{d}}$ ${\displaystyle x,y\in \mathbb {R} ^{d}}$

${\displaystyle \varphi (x)\varphi (y)\leq \varphi (x\wedge y)\varphi (x\vee y)}$.

The Griffith inequality is another inequality from 1967, which makes the same statement as the FKG inequality, but has different requirements and is used in the field of the Ising model .

The Harris Inequality

The Harris inequality is basically the FKG inequality for product dimensions, named after Theodore E. Harris , who found it in 1960 while studying percolations in the plane.

If a totally ordered amount, then the log supermodularity automatically for each measure to met. ${\displaystyle X}$ ${\displaystyle \mu }$ ${\displaystyle X}$

It holds, for example, that for every probability distribution on , and monotonically increasing square integrable functions and ${\displaystyle \mu }$ ${\displaystyle \mathbb {R} }$ ${\displaystyle f}$ ${\displaystyle g}$

${\displaystyle \int _{\mathbb {R} }f(x)g(x)\,d\mu (x)\geq \int _{\mathbb {R} }f(x)\,d\mu (x)\,\int _{\mathbb {R} }g(x)\,d\mu (x),}$

applies. This follows from

${\displaystyle \int _{\mathbb {R} }\int _{\mathbb {R} }[f(x)-f(y)][g(x)-g(y)]\,d\mu (x)\,d\mu (y)\geq 0}$

(the terms in the square brackets have the same sign .)

The log supermodularity is also automatically fulfilled if the lattice is a product of totally ordered lattices , and a product measure . The (product) distribution of independently and identically distributed random variables on independent copies of a probability space is often used . ${\displaystyle X=X_{1}\times \dots \times X_{n}}$ ${\displaystyle \mu =\mu _{1}\otimes \dots \otimes \mu _{n}}$ ${\displaystyle X}$ ${\displaystyle \mu }$ ${\displaystyle X_{i}}$

Let be a finite index set. Be provided with the coordinate order and with the association operations: ${\displaystyle E}$ ${\displaystyle X=\prod _{e\in E}\{0,1\}}$ ${\displaystyle \leq }$

${\displaystyle \xi \vee \eta }$be for all , defined by , ${\displaystyle \xi ,\eta \in X}$ ${\displaystyle e\in E}$ ${\displaystyle \xi (e)\vee \eta (e):=\max\{\xi (e),\eta (e)\}}$

as well as over . ${\displaystyle \xi \wedge \eta }$ ${\displaystyle \xi (e)\wedge \eta (e):=\min\{\xi (e),\eta (e)\}}$

With these operations is a Boolean algebra. ${\displaystyle X}$

Be a probability measure on . Then the FKG inequality is written ${\displaystyle \mu }$ ${\displaystyle (X,\wp (X))}$

${\displaystyle \mathbf {E} _{\mu }fg\geq (\mathbf {E} _{\mu }f)(\mathbf {E} _{\mu }g)}$

for all monotonically growing for which the expected values ​​exist, where denotes the expected value with . ${\displaystyle f,g}$ ${\displaystyle \mathbf {E} _{\mu }}$ ${\displaystyle \mu }$

An event is called growing accordingly if for everyone with it . (And an event is called decreasing when the complement is increasing.) ${\displaystyle A\in \wp (X)}$ ${\displaystyle \mathbb {I} _{A}(x)\leq \mathbb {I} _{A}(y)}$ ${\displaystyle x,y\in X}$ ${\displaystyle x\leq y}$ ${\displaystyle \Omega \setminus A}$

If and are increasing events, then it holds ${\displaystyle A}$ ${\displaystyle B}$

${\displaystyle \mathbf {P} _{\mu }(A\cap B)\geq \mathbf {P} _{\mu }(A)\mathbf {P} _{\mu }(B).}$

A proof of the Harris inequality based on the double integral trick used here can be found in Grimmett 1999. ${\displaystyle \{0,1\}}$

Examples

Honeycomb grid with randomly colored honeycombs.

You randomly color every hexagon of the infinite honeycomb lattice black, each stochastically independent of one another with probability and white with probability . Let there be four (not necessarily different) such hexagons. Be and the events that there is a black path from to and from to , respectively . Then the FKG inequality says that these events are positively correlated :: . In other words, assuming that one black path already exists, the other path becomes more likely to exist. ${\displaystyle p}$ ${\displaystyle 1-p}$ ${\displaystyle A,B,X,Y}$ ${\displaystyle A\leftrightarrow B}$ ${\displaystyle X\leftrightarrow Y}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle \mathbf {P} (A\leftrightarrow B,\ X\leftrightarrow Y)\geq \mathbf {P} (A\leftrightarrow B)\mathbf {P} (X\leftrightarrow Y)}$

In the Erdős-Rényi random graph , the existence of a Hamilton cycle is negatively correlated with the 3-colorability of the graph , since the probability of the existence of a Hamilton cycle increases with the number of occupied connections (increasing event), while the probability of the latter decreases (falling event).

The Holley inequality

This inequality , discovered by Richard Holley in 1974 and sometimes referred to as the Holley inequality , states: Let and two be strictly positive distributions on a finite distributive lattice , which ${\displaystyle \mu _{1}}$ ${\displaystyle \mu _{2}}$ ${\displaystyle X}$

${\displaystyle \mu _{1}(\{x\wedge y\})\mu _{2}(\{x\vee y\})\geq \mu _{1}(\{x\})\mu _{2}(y\})}$ for all ${\displaystyle x,y\in X}$

fulfill. Then applies

${\displaystyle \int f\;\mathrm {d} \mu _{2}\geq \int f\;\mathrm {d} \mu _{1}}$.

for all monotonic integrable functions to . This is equivalent to saying that is greater than with respect to the ordinary stochastic order . Thomas Liggett has a proof for spaces of form , which is based on the coupling of two Markov chains in continuous time with and as stationary distributions. It also indicates how the proof could be extended to countable product spaces. The FKG inequality can be deduced from the Holley inequality by clever insertion. ${\displaystyle f}$ ${\displaystyle X}$ ${\displaystyle \mu _{2}}$ ${\displaystyle \mu _{1}}$ ${\displaystyle \Omega =\prod _{s\in S}\{0,1\}}$ ${\displaystyle \mu _{1}}$ ${\displaystyle \mu _{2}}$

Alternative requirement for the FKG inequality

Be provided with the coordinate-wise partial order. For a distribution to , the following property is often easier to check than the log supermodularity: ${\displaystyle \mathbb {R} ^{d}}$ ${\displaystyle \mu }$ ${\displaystyle \mathbb {R} ^{d}}$

Fixed to a coordinate and two configurations , and in so that with respect to the other coordinate for all , on the conditional distribution of given is stochastic greater than that on conditional distribution of given . ${\displaystyle i\in \{1,\dots ,d\}}$ ${\displaystyle \varphi }$ ${\displaystyle \psi }$ ${\displaystyle \mathbb {R} ^{d}}$ ${\displaystyle \varphi _{j}\geq \psi _{j}}$ ${\displaystyle w\not =v}$ ${\displaystyle \mu }$ ${\displaystyle \varphi _{i}}$ ${\displaystyle \{\varphi (j):j\not =i\}}$ ${\displaystyle \mu }$ ${\displaystyle \psi }$ ${\displaystyle \{\psi _{j}:j\not =i\}}$

If this quality is fulfilled , then it is associated. ${\displaystyle \mu }$ ${\displaystyle \mu }$

The four function inequality

The four-function inequality of Ahlswede and Daykin from 1978 can be formulated as follows: Let non-negative real-valued functions meet the following condition: ${\displaystyle f_{1},f_{2},g_{1},g_{2}}$ ${\displaystyle \mathbb {R} ^{d}}$

${\displaystyle f_{1}(x)f_{2}(y)\leq g_{1}(x\vee y)g_{2}(x\wedge y)}$ for all ${\displaystyle x,y}$

Then for every log-supermodular measure on , ${\displaystyle \mu }$ ${\displaystyle \mathbb {R} ^{d}}$

${\displaystyle \int _{\mathbb {R} ^{d}}f_{1}(x)\mathrm {d} \mu (x)\int _{\mathbb {R} ^{d}}f_{2}(x)\mathrm {d} \mu (x)\leq \int _{\mathbb {R} ^{d}}g_{1}(x)\mathrm {d} \mu (x)\int _{\mathbb {R} ^{d}}g_{2}(x)\mathrm {d} \mu (x)}$

It can be shown that Holley's inequality follows from the four-function inequality, which in turn leads to the FKG inequality.

Individual evidence

1. ↑ Rinott and Saks, p. 332.
2. ↑ Grimmet, p. 11.
3. ↑ Fortuin, Kasteleyn, Ginibre, 1971, p. 89.
4. ↑ Müller, Stoyan, p. 122.
5. ↑ Where the partial order and topology are compatible , i.e. H. be finished. This is the case for discrete rooms. ${\displaystyle \{(x,y)\in X\times X\colon x\leq y\}}$
6. ^ Liggett, p. 79.
7. ^ Fortuin, Kasteleyn and Ginibre, p. 89.
8. ↑ Harris, pp. 13-20.
9. ^ Fishburn: FKG inequality.
10. ↑ Liggett, p. 77.
11. ^ Liggett, p. 79.
12. ↑ Rinott and Saks, p. 333.

literature

• CM Fortuin, PW Kasteleyn, J. Ginibre: Correlation inequalities on some partially ordered sets. In: Comm. Math. Phys. No. 22, 1971, MR0309498, ISSN  0010-3616 , pp. 89-103.
• PC Fishburn: FKG inequality . In: Michiel Hazewinkel (Ed.): Encyclopaedia of Mathematics, Kluwer Academic Publishers , 2001, ISBN 978-1-55608-010-4 .
• PC Fishburn: Correlation inequalities . In: Michiel Hazewinkel (Ed.): Encyclopaedia of Mathematics, Kluwer Academic Publishers , 2001, ISBN 978-1-55608-010-4 .
• H.-O. Georgii, O. Haggstrom, C. Maes: The random geometry of equilibrium phases . In: Phase transitions and critical phenomena . No. 18, 2001, Academic Press, San Diego, CA, MR2014387, pp. 1-142.
• GR Grimmett: Percolation. Second edition . Springer-Verlag, New York 1999, MR1707339, ISBN 3-540-64902-6 .
• TE Harris: A lower bound for the critical probability in a certain percolation . In: Proceedings of the Cambridge Philosophical Society , No. 56, 1960, MR0115221, pp. 13-20.
• R. Holley: Remarks on the FKG inequalities . In: Communications in Mathematical Physics No. 36, 1974, MR0341552, ISSN  0010-3616 , pp. 227-231.
• Thomas M. Liggett: Interacting Particle Systems . Springer-Verlag, New York, 1985. ISBN 3-540-96069-4 .
• R. Lyons: Phase transitions on nonamenable graphs In: J. Math. Phys. No. 41, 2000, MR1757952, pp. 1099-1126.
• S. Sheffield: Random surfaces . In: Asterisque , No. 304, 2005, MR2251117.
• A. Müller and D. Stoyan: Comparison Methods for Stochastic Models and Risk . Wiley, Chichester, 2002.
• Yosef Rinott, Michael Saks: On FKG-type and permanent inequalities . In: Moshe Shaked, YL Tong (Ed.): Stochastic inequalities: Papers from the AMS-IMS-SIAM Joint Summer Research Conference held in Seattle, Washington . July 1991 (Hayward, CA: Institute of Mathematical Statistics, 1992), ISBN 0-940600-29-3 , ISBN 978-0-940600-29-4 , 332-342, MR1228073.