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.
The FKG inequality then says that for any two monotonically increasing functions ƒ and g on
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, including when the set underlying
is not necessarily finite or countable (though it must be bounded and totally ordered).
In that case, μ has to be a finite measure, and the lattice condition has to be defined using cylinder events; see, e.g., Section 2.2 of Grimmett (1999).
Also, a rough sketch is given below, due to Holley (1974), using a Markov chain coupling argument.
, and note that from our hypothesis we have that Taking expected value and factoring concludes the proof.
is totally ordered, then the lattice condition is satisfied trivially for any measure μ.
In case the measure μ is uniform, the FKG inequality is Chebyshev's sum inequality: if the two increasing functions take on values
Often all the factors (both the lattices and the measures) are identical, i.e., μ is the probability distribution of i.i.d.
A proof of the Harris inequality that uses the above double integral trick on
Color each hexagon of the infinite honeycomb lattice black with probability
In other words, assuming the presence of one path can only increase the probability of the other.
On the other hand, having a left-to-right black crossing is negatively correlated with having a top-to-bottom white crossing, since the first is an increasing event (in the amount of blackness), while the second is decreasing.
In statistical mechanics, the usual source of measures that satisfy the lattice condition (and hence the FKG inequality) is the following: If
, then it is easy to show that μ satisfies the lattice condition, see Sheffield (2005).
Take the following potential: Submodularity is easy to check; intuitively, taking the min or the max of two configurations tends to decrease the number of disagreeing spins.
, there could be one or more extremal Gibbs measures, see, e.g., Georgii, Häggström & Maes (2001) and Lyons (2000).
The Holley inequality, due to Richard Holley (1974), states that the expectations of a monotonically increasing function ƒ on a finite distributive lattice
with respect to two positive functions μ1, μ2 on the lattice satisfy the condition 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
The lattice condition on μ is easily seen to imply the following monotonicity, which has the virtue that it is often easier to check than the lattice condition: 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[clarification needed] on
, one can run a simple Markov chain (the Metropolis algorithm) that uses independent Uniform[0,1] random variables to update the configuration in each step, such that the chain has a unique stationary measure, the given μ.
The monotonicity of μ implies that the configuration at each step is a monotone function of independent variables, hence the product measure version of Harris implies that it has positive associations.
The monotonicity property has a natural version for two measures, saying that μ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.