Bonferroni Inequality

From GM-RKB
Jump to navigation Jump to search

A Bonferroni Inequality is a generalizations of the Boole's Inequality for finding lower or upper bounds of a set union.



References

2016

Define [math]\displaystyle{ S_1 := \sum_{i=1}^n {\mathbb P}(A_i), }[/math] and [math]\displaystyle{ S_2 := \sum_{1\le i\lt j\le n} {\mathbb P}(A_i \cap A_j), }[/math] as well as [math]\displaystyle{ S_k := \sum_{1\le i_1\lt \cdots\lt i_k\le n} {\mathbb P}(A_{i_1}\cap \cdots \cap A_{i_k} ) }[/math] for all integers k in {3, ..., n}. Then, for odd k in {1, ..., n},
[math]\displaystyle{ {\mathbb P}\biggl( \bigcup_{i=1}^n A_i \biggr) \le \sum_{j=1}^k (-1)^{j-1} S_j, }[/math]
and for even k in {2, ..., n},
[math]\displaystyle{ {\mathbb P}\biggl( \bigcup_{i=1}^n A_i \biggr) \ge \sum_{j=1}^k (-1)^{j-1} S_j. }[/math]
Boole's inequality is recovered by setting k = 1. When k = n, then equality holds and the resulting identity is the inclusion–exclusion principle.

1977

  • (Galambos, 1977) ⇒ Galambos, J. (1977). Bonferroni inequalities. The Annals of Probability, 577-581. http://www.jstor.org/stable/2243081
    • Let [math]\displaystyle{ A_1, A_2, \cdots, A_n }[/math] be events on a probability space. Let [math]\displaystyle{ S_{k,n} }[/math] be the k-th binomial moment of the number [math]\displaystyle{ m_n }[/math] of those A's which occur. An estimate on the distribution [math]\displaystyle{ y_t = P(m_n \geqq t) }[/math] by a linear combination of [math]\displaystyle{ S_{1,n}, S_{2,n}, \cdots, S_{n,n} }[/math] is called a Bonferroni inequality. We present for proving Bonferroni inequalities a method which makes use of the following two facts: the sequence [math]\displaystyle{ y_t }[/math] is decreasing and [math]\displaystyle{ S_{k,n} }[/math] is a linear combination of the [math]\displaystyle{ y_t }[/math]. By this method, we significantly simplify a recent proof for the sharpest possible lower bound on [math]\displaystyle{ y_1 }[/math] in terms of [math]\displaystyle{ S_{1,n} }[/math] and [math]\displaystyle{ S_{2,n} }[/math]. In addition, we obtain an extension of known bounds on [math]\displaystyle{ y_t }[/math] in the spirit of a recent extension of the method of inclusion and exclusion.