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

$$\begin{array}{}\text{(a1)}& S_j=S_{j,n}=\sum \mathsf{P}(A_{i_1}\cap \cdots \cap A_{i_j}),j\ge 1,\end{array}$$

where summation is over all subscripts $1\le i_1<\cdots <i_j\le n$. The numbers $S_j$, $j\ge 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],k\ge 0.$$

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

$$\begin{array}{}\text{(a2)}& \sum _{j=1}^{2k+1}(-1{)}^{j-1}{S}_j\le \mathsf{P}(m_n(A)\ge 1)\le \sum _{j=1}^{2t}(-1{)}^{j-1}{S}_j.\end{array}$$

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)\ge 1)$. Furthermore, it can be extended to

$$\begin{array}{}\text{(a3)}& \sum _{j=0}^{2k+1}(-1{)}^j\left(\begin{array}{c}r+j-1\\ j\end{array}\right)S_{r+j}\le \end{array}$$

$$\le \mathsf{P}(m_n(A)\ge r)\le \sum _{j=0}^{2t}(-1{)}^j\left(\begin{array}{c}r+j-1\\ j\end{array}\right)S_{r+j},$$

and

$$\begin{array}{}\text{(a4)}& \sum _{j=0}^{2k+1}(-1{)}^j\left(\begin{array}{c}r+j\\ j\end{array}\right)S_{r+j}\le \end{array}$$

$$\le \mathsf{P}(m_n(A)=r)\le \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\le r\le n$ and the limits $k$ and $t$ satisfy $2k+1+r\le n$ and $r+2t\le 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]