In mathematics, the Fortuin–Kasteleyn–Ginibre (FKG) inequality is a correlation inequality, a fundamental tool in statistical mechanics and probabilistic combinatorics (especially random graphs and the probabilistic method), due to Cees M. Fortuin, Pieter W. Kasteleyn, and Jean Ginibre (1971). Informally, it says that in many random systems, increasing events are positively correlated, while an increasing and a decreasing event are negatively correlated.
Contents
- The inequality
- Variations on terminology
- A special case the Harris inequality
- Simple examples
- Examples from Statistical Mechanics
- A generalization the Holley inequality
- Weakening the lattice condition monotonicity
- References
An earlier version, for the special case of i.i.d. variables, called Harris inequality, is due to Theodore Edward Harris (1960), see below. One generalization of the FKG inequality is the Holley inequality (1974) below, and an even further generalization is the Ahlswede–Daykin "four functions" theorem (1978). Furthermore, it has the same conclusion as the Griffiths inequalities, but the hypotheses are different.
The inequality
Let
for all x, y in the lattice
The FKG inequality then says that for any two monotonically increasing functions ƒ and g on
The same inequality (positive correlation) is true when both ƒ and g are decreasing. If one is increasing and the other is decreasing, then they are negatively correlated and the above inequality is reversed.
Similar statements hold more generally, when
For proofs, see the original Fortuin, Kasteleyn & Ginibre (1971) or the Ahlswede–Daykin inequality (1978). Also, a rough sketch is given below, due to Holley (1974), using a Markov chain coupling argument.
Variations on terminology
The lattice condition for μ is also called multivariate total positivity, and sometimes the strong FKG condition; the term (multiplicative) FKG condition is also used in older literature.
The property of μ that increasing functions are positively correlated is also called having positive associations, or the weak FKG condition.
Thus, the FKG theorem can be rephrased as "the strong FKG condition implies the weak FKG condition".
A special case: the Harris inequality
If the lattice
More generally, for any probability measure μ on
which follows immediately from
The lattice condition is trivially satisfied also when the lattice is the product of totally ordered lattices,
The FKG inequality for the case of a product measure is known also as the Harris inequality after Harris (Harris 1960), who found and used it in his study of percolation in the plane. A proof of the Harris inequality that uses the above double integral trick on
Simple examples
A typical example is the following. Color each hexagon of the infinite honeycomb lattice black with probability
Similarly, if we randomly color the hexagons inside an
In the Erdős–Rényi random graph, the existence of a Hamiltonian cycle is negatively correlated with the 3-colorability of the graph, since the first is an increasing event, while the latter is decreasing.
Examples from Statistical Mechanics
In statistical mechanics, the usual source of measures that satisfy the lattice condition (and hence the FKG inequality) is the following:
If
Now, if
one for each finite
If μ is an extremal Gibbs measure for this Hamiltonian on the set of configurations
A key example is the Ising model on a graph
Submodularity is easy to check; intuitively, taking the min or the max of two configurations tends to decrease the number of disagreeing spins. Then, depending on the graph
A generalization: the Holley inequality
The Holley inequality, due to Richard Holley (1974), states that the expectations
of a monotonically increasing function ƒ on a finite distributive lattice
provided the functions satisfy the Holley condition (criterion)
for all x, y in the lattice.
To recover the FKG inequality: If μ satisfies the lattice condition and ƒ and g are increasing functions on
which is just the FKG inequality.
As for FKG, the Holley inequality follows from the Ahlswede–Daykin inequality.
Weakening the lattice condition: monotonicity
Consider the usual case of
Whenever one fixes a vertex
Now, if μ satisfies this monotonicity property, that is already enough for the FKG inequality (positive associations) to hold.
Here is a rough sketch of the proof, due to Holley (1974): starting from any initial configuration on
The monotonicity property has a natural version for two measures, saying that μ1 conditionally pointwise dominates μ2. It is again easy to see that if μ1 and μ2 satisfy the lattice-type condition of the Holley inequality, then μ1 conditionally pointwise dominates μ2. On the other hand, a Markov chain coupling argument similar to the above, but now without invoking the Harris inequality, shows that conditional pointwise domination, in fact, implies stochastically domination. Stochastic domination is equivalent to saying that
See Holley (1974) and Georgii, Häggström & Maes (2001) for details.