FKG inequality

The FKG inequality gives positive association under a log-supermodular probability measure on a finite distributive lattice.

This lattice condition on configuration masses is the hypothesis of the FKG inequality. A product measure on a finite Boolean lattice satisfies it with equality, since in each coordinate the minimum and maximum retain the original two coordinate values. It implies positive association of random variables for increasing functions.

For a strictly positive law $\mu$ satisfying the FKG lattice condition on a finite Boolean lattice, and an increasing function $g$, tilt to ${\mu }_t(\omega )\propto e^{tg(\omega )}\mu (\omega )$. For $t\ge 0$, the lattice inequality and $g(\omega \vee \eta )\ge g(\omega )$ give the Holley condition for ${\mu }_t{\ge }_{\mathrm{st}}\mu$. For any increasing $f$, differentiate ${\mathbb{E}}_{{\mu }_t}f\ge {\mathbb{E}}_{\mu }f$ at $t=0$ from the right. The derivative is ${\mathrm{Cov}}_{\mu }(f,g)$, proving positive association of random variables.

Increasing events under a product probability measure are positively associated: $\mathbb{P}(A\cap B)\ge \mathbb{P}(A)\mathbb{P}(B)$.

For two increasing events of equal probability $a$ under a product measure, positive association of their complements gives $1-P(A\cup B)\ge (1-a{)}^2$. Hence $a\ge 1-\sqrt{1-P(A\cup B)}$. For $r$ equal-probability increasing events, the same reasoning gives $a\ge 1-(1-P({\bigcup }_j{A}_j){)}^{1/r}$.

If increasing events $A_1,\dots ,A_k$ have a common probability, applying the Harris-FKG inequality to their decreasing complements gives $\mathbb{P}(A_1)\ge 1-(1-\mathbb{P}({\bigcup }_i{A}_i){)}^{1/k}$.

Harris' inequality states that two increasing events under an independent Bernoulli product measure are positively correlated.

Under a product measure on a finite Boolean lattice, an increasing event $E$ and a decreasing event $G$ obey the displayed inequality. The complement $G^c$ is an increasing event, so Harris' inequality gives $\mathbb{P}(E\cap G^c)\ge \mathbb{P}(E)\mathbb{P}(G^c)$. Subtract from $\mathbb{P}(E)$ to obtain the result. This implication includes degenerate Bernoulli distribution parameters $0$ and $1$.

An event in a partially ordered configuration space is increasing when changing coordinates upward cannot make a configuration leave the event.

For a sequence of nontrivial increasing events on finite product measures, write $p_x$ for the parameter at which the success probability is $x$. An additive sharp threshold means that $p_{1-\epsilon }-p_{\epsilon }\to 0$ for every fixed $0<\epsilon <1/2$. When the threshold parameter itself tends to zero, relative sharpness instead compares this window with $p_{1/2}$; additive sharpness alone is then a weaker assertion. The Friedgut-Kalai sharp threshold theorem provides an explicit additive bound for transitive increasing events.

An increasing event on a finite product of identically distributed coordinates is transitive if a group action preserving the event is transitive on the coordinate set. Its influences are all equal. Transitivity concerns coordinates, and does not assert transitivity on successful configurations.

An event is decreasing when closing additional edges cannot destroy it. Its complement is an increasing event.