# Difference between revisions of "Bonferroni inequalities"

(Importing text file) |
Ulf Rehmann (talk | contribs) m (tex done, typo) |
||

Line 1: | Line 1: | ||

− | + | {{TEX|done}} | |

− | + | A solution of the classical matching problem and the counting inclusion-and-exclusion method (cf. also [[Inclusion-and-exclusion principle|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|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 < | + | 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 | + | 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 | + | 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 | 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 | + | 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 [[#References|[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 [[#References|[a3]]]. | Inequalities (a2), (a3) and (a4) are known as the Bonferroni inequalities because of their extensive use by C.E. Bonferroni [[#References|[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 [[#References|[a3]]]. | ||

− | When the probability | + | 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 [[#References|[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 | + | 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|Bonferroni-type inequalities]], overcome this difficulty. | ||

====References==== | ====References==== | ||

<table><TR><TD valign="top">[a1]</TD> <TD valign="top"> C.E. Bonferroni, "Teoria statistica delle classi e calcolo delle probabilità" ''Istit. Sup. Sci. Econ. Commerc. Firenze'' , '''8''' (1936) pp. 1–62</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top"> J. Galambos, I. Simonelli, "Bonferroni-type inequalities with applications" , Springer (1996)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top"> K. Jordan, "The foundations of the theory of probability" ''Mat. Phys. Lapok'' , '''34''' (1927) pp. 109–136 (In Hungarian)</TD></TR></table> | <table><TR><TD valign="top">[a1]</TD> <TD valign="top"> C.E. Bonferroni, "Teoria statistica delle classi e calcolo delle probabilità" ''Istit. Sup. Sci. Econ. Commerc. Firenze'' , '''8''' (1936) pp. 1–62</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top"> J. Galambos, I. Simonelli, "Bonferroni-type inequalities with applications" , Springer (1996)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top"> K. Jordan, "The foundations of the theory of probability" ''Mat. Phys. Lapok'' , '''34''' (1927) pp. 109–136 (In Hungarian)</TD></TR></table> |

## Latest revision as of 11:55, 9 February 2020

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

[a1] | C.E. Bonferroni, "Teoria statistica delle classi e calcolo delle probabilità" Istit. Sup. Sci. Econ. Commerc. Firenze , 8 (1936) pp. 1–62 |

[a2] | J. Galambos, I. Simonelli, "Bonferroni-type inequalities with applications" , Springer (1996) |

[a3] | K. Jordan, "The foundations of the theory of probability" Mat. Phys. Lapok , 34 (1927) pp. 109–136 (In Hungarian) |

**How to Cite This Entry:**

Bonferroni inequalities.

*Encyclopedia of Mathematics.*URL: http://encyclopediaofmath.org/index.php?title=Bonferroni_inequalities&oldid=44397