FKG inequality
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 . Informally, it says that in many random systems, increasing events are positively correlated, while an increasing and a decreasing event are negatively correlated. It was obtained by studying the random cluster model. An earlier version, for the special case of i.i.d. variables, called Harris inequality, is due to , see . One generalization of the FKG inequality is the 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 formula_1 be a finite distributive lattice, and "μ" a nonnegative function on it, that is assumed to satisfy the (FKG) lattice condition (sometimes a function satisfying this condition is called log supermodular) i.e., for all "x", "y" in the lattice formula_1. The FKG inequality then says that for any two monotonically increasing functions "ƒ" and "g" on formula_1, the following positive correlation inequality holds: 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 formula_1 is not necessarily finite, not even countable. 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 . For proofs, see or the Ahlswede–Daykin inequality (1978). Also, a rough sketch is given below, due to , 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 formula_1 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 formula_8  and formula_9, then More generally, for any probability measure "μ" on formula_11 and increasing functions "ƒ" and "g", which follows immediately from The lattice condition is trivially satisfied also when the lattice is the product of totally ordered lattices, formula_14, and formula_15 is a product measure. Often all the factors (both the lattices and the measures) are identical, i.e., "μ" is the probability distribution of i.i.d. random variables. The FKG inequality for the case of a product measure is known also as the Harris inequality after Harris , 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 formula_11 can be found, e.g., in Section 2.2 of . Simple examples. A typical example is the following. Color each hexagon of the infinite honeycomb lattice black with probability formula_17 and white with probability formula_18, independently of each other. Let "a, b, c, d" be four hexagons, not necessarily distinct. Let formula_19 and formula_20 be the events that there is a black path from "a" to "b", and a black path from "c" to "d", respectively. Then the Harris inequality says that these events are positively correlated : formula_21. In other words, assuming the presence of one path can only increase the probability of the other. Similarly, if we randomly color the hexagons inside an formula_22 rhombus-shaped hex board, then the events that there is black crossing from the left side of the board to the right side is positively correlated with having a black crossing from the top side to the bottom. 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 fact, in any coloring of the hex board exactly one of these two events happen — this is why hex is a well-defined game. 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 formula_23 is an ordered set (such as formula_24), and formula_25  is a finite or infinite graph, then the set formula_26 of formula_23-valued configurations is a poset that is a distributive lattice. Now, if formula_28 is a submodular potential (i.e., a family of functions one for each finite formula_30, such that each formula_31 is submodular), then one defines the corresponding Hamiltonians as If "μ" is an extremal Gibbs measure for this Hamiltonian on the set of configurations formula_33, then it is easy to show that "μ" satisfies the lattice condition, see . A key example is the Ising model on a graph formula_25. Let formula_35, called spins, and formula_36. 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. Then, depending on the graph formula_25 and the value of formula_39, there could be one or more extremal Gibbs measures, see, e.g., and . A generalization: the Holley inequality. The Holley inequality, due to , states that the expectations of a monotonically increasing function "ƒ" on a finite distributive lattice formula_1 with respect to two positive functions "μ", "μ" 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 formula_1, then "μ"("x") = "g"("x")"μ"("x") and "μ"("x") = "μ"("x") will satisfy the lattice-type condition of the Holley inequality. Then the Holley inequality states that 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 formula_1 being a product formula_47 for some finite set formula_48. 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 formula_49 and two configurations "φ" and "ψ" outside "v" such that formula_50 for all formula_51, the "μ"-conditional distribution of "φ"("v") given formula_52 stochastically dominates the "μ"-conditional distribution of "ψ"("v") given formula_53. 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 : starting from any initial configuration on formula_48, 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 implies that it has positive associations. Therefore, the limiting stationary measure "μ" also has this property. The monotonicity property has a natural version for two measures, saying that "μ" conditionally pointwise dominates "μ". It is again easy to see that if "μ" and "μ" satisfy the lattice-type condition of the , then "μ" conditionally pointwise dominates "μ". 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 formula_55 for all increasing "ƒ", thus we get a proof of the Holley inequality. (And thus also a proof of the FKG inequality, without using the Harris inequality.) See and for details.