In mathematics, the Fortuin–Kasteleyn–Ginibre (FKG) inequality is a
correlation
In statistics, correlation or dependence is any statistical relationship, whether causal or not, between two random variables or bivariate data. Although in the broadest sense, "correlation" may indicate any type of association, in statisti ...
inequality, a fundamental tool in
statistical mechanics and
probabilistic combinatorics
The probabilistic method is a nonconstructive method, primarily used in combinatorics and pioneered by Paul Erdős, for proving the existence of a prescribed kind of mathematical object. It works by showing that if one randomly chooses objects fro ...
(especially
random graph
In mathematics, random graph is the general term to refer to probability distributions over graphs. Random graphs may be described simply by a probability distribution, or by a random process which generates them. The theory of random graphs ...
s and the
probabilistic method
The probabilistic method is a nonconstructive method, primarily used in combinatorics and pioneered by Paul Erdős, for proving the existence of a prescribed kind of mathematical object. It works by showing that if one randomly chooses objects fr ...
), 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
below
Below may refer to:
*Earth
* Ground (disambiguation)
* Soil
* Floor
* Bottom (disambiguation)
* Less than
*Temperatures below freezing
* Hell or underworld
People with the surname
* Ernst von Below (1863–1955), German World War I general
* Fr ...
. 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
be a finite
distributive lattice
In mathematics, a distributive lattice is a lattice in which the operations of join and meet distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice operations can be given by set ...
, 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
.
The FKG inequality then says that for any two monotonically increasing functions ''ƒ'' and ''g'' on
, 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
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
A cylinder (from ) has traditionally been a three-dimensional solid, one of the most basic of curvilinear geometric shapes. In elementary geometry, it is considered a prism with a circle as its base.
A cylinder may also be defined as an infi ...
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
A Markov chain or Markov process is a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. Informally, this may be thought of as, "What happen ...
coupling
A coupling is a device used to connect two shafts together at their ends for the purpose of transmitting power. The primary purpose of couplings is to join two pieces of rotating equipment while permitting some degree of misalignment or end mov ...
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
is
totally ordered
In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X:
# a \leq a ( reflexiv ...
, 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
and
, then
:
More generally, for any probability measure ''μ'' on
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,
, and
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
Ted Harris (mathematician), Harris , who found and used it in his study of
percolation
Percolation (from Latin ''percolare'', "to filter" or "trickle through"), in physics, chemistry and materials science, refers to the movement and filtering of fluids through porous materials.
It is described by Darcy's law.
Broader applicatio ...
in the plane. A proof of the Harris inequality that uses the above double integral trick on
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
The hexagonal lattice or triangular lattice is one of the five two-dimensional Bravais lattice types. The symmetry category of the lattice is wallpaper group p6m. The primitive translation vectors of the hexagonal lattice form an angle of 120° ...
black with probability
and white with probability
, independently of each other. Let ''a, b, c, d'' be four hexagons, not necessarily distinct. Let
and
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:
. 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
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
In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex ...
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
is an ordered set (such as
), and
is a finite or infinite
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
, then the set
of
-valued configurations is a
poset
In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary r ...
that is a distributive lattice.
Now, if
is a submodular
potential
Potential generally refers to a currently unrealized ability. The term is used in a wide variety of fields, from physics to the social sciences to indicate things that are in a state where they are able to change in ways ranging from the simple r ...
(i.e., a family of functions
:
one for each finite
, such that each
is
submodular), then one defines the corresponding
Hamiltonians as
:
If ''μ'' is an
extremal Gibbs measure for this Hamiltonian on the set of configurations
, then it is easy to show that ''μ'' satisfies the lattice condition, see .
A key example is the
Ising model
The Ising model () (or Lenz-Ising model or Ising-Lenz model), named after the physicists Ernst Ising and Wilhelm Lenz, is a mathematical model of ferromagnetism in statistical mechanics. The model consists of discrete variables that represent ...
on a graph
. Let
, called spins, and