Skip to main content
\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)
Mathematics LibreTexts

05 The Borel-Cantelli Lemmas

Let \((\Omega, {\cal F}, \prob)\) be a probability space, and let \(A_1, A_2, A_3, \ldots \in {\cal F}\) be a sequence of events. We define the following events derived from the sequence \((A_n)_n\):

\limsup A_n &=& \bigcap_{N=1}^\infty \bigcup_{n=N}^\infty A_n, \\
\liminf A_n &=& \bigcup_{N=1}^\infty \bigcap_{n=N}^\infty A_n.

What is the meaning of these events? If we think of the sequence \(A_n\) as representing a sequence of (not necessarily independent) probabilistic experiments, then we can translate the first event into words as

\limsup A_n &=& \textrm{``the event that for all \(N\ge 1\) there is an \(n\ge N\) such}
\\ &  & \textrm{that \(A_n\) occurred''} \\ &=& \textrm{``the event that infinitely many of the \(A_n$'s occurred''.}

For this reason, the event \(\limsup A_n\) is often denoted by \(\{ A_n\textrm{ infinitely often}\}\) or \(\{A_n \textrm{ i.o.}\}\).

The definition of the event \(\liminf A_n\) can similarly be given meaning by writing
\liminf A_n &=& \textrm{``the event that there exists an \(N\ge 1\) such that \(A_n\) }
\\ &  & \textrm{occurred for all \(n\ge N$''} \\ &=& \textrm{``the event that all but finitely many of the \(A_n$'s occurred''.}

Prove that for any \(\omega \in \Omega\) we have
\ind_{\limsup A_n}(\omega) &=& \limsup_{n\to\infty} \ind_{A_n}(\omega), \\
\ind_{\liminf A_n}(\omega) &=& \liminf_{n\to\infty} \ind_{A_n}(\omega).

\begin{thm}[Borel-Cantelli lemmas] \

  1. \If\ \ \(\sum_{n=1}^\infty \prob(A_n) < \infty\) then \(\prob(A_n\textrm{ i.o.}) = 0\).
  2. \If\ \ \(\sum_{n=1}^\infty \prob(A_n) = \infty\) and \((A_n)_{n=1}^\infty\) are independent then \(\prob(A_n\textrm{ i.o.}) = 1\).



We essentially already proved part (i) in the first lecture, but here is a more general repetition of the same argument.

\[ \prob(A_n\textrm{ i.o.}) = \prob\left(\bigcap_{N=1}^\infty \bigcup_{n=N}^\infty A_n \right) %\\
\le \inf_{N\ge1}  \prob\left( \bigcup_{n=N}^\infty A_n\right) \le \inf_{N\ge 1} \sum_{n=N}^\infty \prob(A_n). \]
Since we assumed that \(\sum_{n=1}^\infty \prob(A_n)\), converges, this last expression is equal to \(0\).

Proof of (ii):
Consider the complementary event that the \(A_n$'s did \emph{not} occur for infinitely many values of \(n\). Using De-Morgan's laws, we get

\prob(\{A_n\textrm{ i.o.}\}^c) &=& \prob\left(\left(\bigcap_{N=1}^\infty \bigcup_{n=N}^\infty A_n\right)^c \right) = \prob\left( \bigcup_{N=1}^\infty \bigcap_{n=N}^\infty A_n^c \right)
\\ &\le &\sum_{N=1}^\infty \prob\left( \bigcap_{n=N}^\infty A_n^c \right).

So, to show that this is 0 (under the assumptions that \(\sum_{n=1}^\infty \prob(A_n) = \infty\) and that the events are independent), we show that \(\prob\left( \cap_{n=N}^\infty A_n^c \right) = 0\) for all \(N\ge 1\). Since the events are independent, the probability of the intersection is the product of the probabilities, so we need to show that

\[ \prod_{n=N}^\infty (1-\prob(A_n)) = 0, \]

or equivalently (taking minus the logarithm) that

\[ -\sum_{n=N}^\infty \log(1-\prob(A_n)) = \infty. \]

But \)-\log(1-x) \ge x\) for all \(x>0\), so this follows from the assumption that the series of probabilities diverges.