# 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$.

Tags: