Type | Theorem |
---|---|
Field | Probability theory |
Symbolic statement | |
Conjectured by | van den Berg and Kesten |
Conjectured in | 1985 |
First proof by | Reimer |
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. Reimer [2] later proved this conjecture. [3]: 159 [4]: 44 The inequality is applied to probability spaces with a product structure, such as in percolation problems. [5]: 829
Let be probability spaces, each of finitely many elements. The inequality applies to spaces of the form , equipped with the product measure, so that each element is given the probability
For two events , their disjoint occurrence is defined as the event consisting of configurations whose memberships in and in can be verified on disjoint subsets of indices. Formally, if there exist subsets such that:
The inequality asserts that: for every pair of events and [3]: 160
If corresponds to tossing a fair coin times, then each 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 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 [4]: 42 which is to say the probability of getting in 10 tosses, and getting in another 10 tosses, independent of each other.
Numerically, [6] [7] and their disjoint occurrence would imply at least 8 heads, so [8]
In (Bernoulli) bond percolation of a graph, the '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 that there is a path between two vertices and using only open edges. For events of such form, the disjoint occurrence 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 [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 for a suitably defined critical probability, the radius of the connected component containing the origin obeys a distribution with exponentially small tails:
for some constant depending on Here consists of vertices that satisfies [11]: 87–90 [12]: 202
When there are three or more events, the operator may not be associative, because given a subset of indices on which can be verified, it might not be possible to split a disjoint union such that witnesses and witnesses . [4]: 43 For example, there exists an event such that [13]: 447
Nonetheless, one can define the -ary BKR operation of events as the set of configurations where there are pairwise disjoint subset of indices such that witnesses the membership of in This operation satisfies: whence 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
When is allowed to be infinite, measure theoretic issues arise. For and the Lebesgue measure, there are measurable subsets such that is non-measurable (so in the inequality is not defined), [13]: 437 but the following theorem still holds: [13]: 440
If are Lebesgue measurable, then there is some Borel set such that:
- and
The highly novel BK (van den Berg/Kesten) inequality plays a key role in systems subjected to a product measure such as percolation.
The proof of Item 1 (with in place of ) can be derived from the BK-inequality [vdBK].
Some of the frequent winners, including the top one, were part of an underground market for winning lottery tickets, lottery investigators later found.
Type | Theorem |
---|---|
Field | Probability theory |
Symbolic statement | |
Conjectured by | van den Berg and Kesten |
Conjectured in | 1985 |
First proof by | Reimer |
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. Reimer [2] later proved this conjecture. [3]: 159 [4]: 44 The inequality is applied to probability spaces with a product structure, such as in percolation problems. [5]: 829
Let be probability spaces, each of finitely many elements. The inequality applies to spaces of the form , equipped with the product measure, so that each element is given the probability
For two events , their disjoint occurrence is defined as the event consisting of configurations whose memberships in and in can be verified on disjoint subsets of indices. Formally, if there exist subsets such that:
The inequality asserts that: for every pair of events and [3]: 160
If corresponds to tossing a fair coin times, then each 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 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 [4]: 42 which is to say the probability of getting in 10 tosses, and getting in another 10 tosses, independent of each other.
Numerically, [6] [7] and their disjoint occurrence would imply at least 8 heads, so [8]
In (Bernoulli) bond percolation of a graph, the '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 that there is a path between two vertices and using only open edges. For events of such form, the disjoint occurrence 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 [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 for a suitably defined critical probability, the radius of the connected component containing the origin obeys a distribution with exponentially small tails:
for some constant depending on Here consists of vertices that satisfies [11]: 87–90 [12]: 202
When there are three or more events, the operator may not be associative, because given a subset of indices on which can be verified, it might not be possible to split a disjoint union such that witnesses and witnesses . [4]: 43 For example, there exists an event such that [13]: 447
Nonetheless, one can define the -ary BKR operation of events as the set of configurations where there are pairwise disjoint subset of indices such that witnesses the membership of in This operation satisfies: whence 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
When is allowed to be infinite, measure theoretic issues arise. For and the Lebesgue measure, there are measurable subsets such that is non-measurable (so in the inequality is not defined), [13]: 437 but the following theorem still holds: [13]: 440
If are Lebesgue measurable, then there is some Borel set such that:
- and
The highly novel BK (van den Berg/Kesten) inequality plays a key role in systems subjected to a product measure such as percolation.
The proof of Item 1 (with in place of ) can be derived from the BK-inequality [vdBK].
Some of the frequent winners, including the top one, were part of an underground market for winning lottery tickets, lottery investigators later found.