# 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

Then

\[\mathbb{P}\left(\limsup_{n} A_n \right) = 0.\]**Proof:** Note that

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

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