Bonferroni-type inequalities
The Bonferroni inequalities may become impractical as a result of the large number of terms in (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 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 by limiting its number of terms, but only to an extent that still produces the Bonferroni bounds for some
. The new inequalities obtained in this manner are called Bonferroni-type inequalities. In other words, for i), given the values
,
, where
is a given finite set, one seeks coefficients
,
,
, and
such that, whatever the probability space and the events
on it,
![]() | (a1) |
and
![]() | (a2) |
where signifies summation over
. In the following simple example, all problems and difficulties arising in the solution of (a1) and (a2) are demonstrated.
Let , so that one can use
,
and
in setting the bounds in (a1) or (a2). Concentrating on (a2) and considering only
, one looks for coefficients
,
,
, and
(it easily follows that
) 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
and
no better bounds can be found than
![]() |
![]() |
where 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 if and only if it is valid for independent
with each
either equal to some
,
, 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
. 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
and
such that (a2) holds for
and some set
. Then both (a1) and (a2) hold for arbitrary
,
, with the set
obtained from
by adding
to each of its elements, and the coefficients of
in (a1) and (a2) satisfy the relations
![]() |
![]() |
Upon replacing by
in the right-hand sides above, one obtains
and
, respectively.
For modification ii) of the Bonferroni inequalities there are very general and very effective graph sieves. Choose an arbitrary graph with vertices (that is, the edge set is chosen in an arbitrary manner). Now define
by deleting many terms from
; in fact, retain in
only those terms of
for which
has no edge from the underlying graph just chosen if
is even, and allow, for
odd, a well-defined number of edges in
, the number of which may depend on
but not on
. Define
in a similar manner, but interchange the role of "even" and "odd" . It is proved in [a8], for
, and in [a1], for arbitrary
, that the Bonferroni lower bounds remain valid with
, whilst the upper bounds remain valid with
. These new bounds found many applications in random set selections, information theory, and extreme value theory; see [a5]. The basic idea of constructing
and
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) |
Bonferroni-type inequalities. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Bonferroni-type_inequalities&oldid=14744