KindiakMath

The Union Bound

Let (\Omega, \mathcal F, \mathbb P) be a probability space.

Problem 1. For K_1, K_2, \dots\in \mathcal F, prove Boole’s inequality:

\displaystyle \mathbb P \left( \bigcup_{i=1}^\infty K_i \right) \leq \sum_{i=1}^\infty \mathbb P(K_i).

This result is also known as the union bound.

(Click for Solution)

Solution. Define L_1 := K_1 and inductively, L_{i+1} = K_{i+1} \backslash \bigcup_{j=1}^i K_j. We can check that \{L_i\} is pairwise mutually exclusive and L_i \subseteq K_i for each i. Furthermore, it is not hard to prove that

\displaystyle \bigcup_{i=1}^\infty K_i = \bigsqcup_{i=1}^\infty L_i.

To see this, we first note that (\supseteq) is obvious. For the direction (\subseteq), fix x \in K_i for some i. Take i to be the smallest by the well-ordering principle, so that x \notin \bigcup_{j=1}^{i-1} K_j. Therefore, x \in L_i, as required. Therefore,

\displaystyle \mathbb P\left( \bigcup_{i=1}^\infty K_i\right) = \mathbb P \left( \bigsqcup_{i=1}^\infty L_i \right) = \sum_{i=1}^\infty \mathbb P(L_i) \leq \sum_{i=1}^\infty \mathbb P(K_i) .

This is known as the disjoint union trick.

Problem 2. For K_1, K_2, \dots, K_n \in \mathcal F, prove Bonferroni’s inequality.

\displaystyle \mathbb P \left( \bigcap_{i=1}^n K_i \right) \geq \sum_{i=1}^n \mathbb P(K_i) - (n-1).

(Click for Solution)

Solution. Firstly, setting K_{n+i} = \emptyset for i \geq 0,

\displaystyle \mathbb P \left( \bigcup_{i=1}^n K_i \right) = \mathbb P \left( \bigcup_{i=1}^\infty K_i \right) \leq \sum_{i=1}^\infty \mathbb P(K_i) = \sum_{i=1}^n\mathbb P(K_i).

Defining L_i := \Omega \backslash K_i for i \geq 1, use Problem 1 to deduce

\begin{aligned} \mathbb P \left( \bigcap_{i=1}^n K_i \right) &= \mathbb P \left( \bigcap_{i=1}^n ( \Omega \backslash L_i ) \right) = \mathbb P \left( \Omega \backslash \bigcup_{i=1}^n L_i \right) \\ &= 1 - \mathbb P \left( \bigcup_{i=1}^n L_i \right) \geq 1 - \sum_{i=1}^n \mathbb P(L_i) \geq 1 - \sum_{i=1}^n \mathbb P(\Omega \backslash K_i) \\ &\geq 1 - \sum_{i=1}^n \mathbb (1 - \mathbb P(K_i)) = \sum_{i=1}^n \mathbb P(K_i) - (n-1). \end{aligned}

Corollary 1. We have the inequality

\displaystyle \mathbb P \left( \bigcup_{i=1}^n K_i \right) \leq \sum_{i=1}^n \mathbb P(K_i) \leq \mathbb P \left( \bigcap_{i=1}^n K_i \right) + (n-1).

—Joel Kindiak, 30 Aug 25, 2048H

,

Published by

joelkindiak

Leave a comment