Namespaces
Variants
Actions

Difference between revisions of "Bonferroni inequalities"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex done, typo)
 
Line 1: Line 1:
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110730/b1107301.png" /> be events on a given [[Probability space|probability space]], and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110730/b1107302.png" /> denote the number of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110730/b1107303.png" /> that occur. Set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110730/b1107304.png" /> and
+
{{TEX|done}}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110730/b1107305.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a1)</td></tr></table>
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110730/b1107306.png" />. The numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110730/b1107307.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110730/b1107308.png" />, are known as the binomial moments of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110730/b1107309.png" />, since, by turning to indicators, one immediately obtains that, with the expectation operator <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110730/b11073010.png" />,
+
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} $,
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110730/b11073011.png" /></td> </tr></table>
+
$$
 +
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110730/b11073012.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110730/b11073013.png" />:
+
Now, the following inequalities are valid for all integers 0 \leq  2k \leq  n - 1 $
 +
and $  2 \leq  2t \leq  n $:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110730/b11073014.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a2)</td></tr></table>
+
$$ \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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110730/b11073015.png" /> in the light of the elementary relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110730/b11073016.png" />. Furthermore, it can be extended to
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110730/b11073017.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a3)</td></tr></table>
+
$$ \tag{a3}
 +
\sum _ {j = 0} ^ { {2k }  + 1} ( - 1 )  ^ {j} \left ( \begin{array}{c}
 +
{r + j - 1} \\
 +
j
 +
\end{array}
 +
\right ) S _ {r + j}  \leq
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110730/b11073018.png" /></td> </tr></table>
+
$$
 +
\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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110730/b11073019.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a4)</td></tr></table>
+
$$ \tag{a4}
 +
\sum _ {j = 0} ^ { {2k }  + 1} ( - 1 )  ^ {j} \left ( \begin{array}{c}
 +
{r + j} \\
 +
j
 +
\end{array}
 +
\right ) S _ {r + j}  \leq
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110730/b11073020.png" /></td> </tr></table>
+
$$
 +
\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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110730/b11073021.png" /> is an arbitrary integer with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110730/b11073022.png" /> and the limits <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110730/b11073023.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110730/b11073024.png" /> satisfy <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110730/b11073025.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110730/b11073026.png" />.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110730/b11073027.png" /> 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]]].
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110730/b11073028.png" /> are known with an error term, then, because of the large number of terms in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110730/b11073029.png" /> as a function of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110730/b11073030.png" />, 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.
+
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
This article was adapted from an original article by J. Galambos (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article