Proof of Bonferroni Inequalities

Definitions and Notation.

A measure space is a triple $(X,\Sigma,\mu)$ , where $X$ is a set, $\Sigma$ is a $\sigma$ -algebra over $X$ , and $\mu\colon\Sigma\rightarrow[0,\infty]$ is a measure, that is, a non-negative function that is countably additive. If $A\in\Sigma$ , the characteristic function of $A$ is the function $\chi_{A}\colon X\rightarrow\mathbb{R}$ defined by $\chi_{A}(x)=1$ if $x\in A$ , $\chi_{A}(x)=0$ if $x\notin A$ . A unimodal sequence is a sequence of real numbers $a_{0},a_{1},\ldots,a_{n}$ for which there is an index $k$ such that $a_{i}\leq a_{i+1}$ for $i<k$ and $a_{i}\geq a_{i+1}$ for $i\geq k$ .

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

Lemma 1.

If $a_{0}\leq a_{1}\leq\ldots\leq a_{k}\geq a_{k+1}\geq a_{k+2}\geq\ldots\geq a_{n}$ is a unimodal sequence of non-negative real numbers with $\sum_{i=0}^{n}(-1)^{i}a_{i}=0$ , then $\sum_{i=0}^{j}(-1)^{i}a_{i}\geq 0$ for even $j$ and $\leq 0$ for odd $j$ .

Since the binomial sequence $(\binom{a}{i})_{0\leq i\leq n}$ with integer $a>0$ and integer $n\geq a$ satisfies the hypothesis of Lemma 1, we have:

Corollary 1.

If $a$ is a positive integer, $\sum_{i=0}^{j}(-1)^{i}\binom{a}{i}\geq 0$ for even $j$ and $\leq 0$ for odd $j$ .

Lemma 2.

Let $(A_{i})_{1\leq i\leq n}$ be a sequence of sets and let $X=\bigcup_{1\leq i\leq n}A_{i}$ . For $x\in X$ , let $I(x)$ be the set of indices $j$ such that $x\in A_{j}$ . If $1\leq k\leq n$ ,

\sum_{1\leq i_{1}<i_{2}<\ldots<i_{k}\leq n}\chi_{A_{i_{1}}\cap A_{i_{2}}\cap% \ldots\cap A_{i_{k}}}(x)=\binom{|I(x)|}{k}

for all $x\in X$ .

Proof.

$\chi_{A_{i_{1}}\cap A_{i_{2}}\cap\ldots\cap A_{i_{k}}}(x)=1$ if $\{i_{1},i_{2},\ldots,i_{k}\}\subseteq I(x)$ , and $=0$ otherwise. Therefore the sum equals the number of $k$ -subsets of $I(x)$ , which is $\binom{|I(x)|}{k}$ . ∎

Theorem 1.

Let $(X,\Sigma,\mu)$ be a measure space. If $(A_{i})_{1\leq i\leq n}$ is a finite sequence of measurable sets all having finite measure, and

S_{j}=\mu(A_{1}\cup A_{2}\cup\ldots\cup A_{n})+\sum_{k=1}^{j}(-1)^{k}\sum_{1% \leq i_{1}<i_{2}<\ldots<i_{k}\leq n}\mu(A_{i_{1}}\cap A_{i_{2}}\cap\ldots\cap A% _{i_{k}})

then $S_{j}\geq 0$ for even $j$ , and $\leq 0$ for odd $j$ . Moreover, $S_{n}=0$ (Principle of Inclusion-Exclusion).

Proof.

Let $Y=\bigcup_{1\leq i\leq n}A_{i}$ .

	$\displaystyle S_{j}$	$\displaystyle=$	$\displaystyle\int_{Y}d\mu+\sum_{k=1}^{j}(-1)^{k}\sum_{1\leq i_{1}<i_{2}<\ldots% <i_{k}\leq n}\int_{Y}\chi_{A_{i_{1}}\cap A_{i_{2}}\cap\ldots\cap A_{i_{k}}}d\mu$
		$\displaystyle=$	$\displaystyle\int_{Y}d\mu+\sum_{k=1}^{j}(-1)^{k}\int_{Y}(\sum_{1\leq i_{1}<i_{% 2}<\ldots<i_{k}\leq n}\chi_{A_{i_{1}}\cap A_{i_{2}}\cap\ldots\cap A_{i_{k}}})d\mu$

By Lemma 2,

$\displaystyle S_{j}$	$\displaystyle=$	$\displaystyle\int_{Y}d\mu+\sum_{k=1}^{j}(-1)^{k}\int_{Y}\binom{\|I(x)\|}{k}d\mu$
	$\displaystyle=$	$\displaystyle\sum_{k=0}^{j}(-1)^{k}\int_{Y}\binom{\|I(x)\|}{k}d\mu$
	$\displaystyle=$	$\displaystyle\int_{Y}\sum_{k=0}^{j}(-1)^{k}\binom{\|I(x)\|}{k}d\mu$

Since $|I(x)|>0$ for $x\in Y$ , it follows from Corollary 1 that, in the last integral, the integrand is $\geq 0$ for even $j$ and $\leq 0$ for odd $j$ . Therefore the same is true for the integral itself. In addition, the integrand is identically 0 for $j=n$ , hence $S_{n}=0$ . ∎

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

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