Van den Berg–Kesten inequality

Van den Berg–Kesten inequality
Van den Berg–Kesten inequality
Type	Theorem
Field	Probability theory
Symbolic statement	ℙ(A◻B)≤ℙ(A)ℙ(B)
Conjectured by	van den Berg and Kesten
Conjectured in	1985
First proof by	Reimer [fr; de]

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 in 1985, who also conjectured that the inequality holds in general, not requiring monotonicity. Reimer [fr; de] later proved this conjecture.^: 159^: 44 The inequality is applied to probability spaces with a product structure, such as in percolation problems.^: 829

Statement

Let $Ω_{1}, Ω_{2}, \dots, Ω_{n}$ be probability spaces, each of finitely many elements. The inequality applies to spaces of the form $Ω = Ω_{1} \times Ω_{2} \times \dots \times Ω_{n}$ , equipped with the product measure, so that each element $x = (x_{1}, \dots, x_{n}) \in Ω$ is given the probability $ℙ ({x}) = ℙ_{1} ({x_{1}}) \dots ℙ_{n} ({x_{n}}) .$

For two events $A, B \subseteq Ω$ , their disjoint occurrence $A ◻ B$ is defined as the event consisting of configurations $x$ whose memberships in $A$ and in $B$ can be verified on disjoint subsets of indices. Formally, $x \in A ◻ B$ if there exist subsets $I, J \subseteq [n]$ such that:

$I \cap J = \emptyset,$
for all $y$ that agrees with $x$ on $I$ (in other words, $y_{i} = x_{i} \forall i \in I$ ), $y$ is also in $A,$ and
similarly every $z$ that agrees with $x$ on $J$ is in $B .$

The inequality asserts that: $ℙ (A ◻ B) \leq ℙ (A) ℙ (B)$ for every pair of events $A$ and $B .$ ^: 160

Examples

Coin tosses

If $Ω$ corresponds to tossing a fair coin $n = 10$ times, then each $Ω_{i} = {H, T}$ consists of the two possible outcomes, heads or tails, with equal probability. Consider the event $A$ that there exists 3 consecutive heads, and the event $B$ that there are at least 5 heads in total. Then $A ◻ 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 $ℙ (A) ℙ (B),$ ^: 42 which is to say the probability of getting $A$ in 10 tosses, and getting $B$ in another 10 tosses, independent of each other.

Numerically, $ℙ (A) = 520 / 1024 \approx 0.5078,$ $ℙ (B) = 638 / 1024 \approx 0.6230,$ and their disjoint occurrence would imply at least 8 heads, so $ℙ (A ◻ B) \leq ℙ (8 heads or more) = 56 / 1024 \approx 0.0547.$

Percolation

