Bonferroni-type inequalities

The Bonferroni inequalities may become impractical as a result of the large number of terms in $ S _ {k} $( for notation, see Bonferroni inequalities). In order to overcome this difficulty, two kinds of modification can be performed:

i) one can limit the number of $ S _ {k} $ used in a bound but combine this with "better" coefficients than would be provided by a Bonferroni bound;

ii) one can modify the definition of $ S _ {k} $ by limiting its number of terms, but only to an extent that still produces the Bonferroni bounds for some $ 0 \leq r \leq n $. The new inequalities obtained in this manner are called Bonferroni-type inequalities. In other words, for i), given the values $ S _ {k} $, $ k \in T $, where $ T $ is a given finite set, one seeks coefficients $ a _ {k} ( n,r ) $, $ b _ {k} ( n,r ) $, $ c _ {k} ( n,r ) $, and $ d _ {k} ( n,r ) $ such that, whatever the probability space and the events $ A _ {j} $ on it,

$$ \tag{a1} \sum _ { T } a _ {k} ( n,r ) S _ {k} \leq {\mathsf P} ( m _ {n} ( A ) \geq r ) \leq \sum _ { T } b _ {k} ( n,r ) S _ {k} , $$

and

$$ \tag{a2} \sum _ { T } c _ {k} ( n,r ) S _ {k} \leq {\mathsf P} ( m _ {n} ( A ) = r ) \leq \sum _ { T } d _ {k} ( n,r ) S _ {k} , $$

where $ \sum _ {T} $ signifies summation over $ k \in T $. In the following simple example, all problems and difficulties arising in the solution of (a1) and (a2) are demonstrated.

Let $ T = \{ 0,1,2 \} $, so that one can use $ S _ {0} = 1 $, $ S _ {1} $ and $ S _ {2} $ in setting the bounds in (a1) or (a2). Concentrating on (a2) and considering only $ r = 0 $, one looks for coefficients $ c _ {1} ( n,0 ) $, $ c _ {2} ( n,0 ) $, $ d _ {1} ( n,0 ) $, and $ d _ {2} ( n,0 ) $( it easily follows that $ c _ {0} ( n,0 ) = d _ {0} ( n,0 ) = 1 $) such that (a2) be valid. It turns out (and it is far from easy to arrive at such a conclusion; see [a7] and [a2]) that with this choice of $ T $ and $ r $ no better bounds can be found than

$$ 1 - S _ {1} + { \frac{2}{n} } S _ {2} \leq {\mathsf P} ( m _ {n} ( A ) = 0 ) \leq $$

$$ \leq 1 - { \frac{2}{j + 1} } S _ {1} + { \frac{2}{j ( j + 1 )} } S _ {2} , $$

where $ 1 \leq j \leq n - 1 $ is an arbitrary integer.

For (a2), the following remarkable result has been established in [a4]: It is valid on an arbitrary probability space for every choice of the $ A _ {j} $ if and only if it is valid for independent $ A _ {j} $ with each $ {\mathsf P} ( A _ {j} ) $ either equal to some $ p $, $ 0 \leq p \leq 1 $, or zero. On the other hand, it was proved in [a6] that if (a1) is valid for the independent structures just mentioned, then (a1) is valid on an arbitrary probability space whatever the choice of the $ A _ {j} $. The above results reduce both (a1) and (a2) to polynomial inequalities. Amongst the several advantages of transforming (a1) and (a2) to polynomials, known as the method of polynomials for proving Bonferroni-type inequalities, is the following reduction formula: Assume one has found coefficients $ c _ {k} ( n ) = c _ {k} ( n,0 ) $ and $ d _ {k} ( n ) = d _ {k} ( n,0 ) $ such that (a2) holds for $ r = 0 $ and some set $ T = T _ {0} $. Then both (a1) and (a2) hold for arbitrary $ r $, $ 0 \leq r \leq n $, with the set $ T = T _ {r} $ obtained from $ T _ {0} $ by adding $ r $ to each of its elements, and the coefficients of $ S _ {k + r,n + r} $ in (a1) and (a2) satisfy the relations

