FKG inequality
As Korrelationsungleichungen a group designated by mathematical inequalities, which transfer the notion of positive correlation on partially ordered sets ( posets ) and distributive lattices. They also have a probabilistic interpretation and touch the mathematical subfield of theory of stochastic orders.
The development was initiated by the FKG inequality from 1971, named after CM Fortuin, Jean Ginibre and Kasteleyn PW, which has found application in various fields, including in the fields of statistical mechanics, particle systems, combinatorics and percolation theory. An earlier version of this inequality for independent and identically distributed random variables was proved in 1960 by Theodore Edward Harris, however, was initially not rezipiert of mathematicians from other disciplines, and only through the publication of Fortuin, Kasteleyn and Ginibre known. In this context, the term of the associated measure ( even degree with positive correlations) plays a role.
Based on the FKG inequalities other inequalities have been found, for example, the Holley inequality by Richard Holley in 1974, or the very general four-function inequality of Rudolf Ahlswede and David E. Daykin of 1978, called from the other follow inequalities.
- 3.1 Examples
Associated Dimensions
The term of the associated measure was introduced by JD Esary, Frank Proschan and DW Walkup 1967. Because of the analogy to positive correlations of random variables, some authors the term used measure with positive correlations.
A finite measure on, where a partially ordered topological space is called associated if
For all bounded, continuous, monotonically increasing functions applies from to.
The FKG inequality
The FKG inequality, named after CM Fortuin, J. Ginibre and Kasteleyn PW (1971 ) is originally a Korrelationsungleichung on distributive associations. It is a fundamental tool in the fields of statistical mechanics and probabilistic combinatorics (especially in the field of random graphs. ) It says transferred to a probabilistic setting in about that growing events are positively correlated with each other.
Formulation for finite distributive lattices
Be a finite distributive lattice, and is a measure on which
, met for all of the association. This property is also called log - supermodularity.
The FKG inequality then states that the measure is associated, so that for any two respect to the induced by the lattice operations partial order continuous, monotonically increasing, square integrable functions and is regarded by after that they are positively correlated:
Also correlated positively are two functions and when the condition " monotonically increasing " is replaced by " monotonically decreasing ". Is that a function is monotonically increasing, the other monotonically decreasing, then they are negatively correlated. A proof is in the original paper.
A similar statement holds in the more general case that a countable compact metric space. In this case, a strictly positive finite measure must be and the log - supermodularity must be defined via edge events ( cylinder sets ).
Additional formulations
In Rinott, Saks there is evidence of a form of FKG - inequality for finite - extent on the ( uncountable ) set. In this case, log - supermodularity a measure of the density function ( with respect to any product measure on ) is defined, which must meet for all:
The Griffith 's inequality is another inequality from 1967, which makes the same statement as the FKG inequality, however, has different requirements and has application in the field of the Ising model.
The Harris 's inequality
The Harris 's inequality is basically the FKG - inequality for product measures, named after TE Harris, which she has found in 1960 in the study of percolations in the plane.
If a totally ordered set, then the log - supermodularity is automatically satisfied for each measure on.
It is, for example, that for each of the probability distribution, and monotone increasing square integrable functions, and
Applies. This follows from
( the terms in square brackets in each case have the same sign. )
The log - supermodularity is satisfied automatically if the association is a product totally ordered associations, and a product measure on. In use is often the (product) distribution of independent and identically distributed random variables independent copies of a probability space.
Let be a finite index set. Be provided with the coordinate- wise order and with the association operations:
With these operations is a Boolean algebra.
Be a probability measure on. Then the FKG inequality writes
For all monotonically increasing for the expected values exist, where the expectation value with respect to call.
An event is, accordingly increasing if for all with. ( And an event is called decreasing if the complement is growing. )
Are growing and events, it shall
A proof of the Harris inequality, which is based on the double integral trick to use here can be found in Grimmett 1999.
Examples
You dyeing randomly each hexagon of the infinite honeycomb lattice black each stochastically independently with probability and white with probability. Be four (not necessarily distinct ) such hexagons. Be and the events that there is a black path from to, respectively, from to. Then says the FKG inequality that these events are positive correlated. :: In other words, it is assumed that there are even a black path, the existence of the other path is likely.
In Erdős Renyi random graph, the existence of a Hamiltonian cycle is negatively correlated with the 3- dyeability of the graph, as the probability of the existence of a Hamiltonian cycle with the number of used connections increases (increasing event) while the probability of the latter falls (dropping event).
The Holley 's inequality
This was discovered in 1974 by Richard Holley and occasionally referred to as Holley 's inequality implies inequality: Let and be two strictly positive distributions on a finite distributive lattice, which
. meet Then we have
For all monotonically increasing on integrable functions. This is equivalent to saying that respect is greater than the usual stochastic order. Thomas Liggett has a proof for spaces of the form, which is based on the coupling of two Markov chains in continuous time with and as stationary distributions. It indicates furthermore, as the proof would be to expand on countable product spaces. From the Holley inequality, the FKG inequality can be inferred by clever insertion.
Alternative condition for the FKG inequality
Be provided with the coordinate- wise partial order. For a distribution on the following property is often easier to check than the log - supermodularity:
Complies with this property, then it is associated.
The four-function inequality
The four-function inequality by Ahlswede and Daykin of 1978 can be formulated as follows: Be non-negative real-valued functions that satisfy the following condition:
Then on each log -super modular degree,
It can be shown that from the four-function inequality follows Holley's inequality, which in turn follows from the FKG inequality.