Proof of Bonferroni Inequalities


Definitions and Notation.

A measure spaceMathworldPlanetmath is a triple (X,Σ,μ), where X is a set, Σ is a σ-algebra over X, and μ:Σ[0,] is a measure, that is, a non-negative function that is countably additive. If AΣ, the characteristic functionMathworldPlanetmathPlanetmathPlanetmathPlanetmath of A is the function χA:XR defined by χA(x)=1 if xA, χA(x)=0 if xA. A unimodal sequence is a sequenceMathworldPlanetmath of real numbers a0,a1,,an for which there is an index k such that aiai+1 for i<k and aiai+1 for ik.

The proof of the following easy lemma is left to the reader:

Lemma 1.

If a0a1akak+1ak+2an is a unimodal sequence of non-negative real numbers with i=0n(-1)iai=0, then i=0j(-1)iai0 for even j and 0 for odd j.

Since the binomial sequence ((ai))0in with integer a>0 and integer na satisfies the hypothesisMathworldPlanetmath of Lemma 1, we have:

Corollary 1.

If a is a positive integer, i=0j(-1)i(ai)0 for even j and 0 for odd j.

Lemma 2.

Let (Ai)1in be a sequence of sets and let X=1inAi. For xX, let I(x) be the set of indices j such that xAj. If 1kn,

1i1<i2<<iknχAi1Ai2Aik(x)=(|I(x)|k)

for all xX.

Proof.

χAi1Ai2Aik(x)=1 if {i1,i2,,ik}I(x), and =0 otherwise. Therefore the sum equals the number of k-subsets of I(x), which is (|I(x)|k). ∎

Theorem 1.

Let (X,Σ,μ) be a measure space. If (Ai)1in is a finite sequence of measurable setsMathworldPlanetmath all having finite measure, and

Sj=μ(A1A2An)+k=1j(-1)k1i1<i2<<iknμ(Ai1Ai2Aik)

then Sj0 for even j, and 0 for odd j. Moreover, Sn=0 (Principle of Inclusion-Exclusion).

Proof.

Let Y=1inAi.

Sj = Y𝑑μ+k=1j(-1)k1i1<i2<<iknYχAi1Ai2Aik𝑑μ
= Y𝑑μ+k=1j(-1)kY(1i1<i2<<iknχAi1Ai2Aik)𝑑μ

By Lemma 2,

Sj = Y𝑑μ+k=1j(-1)kY(|I(x)|k)𝑑μ
= k=0j(-1)kY(|I(x)|k)𝑑μ
= Yk=0j(-1)k(|I(x)|k)dμ

Since |I(x)|>0 for xY, it follows from Corollary 1 that, in the last integral, the integrand is 0 for even j and 0 for odd j. Therefore the same is true for the integral itself. In additionPlanetmathPlanetmath, the integrand is identically 0 for j=n, hence Sn=0. ∎

This proof shows that at the heart of Bonferroni’s inequalities lie similar inequalities governing the binomial coefficientsMathworldPlanetmath.

Title Proof of Bonferroni Inequalities
Canonical name ProofOfBonferroniInequalities
Date of creation 2013-03-22 19:12:44
Last modified on 2013-03-22 19:12:44
Owner csguy (26054)
Last modified by csguy (26054)
Numerical id 6
Author csguy (26054)
Entry type Proof
Classification msc 60A99