Borel-Cantelli lemma
Published:
In this entry we will discuss the Borel-Cantelli lemma. Despite it being usually called just a lemma, it is without any doubts one of the most important and foundational results of probability theory: it is one of the essential zero-one laws, and it allows us to prove a variety of almost-sure results.
First Borel-Cantelli lemma
Suppose that $A_1,\dots$ is a sequence of events in $\Omega$. We define its limsup as the sets
\[\limsup_n A_n = \bigcap_{n=1}^\infty \bigcup_{k=n}^\infty A_n.\]In other words, $\limsup A_n$ can be thought as the set of points $\omega\in\Omega$ belonging to infinitely many of the sets $A_n$. The Borel-Cantelli lemma gives us conditions for when the limsup of the sequence has either full measure or zero measure.
Theorem (Borel-Cantelli): Suppose that
\[\sum_{n=1}^{\infty} \mathbb{P}(A_n) \lt \infty .\]Then
\[\mathbb{P}\left(\limsup_{n} A_n \right) = 0.\]Proof: Note that
\[\mathbb{P}\left(\bigcap_{n=1}^{\infty} \bigcup_{k=n}^{\infty} A_{k}\right) = \lim_{n \to \infty} \mathbb{P}\left(\bigcup_{k=n}^{\infty} A_{k}\right) \leq \lim_{n \to \infty} \sum_{m=n}^{\infty} \mathbb{P}(A_m) = 0\]since $\sum_n \mathbb{P}(A_n) < \infty$. This proves the statement $\square$.
The converse is not true in general: consider in $[0,1]$ with the usual Borel structure, and the sets $A_n = [0,\frac{1}{n}]$, with corresponding probabilities $\mathbb{P}(A_n) = \frac{1}{n}$. The limsup of the sequence is {$0$}, which has probability zero, while the sum of the probabilities is infinte.
Second Borel-Cantelli lemma
The second Borel-Cantelli lemma provides a partial converse: if the events {$A_n$} are independent, then the converse is true.
Theorem (Borel-Cantelli) Suppose that the sequence ${A_n }$ is independent and
\[\sum_{n=1}^{\infty} \mathbb{P}(A_n) = \infty .\]Then
\[\mathbb{P}\left(\limsup_{n} A_n \right) = 1.\]Proof:
We will prove that
\[\mathbb{P}\left(\limsup_{n} A_n \right)^c = 0.\]Note that
\[\mathbb{P}\left(\limsup_{n} A_n \right)^c = \sum_{n=1}^\infty\mathbb{P} \left(\bigcup_{k=n}^\infty A_k \right)^c.\]But
\[\mathbb{P} \left(\bigcup_{k=n}^\infty A_k \right)^c \leq \mathbb{P}\left(\bigcap_{k=n}^\infty A_n^c \right) = \lim_{N \to \infty} \mathbb{P}\left(\bigcap_{k=n}^{N} A_{k}^{c}\right) = \lim_{N \to \infty} \prod_{k=n}^{N} \mathbb{P}\left(A_{k}^{c}\right)\] \[= \lim_{N \to \infty} \prod_{k=n}^{N} (1-\mathbb{P}(A_{k})) \leq \lim_{N \to \infty} \prod_{k=n}^{N} \exp(-\mathbb{P}(A_n)) = \lim_{N \to \infty} \exp(-\sum_{k=n}^{N}\mathbb{P}(A_n) ) = 0.\]Here we used that for $x\geq 0$, $1-x \leq \exp(-x)$ $\square$.
Leave a Comment