Van den Berg–Kesten inequality

Coin tosses

If ${\displaystyle \Omega }$ corresponds to tossing a fair coin ${\displaystyle n=10}$ times, then each ${\displaystyle \Omega _{i}=\{H,T\}}$ consists of the two possible outcomes, heads or tails, with equal probability. Consider the event ${\displaystyle A}$ that there exists 3 consecutive heads, and the event ${\displaystyle B}$ that there are at least 5 heads in total. Then ${\displaystyle A\mathbin {\square } B}$ would be the following event: there are 3 consecutive heads, and discarding those there are another 5 heads remaining. This event has probability at most ${\displaystyle \mathbb {P} (A)\mathbb {P} (B),}$^[4]: 42 which is to say the probability of getting ${\displaystyle A}$ in 10 tosses, and getting ${\displaystyle B}$ in another 10 tosses, independent of each other.

Numerically, ${\displaystyle \mathbb {P} (A)=520/1024\approx 0.5078,}$^[6] ${\displaystyle \mathbb {P} (B)=638/1024\approx 0.6230,}$^[7] and their disjoint occurrence would imply at least 8 heads, so ${\displaystyle \mathbb {P} (A\mathbin {\square } B)\leq \mathbb {P} ({\text{8 heads or more}})=56/1024\approx 0.0547.}$^[8]

Percolation

In (Bernoulli) bond percolation of a graph, the ${\displaystyle \Omega _{i}}$'s are indexed by edges. Each edge is kept (or "open") with some probability ${\displaystyle p,}$ or otherwise removed (or "closed"), independent of other edges, and one studies questions about the connectivity of the remaining graph, for example the event ${\displaystyle u\leftrightarrow v}$ that there is a path between two vertices ${\displaystyle u}$ and ${\displaystyle v}$ using only open edges. For events of such form, the disjoint occurrence ${\displaystyle A\mathbin {\square } B}$ is the event where there exist two open paths not sharing any edges (corresponding to the subsets ${\displaystyle I}$ and ${\displaystyle J}$ in the definition), such that the first one providing the connection required by ${\displaystyle A,}$ and the second for ${\displaystyle B.}$^{[9]: 1322 [10]}

The inequality can be used to prove a version of the exponential decay phenomenon in the subcritical regime, namely that on the integer lattice graph ${\displaystyle \mathbb {Z} ^{d},}$ for ${\displaystyle p<p_{\mathrm {c} }}$ a suitably defined critical probability, the radius of the connected component containing the origin obeys a distribution with exponentially small tails:

$${\displaystyle \mathbb {P} (0\leftrightarrow \partial [-r,r]^{d})\leq \exp(-cr)}$$ for some constant ${\displaystyle c>0}$ depending on ${\displaystyle p.}$ Here ${\displaystyle \partial [-r,r]^{d}}$ consists of vertices ${\displaystyle x}$ that satisfies ${\displaystyle \max _{1\leq i\leq d}|x_{i}|=r.}$^{[11]: 87–90 [12]: 202}

Multiple events

When there are three or more events, the operator ${\displaystyle \square }$ may not be associative, because given a subset of indices ${\displaystyle K}$ on which ${\displaystyle x\in A\mathbin {\square } B}$ can be verified, it might not be possible to split ${\displaystyle K}$ a disjoint union ${\displaystyle I\sqcup J}$ such that ${\displaystyle I}$ witnesses ${\displaystyle x\in A}$ and ${\displaystyle J}$ witnesses ${\displaystyle x\in B}$.^[4]: 43 For example, there exists an event ${\displaystyle A\subseteq \{0,1\}^{6}}$ such that ${\displaystyle \left((A\mathbin {\square } A)\mathbin {\square } A\right)\mathbin {\square } A\neq (A\mathbin {\square } A)\mathbin {\square } (A\mathbin {\square } A).}$^[13]: 447

Nonetheless, one can define the ${\displaystyle k}$-ary BKR operation of events ${\displaystyle A_{1},A_{2},\ldots ,A_{k}}$ as the set of configurations ${\displaystyle x}$ where there are pairwise disjoint subset of indices ${\displaystyle I_{i}\subseteq [n]}$ such that ${\displaystyle I_{i}}$ witnesses the membership of ${\displaystyle x}$ in ${\displaystyle A_{i}.}$ This operation satisfies: $${\displaystyle A_{1}\mathbin {\square } A_{2}\mathbin {\square } A_{3}\mathbin {\square } \cdots \mathbin {\square } A_{k}\subseteq \left(\cdots \left((A_{1}\mathbin {\square } A_{2})\mathbin {\square } A_{3}\right)\mathbin {\square } \cdots \right)\mathbin {\square } A_{k},}$$ whence $${\displaystyle {\begin{aligned}\mathbb {P} (A_{1}\mathbin {\square } A_{2}\mathbin {\square } A_{3}\mathbin {\square } \cdots \mathbin {\square } A_{k})&\leq \mathbb {P} \left(\left(\cdots \left((A_{1}\mathbin {\square } A_{2})\mathbin {\square } A_{3}\right)\mathbin {\square } \cdots \right)\mathbin {\square } A_{k}\right)\\&\leq \mathbb {P} (A_{1})\mathbb {P} (A_{2})\cdots \mathbb {P} (A_{k})\end{aligned}}}$$ by repeated use of the original BK inequality.^{[14]: 204–205} This inequality was one factor used to analyse the winner statistics from the Florida Lottery and identify what Mathematics Magazine referred to as "implausibly lucky"^[14]: 210 individuals, confirmed later by enforcement investigation^[15] that law violations were involved.^[14]: 210

Spaces of larger cardinality

When ${\displaystyle \Omega _{i}}$ is allowed to be infinite, measure theoretic issues arise. For ${\displaystyle \Omega =[0,1]^{n}}$ and ${\displaystyle \mathbb {P} }$ the Lebesgue measure, there are measurable subsets ${\displaystyle A,B\subseteq \Omega }$ such that ${\displaystyle A\mathbin {\square } B}$ is non-measurable (so ${\displaystyle \mathbb {P} (A\mathbin {\square } B)}$ in the inequality is not defined),^[13]: 437 but the following theorem still holds:^[13]: 440

If ${\displaystyle A,B\subseteq [0,1]^{n}}$ are Lebesgue measurable, then there is some Borel set ${\displaystyle C}$ such that:

• ${\displaystyle A\mathbin {\square } B\subseteq C,}$ and
• ${\displaystyle \mathbb {P} (C)\leq \mathbb {P} (A)\mathbb {P} (B).}$