---
tag: N8SE78CN33
kind: proof
name: Proof of the second Borel–Cantelli lemma
msc: [60F20]
proves: 0NWXRAMEE7
uses: [0GCVEV6BJA, 0PQEBTYDZM, 012C7GFF20, 0X8HBKCSYB, 0EGSEE9J9R, 0VK0W4D5Y5]
sources:
  - url: https://en.wikipedia.org/wiki/Borel–Cantelli_lemma
    locator: Converse result
---

## Proof

We show that the complement of $\limsup_n A_n$ has probability $0$.

1. Let $L = \limsup_n A_n = \bigcap_{n \ge 1} \bigcup_{m \ge n} A_m$. By [[De Morgan's laws|0VK0W4D5Y5]], $\Omega \setminus L = \bigcup_{n \ge 1} C_n$ with $C_n = \bigcap_{m \ge n} A_m^c$.
2. Claim: let $J$ be a finite nonempty set of indices, and let $K \subseteq J$. Put $E_j = A_j^c$ for $j \in K$ and $E_j = A_j$ for $j \in J \setminus K$. Then $P\left(\bigcap_{j \in J} E_j\right) = \prod_{j \in J} P(E_j)$.
3. We prove the claim by induction on the size of $K$. For $K = \varnothing$, it is the definition of [[mutually independent|0GCVEV6BJA]] events.
4. Let $K \ne \varnothing$, and assume the claim for all smaller sets $K$. Pick $l \in K$, and let $D = \bigcap_{j \in J \setminus \set{l}} E_j$, with $D = \Omega$ if $J = \set{l}$.
5. By the induction hypothesis, $P(D) = \prod_{j \ne l} P(E_j)$ and $P(A_l \cap D) = P(A_l) P(D)$. So $P(A_l^c \cap D) = P(D) - P(A_l \cap D) = (1 - P(A_l)) P(D)$.
6. By the [[probability of the complement|0PQEBTYDZM]], $1 - P(A_l) = P(A_l^c)$. So the product formula holds for $K$, which proves the claim.
7. Fix $n \ge 1$ and $N \ge n$. By step 2, $P\left(\bigcap_{m = n}^{N} A_m^c\right) = \prod_{m=n}^{N} (1 - P(A_m))$.
8. By the inequality [[$1 + x \le e^x$|012C7GFF20]] with $x = -P(A_m)$, each factor satisfies $0 \le 1 - P(A_m) \le e^{-P(A_m)}$. So the product is at most $\exp\left(-\sum_{m=n}^{N} P(A_m)\right)$.
9. Since $\sum_{m \ge 1} P(A_m) = \infty$ and the finitely many terms with $m < n$ are finite, $\sum_{m=n}^{N} P(A_m) \to \infty$ as $N \to \infty$. So the bound in step 8 tends to $0$.
10. The events $\bigcap_{m=n}^{N} A_m^c$ decrease in $N$ to $C_n$. By the [[continuity of probability|0X8HBKCSYB]], $P(C_n) = \lim_{N} P\left(\bigcap_{m=n}^{N} A_m^c\right) = 0$.
11. By step 1 and [[Boole's inequality|0EGSEE9J9R]], $P(\Omega \setminus L) \le \sum_{n \ge 1} P(C_n) = 0$.
12. So $P(L) = 1$. An outcome lies in $L$ exactly when, for each $n$, it lies in some $A_m$ with $m \ge n$, that is, in infinitely many $A_m$. So almost surely infinitely many of the events occur.

## Idea

Not being in $\limsup_n A_n$ means avoiding all $A_m$ from some index on. By independence, avoiding $A_n, \dots, A_N$ has probability $\prod (1 - P(A_m))$. A divergent sum $\sum P(A_m)$ forces this product to $0$, by the bound $1 - x \le e^{-x}$.