$$ c _ {k + r} ( n + r,r ) = \left ( \begin{array}{c} {k + r} \\ r \end{array} \right ) c _ {k} ( n ) , $$

$$ d _ {k + r} ( n + r,r ) = \left ( \begin{array}{c} {k + r} \\ r \end{array} \right ) d _ {k} ( n ) . $$

Upon replacing $ \left ( \begin{array}{c} {k + r} \\ r \end{array} \right ) $ by $ \left ( \begin{array}{c} {k + r - 1} \\ {r - 1} \end{array} \right ) $ in the right-hand sides above, one obtains $ a _ {k + r} ( n + r,r ) $ and $ b _ {k+r} ( n + r,r ) $, respectively.

For modification ii) of the Bonferroni inequalities there are very general and very effective graph sieves. Choose an arbitrary graph with vertices $ \{ 1 \dots n \} $( that is, the edge set is chosen in an arbitrary manner). Now define $ S _ {k} ^ {*} $ by deleting many terms from $ S _ {k} $; in fact, retain in $ S _ {k + r} ^ {*} $ only those terms of $ S _ {k + r} $ for which $ ( i _ {1} \dots i _ {k + r} ) $ has no edge from the underlying graph just chosen if $ k $ is even, and allow, for $ k $ odd, a well-defined number of edges in $ ( i _ {1} \dots i _ {k + r} ) $, the number of which may depend on $ r $ but not on $ k $. Define $ S _ {k} ^ {* *} $ in a similar manner, but interchange the role of "even" and "odd" . It is proved in [a8], for $ r = 0 $, and in [a1], for arbitrary $ r $, that the Bonferroni lower bounds remain valid with $ S _ {k} ^ {*} $, whilst the upper bounds remain valid with $ S _ {k} ^ {* *} $. These new bounds found many applications in random set selections, information theory, and extreme value theory; see [a5]. The basic idea of constructing $ S _ {k} ^ {*} $ and $ S _ {k} ^ {* *} $ is similar to Brun's method in number theory (cf. Brun sieve).

Extension of Bonferroni and Bonferroni-type inequalities have also been studied in multivariate settings. Here, multivariate means that one faces several sequences of events, and one establishes linear bounds on the joint distribution of the numbers counting the occurrences in each sequence of events. Bounds are again in terms of binomial moments. Such multivariate studies are quite new; see [a3]. For a full coverage of the known (1996) multivariate bounds, see [a5].

References

[a1]	J. Galambos, "On the sieve methods in probability theory. I" Studia Sci. Math. Hung. , 1 (1966) pp. 39–50
[a2]	J. Galambos, "Bonferroni inequalities" Ann. of Probab. , 5 (1977) pp. 577–581
[a3]	"Probability theory and applications" J. Galambos (ed.) I. Kátai (ed.) , Kluwer Acad. Publ. (1992)
[a4]	J. Galambos, R. Mucci, "Inequalities for linear combination of binomial moments" Publ. Math. Debrecen , 27 (1980) pp. 263–269
[a5]	J. Galambos, I. Simonelli, "Bonferroni-type inequalities with applications" , Springer (1996)
[a6]	J. Galambos, I. Simonelli, "An extension of the method of polynomials and a new reduction formula for Bonferroni-type inequalities" Statistics and Probability Lett. , 28 (1996) pp. 147–151
[a7]	S.M. Kwerel, "Most stringent bounds on aggregated probabilities of partially specified dependent probability systems" J. Amer. Statist. Assoc. , 70 (1975) pp. 472–479
[a8]	A. Rényi, "A general method for proving theorems of probability theory and some of its applications" , Selected papers of Alfréd Rényi , 2 , Akad. Kiadó (1976) (Original (in Hungarian): MTA III Oszt. Közl. 11 (1961), 79–105)