# 05 The Borel-Cantelli Lemmas

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

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\):

\begin{eqnarray*}

\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.

\end{eqnarray*}

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

\begin{eqnarray*}

\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''.}

\end{eqnarray*}

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

\begin{eqnarray*}

\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''.}

\end{eqnarray*}

\begin{exercise}

Prove that for any \(\omega \in \Omega\) we have

\begin{eqnarray*}

\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).

\end{eqnarray*}

\end{exercise}

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

\renewcommand{\labelenumi}{(\roman{enumi})}

\begin{enumerate}

- \If\ \ \(\sum_{n=1}^\infty \prob(A_n) < \infty\) then \(\prob(A_n\textrm{ i.o.}) = 0\).
- \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\).

\end{thm}

\begin{proof}

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

\begin{eqnarray*}

\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).

\end{eqnarray*}

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.

\end{proof}

### Contributors

- Dan Romik (UC Davis)