Van den Berg–Kesten inequality explained

Van den Berg–Kesten inequality
Type:	Theorem
Field:	Probability theory
Symbolic Statement:	P(An\squareB)\leP(A)P(B)
Conjectured By:	van den Berg and Kesten
Conjecture Date:	1985

In probability theory, the van den Berg–Kesten (BK) inequality or van den Berg–Kesten–Reimer (BKR) inequality states that the probability for two random events to both happen, and at the same time one can find "disjoint certificates" to show that they both happen, is at most the product of their individual probabilities. The special case for two monotone events (the notion as used in the FKG inequality) was first proved by van den Berg and Kesten^[1] in 1985, who also conjectured that the inequality holds in general, not requiring monotonicity. ^[2] later proved this conjecture.^[3] ^[4] The inequality is applied to probability spaces with a product structure, such as in percolation problems.^[5]

Statement

Let

\Omega_1,\Omega_2,\ldots,\Omega_n

be probability spaces, each of finitely many elements. The inequality applies to spaces of the form

\Omega=\Omega₁ x \Omega₂ x … x \Omega_n

, equipped with the product measure, so that each element

x=(x_1,\ldots,x_n)\in\Omega

is given the probability

\mathbb P(\) = \mathbb P_1(\) \cdots \mathbb P_n(\).

For two events

A,B\subseteq\Omega

, their disjoint occurrence

An{\square}B

is defined as the event consisting of configurations

whose memberships in

and in

can be verified on disjoint subsets of indices. Formally,

x\inAn{\square}B

if there exist subsets

I,J\subseteq[n]

such that:

I\capJ=\varnothing,

for all

that agrees with

(in other words,

y_i=x_i\foralli\inI

is also in

and

similarly every

that agrees with

is in

The inequality asserts that:

\mathbb P (A \mathbin B) \le \mathbb P (A) \mathbb P (B)

for every pair of events

and

^[3]

Examples

Coin tosses

\Omega

corresponds to tossing a fair coin

n=10

times, then each

\Omega_i=\{H,T\}

consists of the two possible outcomes, heads or tails, with equal probability. Consider the event

that there exists 3 consecutive heads, and the event

that there are at least 5 heads in total. Then

An\squareB

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

P(A)P(B),

^[4] which is to say the probability of getting

in 10 tosses, and getting

in another 10 tosses, independent of each other.

Numerically,

P(A)=520/1024 ≈ 0.5078,

P(B)=638/1024 ≈ 0.6230,

and their disjoint occurrence would imply at least 8 heads, so

P(An\squareB)\leP(8headsormore)=56/1024 ≈ 0.0547.

Percolation

In (Bernoulli) bond percolation of a graph, the

\Omega_i

's are indexed by edges. Each edge is kept (or "open") with some probability

or otherwise removed (or "closed"), independent of other edges, and one studies questions about the connectivity of the remaining graph, for example the event

u\leftrightarrowv

that there is a path between two vertices

and

using only open edges. For events of such form, the disjoint occurrence

An\squareB

is the event where there exist two open paths not sharing any edges (corresponding to the subsets

and

in the definition), such that the first one providing the connection required by

and the second for

^[6] ^[7]

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

Z^d,

for

p<p_c

a suitably defined critical probability, the radius of the connected component containing the origin obeys a distribution with exponentially small tails:

c>0

Van den Berg–Kesten inequality explained

Statement

Examples

Coin tosses

Percolation

Extensions

Multiple events

Spaces of larger cardinality

Notes and References