Problem
Let $A_1, A_2, ...$ be events. Show that:
$P(\bigcup_{n=1}^{\infty} A_n) \leq \sum_{n=1}^{\infty} P(A_n)$
Hint: define $B_n = A_n - \bigcup_{i=1}^{n-1}A_i$ and show:
- $B_n$ are disjoint
- $\bigcup_{n=1}^{\infty} A_n = \bigcup_{n=1}^{\infty} B_n$
Solution
Showing $B_n$ are disjoint
To show that $B_n$ are disjoint, we can show that $B_j \cap B_k = \emptyset \forall (j,k) \in \mathbb{N}$. We can assume $j < k$ without loss of generality.
$B_j \cap B_k$
= $(A_j - \bigcup_{i=1}^{j-1} A_i) \cap (A_k - \bigcup_{i=1}^{k-1} A_i)$
= $A_j \cap (\bigcup_{i=1}^{j-1} A_i)^c \cap A_k \cap (\bigcup_{i=1}^{k-1} A_i)^c$
= $A_j \cap (\bigcup_{i=1}^{j-1} A_i)^c \cap A_k \cap \bigcap_{i=1}^{k-1} A_i^c$
Note that we can pull out a $A_j^c$ from $\bigcap_{i=1}^{k-1} A_i^c$
= $A_j \cap A_j^c \cap (\bigcup_{i=1}^{j-1} A_i)^c \cap A_k \cap \bigcap_{i=1}^{k-1} A_i^c$
= $\emptyset \cap (\bigcup_{i=1}^{j-1} A_i)^c \cap A_k \cap \bigcap_{i=1}^{k-1} A_i^c$
= $\emptyset$
Showing $\bigcup_{n=1}^{\infty} A_n = \bigcup_{n=1}^{\infty} B_n$
We can prove that $\bigcup_{i=1}^{n} A_i = \bigcup_{i=1}^{n} B_i \forall n \in \mathbb{N}$ using induction.
Base case: $n=1$
$\bigcup_{i=1}^{1} B_i$
= $B_1$
= $A_1$
= $\bigcup_{i=1}^{1} A_i$
Inductive step
Assuming that $\bigcup_{i=1}^{n} A_i = \bigcup_{i=1}^{n} B_i$ and show that $\bigcup_{i=1}^{n+1} A_i = \bigcup_{i=1}^{n+1} B_i$ holds true.
$\bigcup_{i=1}^{n+1} B_i$
= $B_{n+1} \cup \bigcup_{i=1}^{n} B_i$
= $B_{n+1} \cup \bigcup_{i=1}^{n} A_i$ (by inductive assumption)
= $(A_{n+1} \cap (\bigcup_{i=1}^{n} A_i)^c) \cup \bigcup_{i=1}^{n} A_i$
= $[\bigcup_{i=1}^{n} A_i \cup A_{n+1}] \cap [\bigcup_{i=1}^{n} A_i \cup (\bigcup_{i=1}^{n} A_i)^c]$ (union distributes over intersection!)
= $\bigcup_{i=1}^{n+1} A_i \cap \Omega$
= $\bigcup_{i=1}^{n+1} A_i$
Putting it all together
$P(\bigcup_{n=1}^{\infty} A_n)$
= $P(\bigcup_{n=1}^{\infty} B_n)$
= $\sum_{n=1}^{\infty} P(B_n)$ (since $B_n$ are disjoint)
= $\sum_{n=1}^{\infty} P(A_n - \bigcup_{i=1}^{n-1}A_i) \leq \sum_{n=1}^{\infty} P(A_n)$
Sources
- 36-705 hw1 problem 5