In (Bernoulli) bond percolation of a graph, the $Ω_{i}$ 's are indexed by edges. Each edge is kept (or "open") with some probability $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 $u \leftrightarrow v$ that there is a path between two vertices $u$ and $v$ using only open edges. For events of such form, the disjoint occurrence $A ◻ B$ is the event where there exist two open paths not sharing any edges (corresponding to the subsets $I$ and $J$ in the definition), such that the first one providing the connection required by $A,$ and the second for $B .$ ^: 1322

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 $ℤ^{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:

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

Extensions

Multiple events

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

Nonetheless, one can define the $k$ -ary BKR operation of events $A_{1}, A_{2}, \dots, A_{k}$ as the set of configurations $x$ where there are pairwise disjoint subset of indices $I_{i} \subseteq [n]$ such that $I_{i}$ witnesses the membership of $x$ in $A_{i} .$ This operation satisfies: $A_{1} ◻ A_{2} ◻ A_{3} ◻ \dots ◻ A_{k} \subseteq (\dots ((A_{1} ◻ A_{2}) ◻ A_{3}) ◻ \dots) ◻ A_{k},$ whence $\begin{matrix} ℙ (A_{1} ◻ A_{2} ◻ A_{3} ◻ \dots ◻ A_{k}) & \leq ℙ ((\dots ((A_{1} ◻ A_{2}) ◻ A_{3}) ◻ \dots) ◻ A_{k}) \\ \leq ℙ (A_{1}) ℙ (A_{2}) \dots ℙ (A_{k}) \end{matrix}$ by repeated use of the original BK inequality.^{: 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"^: 210 individuals, confirmed later by enforcement investigation that law violations were involved.^: 210

Spaces of larger cardinality

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

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

$A ◻ B \subseteq C,$ and

$ℙ (C) \leq ℙ (A) ℙ (B) .$

References

↑ van den Berg, J.; Kesten, H. (1985). "Inequalities with applications to percolation and reliability". Journal of Applied Probability. 22 (3): 556–569. doi:10.1017/s0021900200029326. ISSN 0021-9002. MR 0799280 – via The Wikipedia Library.
↑ Reimer, David (2000). "Proof of the Van den Berg–Kesten Conjecture". Combinatorics, Probability and Computing. 9 (1): 27–32. doi:10.1017/S0963548399004113. ISSN 0963-5483. MR 1751301. S2CID 33118560 – via The Wikipedia Library.
1 2 Borgs, Christian; Chayes, Jennifer T.; Randall, Dana (1999). "The van den Berg-Kesten-Reimer Inequality: A Review". In Bramson, Maury; Durrett, Rick (eds.). Perplexing Problems in Probability: Festschrift in Honor of Harry Kesten. Progress in Probability. Boston, MA: Birkhäuser. pp. 159–173. doi:10.1007/978-1-4612-2168-5_9. ISBN 978-1-4612-2168-5. MR 1703130 – via The Wikipedia Library.
1 2 3 Bollobás, Béla; Riordan, Oliver (2006). "2 - Probabilistic tools". Percolation. Cambridge University Press. pp. 36–49. doi:10.1017/CBO9781139167383.003. ISBN 9780521872324. MR 2283880 – via The Wikipedia Library.
↑ Grimmett, Geoffrey R.; Lawler, Gregory F. (2020). "Harry Kesten (1931–2019): A Personal and Scientific Tribute". Notices of the AMS. 67 (6): 822–831. arXiv:2001.03639. doi:10.1090/noti2100. S2CID 210164713. The highly novel BK (van den Berg/Kesten) inequality plays a key role in systems subjected to a product measure such as percolation.
↑ "3 consecutive heads in 10 coin flips". Wolfram Alpha Site.
↑ "at least 5 heads in 10 coin flips". Wolfram Alpha Site.
↑ "at least 8 heads in 10 coin flips". Wolfram Alpha Site.
↑ Grimmett, Geoffrey (1995-03-01). "Comparison and disjoint-occurrence inequalities for random-cluster models". Journal of Statistical Physics. 78 (5): 1311–1324. Bibcode:1995JSP....78.1311G. doi:10.1007/BF02180133. ISSN 1572-9613. MR 1316106. S2CID 16426885. Retrieved 2022-12-18.
↑ Chayes, Jennifer Tour; Puha, Amber L.; Sweet, Ted (1999). "Lecture 1. The Basics of Percolation (in Independent and dependent percolation)" (PDF). Probability theory and applications. IAS/Park City Math. Ser. Vol. 6. Amer. Math. Soc., Providence, RI. pp. 53–66. MR 1678308. Retrieved 2022-12-18.
↑ Grimmett, Geoffrey R. (2018). "5.1 Subcritical Phase". Probability on Graphs: Random Processes on Graphs and Lattices. Institute of Mathematical Statistics Textbooks (2 ed.). Cambridge: Cambridge University Press. pp. 86–130. doi:10.1017/9781108528986.006. ISBN 978-1-108-43817-9. MR 2723356.
↑ Duminil-Copin, Hugo; Tassion, Vincent (2017-01-30). "A new proof of the sharpness of the phase transition for Bernoulli percolation on $ℤ^{d}$ ". L'Enseignement Mathématique. 62 (1): 199–206. arXiv:1502.03051. doi:10.4171/lem/62-1/2-12. ISSN 0013-8584. MR 3605816. S2CID 119307436. The proof of Item 1 (with ${\tilde{p}}_{c}$ in place of $p_{c}$ ) can be derived from the BK-inequality [vdBK].
1 2 3 Arratia, Richard; Garibaldi, Skip; Hales, Alfred W. (2018). "The van den Berg–Kesten–Reimer operator and inequality for infinite spaces". Bernoulli. 24 (1): 433–448. arXiv:1508.05337. doi:10.3150/16-BEJ883. ISSN 1350-7265. MR 3706764. S2CID 4666324.
1 2 3 Arratia, Richard; Garibaldi, Skip; Mower, Lawrence; Stark, Philip B. (2015-06-01). "Some People Have All the Luck". Mathematics Magazine. 88 (3): 196–211. arXiv:1503.02902. doi:10.4169/math.mag.88.3.196. ISSN 0025-570X. MR 3383910. S2CID 15631424. Retrieved 2022-12-18.
↑ Mower, Lawrence (2015-07-15). "Math used in Post's Florida Lottery investigation published in journal". Palm Beach Post. Archived from the original on 2022-12-18. Retrieved 2022-12-18. Some of the frequent winners, including the top one, were part of an underground market for winning lottery tickets, lottery investigators later found.

[BK-1] van den Berg, J.; Kesten, H. (1985). "Inequalities with applications to percolation and reliability". Journal of Applied Probability. 22 (3): 556–569. doi:10.1017/s0021900200029326. ISSN 0021-9002. MR 0799280 – via The Wikipedia Library.

[2] Reimer, David (2000). "Proof of the Van den Berg–Kesten Conjecture". Combinatorics, Probability and Computing. 9 (1): 27–32. doi:10.1017/S0963548399004113. ISSN 0963-5483. MR 1751301. S2CID 33118560 – via The Wikipedia Library.

[review-3] 1 2 Borgs, Christian; Chayes, Jennifer T.; Randall, Dana (1999). "The van den Berg-Kesten-Reimer Inequality: A Review". In Bramson, Maury; Durrett, Rick (eds.). Perplexing Problems in Probability: Festschrift in Honor of Harry Kesten. Progress in Probability. Boston, MA: Birkhäuser. pp. 159–173. doi:10.1007/978-1-4612-2168-5_9. ISBN 978-1-4612-2168-5. MR 1703130 – via The Wikipedia Library.

[bollobas-4] 1 2 3 Bollobás, Béla; Riordan, Oliver (2006). "2 - Probabilistic tools". Percolation. Cambridge University Press. pp. 36–49. doi:10.1017/CBO9781139167383.003. ISBN 9780521872324. MR 2283880 – via The Wikipedia Library.

[5] Grimmett, Geoffrey R.; Lawler, Gregory F. (2020). "Harry Kesten (1931–2019): A Personal and Scientific Tribute". Notices of the AMS. 67 (6): 822–831. arXiv:2001.03639. doi:10.1090/noti2100. S2CID 210164713. The highly novel BK (van den Berg/Kesten) inequality plays a key role in systems subjected to a product measure such as percolation.

[6] "3 consecutive heads in 10 coin flips". Wolfram Alpha Site.

[7] "at least 5 heads in 10 coin flips". Wolfram Alpha Site.

[8] "at least 8 heads in 10 coin flips". Wolfram Alpha Site.

[9] Grimmett, Geoffrey (1995-03-01). "Comparison and disjoint-occurrence inequalities for random-cluster models". Journal of Statistical Physics. 78 (5): 1311–1324. Bibcode:1995JSP....78.1311G. doi:10.1007/BF02180133. ISSN 1572-9613. MR 1316106. S2CID 16426885. Retrieved 2022-12-18.

[10] Chayes, Jennifer Tour; Puha, Amber L.; Sweet, Ted (1999). "Lecture 1. The Basics of Percolation (in Independent and dependent percolation)" (PDF). Probability theory and applications. IAS/Park City Math. Ser. Vol. 6. Amer. Math. Soc., Providence, RI. pp. 53–66. MR 1678308. Retrieved 2022-12-18.

[11] Grimmett, Geoffrey R. (2018). "5.1 Subcritical Phase". Probability on Graphs: Random Processes on Graphs and Lattices. Institute of Mathematical Statistics Textbooks (2 ed.). Cambridge: Cambridge University Press. pp. 86–130. doi:10.1017/9781108528986.006. ISBN 978-1-108-43817-9. MR 2723356.

[12] Duminil-Copin, Hugo; Tassion, Vincent (2017-01-30). "A new proof of the sharpness of the phase transition for Bernoulli percolation on $ℤ^{d}$ ". L'Enseignement Mathématique. 62 (1): 199–206. arXiv:1502.03051. doi:10.4171/lem/62-1/2-12. ISSN 0013-8584. MR 3605816. S2CID 119307436. The proof of Item 1 (with ${\tilde{p}}_{c}$ in place of $p_{c}$ ) can be derived from the BK-inequality [vdBK].

[infty-13] 1 2 3 Arratia, Richard; Garibaldi, Skip; Hales, Alfred W. (2018). "The van den Berg–Kesten–Reimer operator and inequality for infinite spaces". Bernoulli. 24 (1): 433–448. arXiv:1508.05337. doi:10.3150/16-BEJ883. ISSN 1350-7265. MR 3706764. S2CID 4666324.

[implausilucky-14] 1 2 3 Arratia, Richard; Garibaldi, Skip; Mower, Lawrence; Stark, Philip B. (2015-06-01). "Some People Have All the Luck". Mathematics Magazine. 88 (3): 196–211. arXiv:1503.02902. doi:10.4169/math.mag.88.3.196. ISSN 0025-570X. MR 3383910. S2CID 15631424. Retrieved 2022-12-18.

[15] Mower, Lawrence (2015-07-15). "Math used in Post's Florida Lottery investigation published in journal". Palm Beach Post. Archived from the original on 2022-12-18. Retrieved 2022-12-18. Some of the frequent winners, including the top one, were part of an underground market for winning lottery tickets, lottery investigators later found.