# Difference between revisions of "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.

How to Cite This Entry:
Bonferroni inequalities. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Bonferroni_inequalities&oldid=44397
This article was adapted from an original article by J. Galambos (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article