Bonferroni inequalities

A solution of the classical matching problem and the counting inclusion-and-exclusion method (cf. also Inclusion-and-exclusion principle) can be given in a unified manner by the following set of inequalities. Let $ A _ {1} \dots A _ {n} $ be events on a given probability space, and let $ m _ {n} ( A ) $ denote the number of $ A _ {j} $ that occur. Set $ S _ {0} = S _ {0,n} = 1 $ and

$$ \tag{a1} S _ {j} = S _ { j,n} = \sum {\mathsf P} ( A _ {i _ 1 } \cap \dots \cap A _ { i _ j } ) , \quad j \geq 1, $$

where summation is over all subscripts $ 1 \leq i _ {1} < \dots < i _ {j} \leq n $. The numbers $ S _ {j} $, $ j \geq 0 $, are known as the binomial moments of $ m _ {n} ( A ) $, since, by turning to indicators, one immediately obtains that, with the expectation operator $ {\mathsf E} $,

$$ S _ {j} = {\mathsf E} \left [ \left ( \begin{array}{c} {m _ {n} ( A )} \\ j \end{array} \right ) \right ] , \quad k \geq 0. $$

Now, the following inequalities are valid for all integers $ 0 \leq 2k \leq n - 1 $ and $ 2 \leq 2t \leq n $:

$$ \tag{a2} \sum _ {j = 1} ^ { {2k } + 1} ( - 1 ) ^ {j - 1} S _ {j} \leq {\mathsf P} ( m _ {n} ( A ) \geq 1 ) \leq \sum _ {j = 1} ^ { {2t} } ( - 1 ) ^ {j - 1} S _ {j} . $$

Inequality (a2) can be rewritten for $ {\mathsf P} ( m _ {n} ( A ) = 0 ) $ in the light of the elementary relation $ {\mathsf P} ( m _ {n} ( A ) = 0 ) = 1 - {\mathsf P} ( m _ {n} ( A ) \geq 1 ) $. Furthermore, it can be extended to

$$ \tag{a3} \sum _ {j = 0} ^ { {2k } + 1} ( - 1 ) ^ {j} \left ( \begin{array}{c} {r + j - 1} \\ j \end{array} \right ) S _ {r + j} \leq $$

$$ \leq {\mathsf P} ( m _ {n} ( A ) \geq r ) \leq \sum _ {j = 0} ^ { {2t} } ( - 1 ) ^ {j} \left ( \begin{array}{c} {r + j - 1} \\ j \end{array} \right ) S _ {r + j} , $$

and

$$ \tag{a4} \sum _ {j = 0} ^ { {2k } + 1} ( - 1 ) ^ {j} \left ( \begin{array}{c} {r + j} \\ j \end{array} \right ) S _ {r + j} \leq $$

$$ \leq {\mathsf P} ( m _ {n} ( A ) = r ) \leq \sum _ {j = 0} ^ { {2t} } ( - 1 ) ^ {j} \left ( \begin{array}{c} {r + j} \\ j \end{array} \right ) S _ {r + j} , $$

where $ r $ is an arbitrary integer with $ 0 \leq r \leq n $ and the limits $ k $ and $ t $ satisfy $ 2k + 1 + r \leq n $ and $ r + 2t \leq n $.

Inequalities (a2), (a3) and (a4) are known as the Bonferroni inequalities because of their extensive use by C.E. Bonferroni [a1] in statistical settings; this work of Bonferroni generated a considerable follow-up in later years. However, the inequalities above were known earlier: for discrete probability spaces they go back to the eighteenth century, whilst for an abstract, and thus general, probability space their validity appears in [a3].

When the probability $ {\mathsf P} $ is just counting proportions (a very typical case in number theory), then (a2) is known as the method of inclusion-and-exclusion. However, each of (a2), (a3) or (a4) is a very useful tool with a generally underlying probability in such widely ranging topics as combinatorics, number theory, information theory, statistics, and extreme value theory. For detailed descriptions of all such applications, see [a2].

Although the Bonferroni inequalities are very effective tools in several problems, they may become impractical in others. In particular, when the general terms of $ S _ {j} $ are known with an error term, then, because of the large number of terms in $ S _ {j} $ as a function of $ n $, the error terms might dominate the sum of the main terms in the Bonferroni bounds, making the results meaningless. Modifications of the Bonferroni inequalities, known as Bonferroni-type inequalities, overcome this difficulty.

References[edit]