Borel-Cantelli Lemma

Let $\{A_n\}$ be a sequence of events and $A:=\{A_n\text{ i.o.}\}:={\cap }_{n=1}^{\infty }{\cup }_{i=n}^{\infty }{A}_i$

1. If ${\sum }_{n=1}^{\infty }P(A_n)<\infty$, then $P(A)=0$.
2. If ${\sum }_{n=1}^{\infty }P(A_n)=\infty$ and $A_n$ are Independent, then $P(A)=1$.
   • The independence is crucial here. The lemma does not hold if the events are not independent.

Proof

Part 1

Since the infinite sum is bounded, we have ${\lim }_{n\to \infty }{\sum }_{i\ge n}P(A_i)=0$. By the definition of $A$, we have

$$P(A)\le P({\cup }_{i=n}^{\infty }{A}_i)\le \sum _{i\ge n}P(A_i)\to 0.$$

Alternative Proof for Part 1

Let $X_n$ be the indicator r.v. for $A_n$. We know that $A$ happens if and only if ${\sum }_{n=1}^{\infty }{X}_n=\infty$. By Monotone Convergence Theorem,

$$\mathbb{E}\left[\sum _{n=1}^{\infty }{X}_n\right]=\sum _{n=1}^{\infty }\mathbb{E}[X_n]=\sum _{n=1}^{\infty }P(A_n)<\infty .$$

Therefore, ${\sum }_{n=1}^{\infty }{X}_n<\infty$ a.s. In other words, with probability 1, $\{A_n\text{ i.o.}\}$ will not happen, i.e., $P(A)=0$.

Part 2

Let $B_n={\cup }_{i\ge n}{A}_n$. By De Morgan’s law, we have

$$P(A^c)=P({\cup }_{n=1}^{\infty }{B}_n^c)\le \sum _{n\ge 1}P(B_n^c)$$

Note that the Independence of $\{A_n\}$ implies the independence of $\{A_n^c\}$ (using the conditional probability definition). Again, by De Morgan,

$$P(B_n^c)=P({\cap }_{i\ge n}{A}_i^c)=\prod _{i\ge n}P(A_i^c)=\prod _{i\ge n}(1-P(A_i)).$$

Note that ${\sum }_{n\ge 1}P(A_n)=\infty ⟹{\sum }_{i\ge n}P(A_i)=\infty$ for any finite $n$. We claim that ${\prod }_{i\ge n}(1-P(A_i))=0$:

$$\log \left(\prod _{i\ge n}(1-P(A_i))\right)=\sum _{i\ge n}\log (1-P(A_i))\le \sum _{i\ge n}(-P(A_i))=-\infty .$$

Therefore, $P(B_n^c)=0$ and then

$$P(A)=1-P(A^c)\ge 1-0=1.$$