# Borel–Cantelli lemma

In probability theory, the Borel–Cantelli lemma is a theorem about sequences of events. In general, it is a result in measure theory. It is named after Émile Borel and Francesco Paolo Cantelli, who gave statement to the lemma in the first decades of the 20th century. A related result, sometimes called the second Borel–Cantelli lemma, is a partial converse of the first Borel–Cantelli lemma. The lemma states that, under certain conditions, an event will have probability of either zero or one. Accordingly, it is the best-known of a class of similar theorems, known as zero-one laws. Other examples include Kolmogorov's zero–one law and the Hewitt–Savage zero–one law.

## Statement of lemma for probability spaces

Let E$_1$, E$_2$, ... be a sequence of events in some probability space. The Borel–Cantelli lemma states:
Borel–Cantelli lemma — If the sum of the probabilities of the events {E$_n$} is finite $\sum _{n=1}^{\infty }\Pr(E_{n})<\infty ,$ then the probability that infinitely many of them occur is 0, that is, $\Pr \left(\limsup _{n\to \infty }E_{n}\right)=0.$
Here, "lim sup" denotes limit supremum of the sequence of events, and each event is a set of outcomes. That is, lim sup E$_n$ is the set of outcomes that occur infinitely many times within the infinite sequence of events (E$_n$). Explicitly, $\limsup _{n\to \infty }E_{n}=\bigcap _{n=1}^{\infty }\bigcup _{k=n}^{\infty }E_{k}.$The set lim sup E$_n$ is sometimes denoted {E$_n$ i.o.}, where "i.o." stands for "infinitely often". The theorem therefore asserts that if the sum of the probabilities of the events E$_n$ is finite, then the set of all outcomes that are "repeated" infinitely many times must occur with probability zero. Note that no assumption of independence is required.

### Example

Suppose (X$_n$) is a sequence of random variables with Pr(X$_n$ = 0) = 1/n$^2$ for each n. The probability that X$_n$ = 0 occurs for infinitely many n is equivalent to the probability of the intersection of infinitely many [X$_n$ = 0] events. The intersection of infinitely many such events is a set of outcomes common to all of them. However, the sum ΣPr(X$_n$ = 0) converges to π$^2$/6 ≈ 1.645 < ∞, and so the Borel–Cantelli Lemma states that the set of outcomes that are common to infinitely many such events occurs with probability zero. Hence, the probability of X$_n$ = 0 occurring for infinitely many n is 0. Almost surely (i.e., with probability 1), X$_n$ is nonzero for all but finitely many n.

## Proof

Let (E$_n$) be a sequence of events in some probability space.
The sequence of events {⋃$_{n=N}$$^∞$E$_n$}$_{N=1}$$^∞${\textstyle \left\{\bigcup _{n=N}^{\infty }E_{n}\right\}_{N=1}^{\infty }} is non-increasing: $\bigcup _{n=1}^{\infty }E_{n}\supseteq \bigcup _{n=2}^{\infty }E_{n}\supseteq \cdots \supseteq \bigcup _{n=N}^{\infty }E_{n}\supseteq \bigcup _{n=N+1}^{\infty }E_{n}\supseteq \cdots \supseteq \limsup _{n\to \infty }E_{n}.$By continuity from above, $\Pr(\limsup _{n\to \infty }E_{n})=\lim _{N\to \infty }\Pr \left(\bigcup _{n=N}^{\infty }E_{n}\right).$By subadditivity, $\Pr \left(\bigcup _{n=N}^{\infty }E_{n}\right)\leq \sum _{n=N}^{\infty }\Pr(E_{n}).$By original assumption, ∑$_{n=1}$$^∞$Pr(E$_n$)<∞.{\textstyle \sum _{n=1}^{\infty }\Pr(E_{n})<\infty .} As the series ∑$_{n=1}$$^∞$Pr(E$_n$){\textstyle \sum _{n=1}^{\infty }\Pr(E_{n})} converges, $\lim _{N\to \infty }\sum _{n=N}^{\infty }\Pr(E_{n})=0,$ as required.

## General measure spaces

For general measure spaces, the Borel–Cantelli lemma takes the following form:
Borel–Cantelli Lemma for measure spaces — Let μ be a (positive) measure on a set X, with σ-algebra F, and let (A$_n$) be a sequence in F. If $\sum _{n=1}^{\infty }\mu (A_{n})<\infty ,$ then $\mu \left(\limsup _{n\to \infty }A_{n}\right)=0.$

## Converse result

A related result, sometimes called the second Borel–Cantelli lemma, is a partial converse of the first Borel–Cantelli lemma. The lemma states: If the events E$_n$ are independent and the sum of the probabilities of the E$_n$ diverges to infinity, then the probability that infinitely many of them occur is 1. That is:
Second Borel–Cantelli Lemma — If $\sum _{n=1}^{\infty }\Pr(E_{n})=\infty$ and the events $(E_{n})_{n=1}^{\infty }$ are independent, then $\Pr(\limsup _{n\to \infty }E_{n})=1.$
The assumption of independence can be weakened to pairwise independence, but in that case the proof is more difficult.
The infinite monkey theorem follows from this second lemma.

### Example

The lemma can be applied to give a covering theorem in R$^n$. Specifically (Stein 1993, Lemma X.2.1), if E$_j$ is a collection of Lebesgue measurable subsets of a compact set in R$^n$ such that $\sum _{j}\mu (E_{j})=\infty ,$ then there is a sequence F$_j$ of translates $F_{j}=E_{j}+x_{j}$ such that $\lim \sup F_{j}=\bigcap _{n=1}^{\infty }\bigcup _{k=n}^{\infty }F_{k}=\mathbb {R} ^{n}$ apart from a set of measure zero.

### Proof

Suppose that ∑$_{n=1}$$^∞$Pr(E$_n$)=∞{\textstyle \sum _{n=1}^{\infty }\Pr(E_{n})=\infty } and the events $(E_{n})_{n=1}^{\infty }$ are independent. It is sufficient to show the event that the E$_n$'s did not occur for infinitely many values of n has probability 0. This is just to say that it is sufficient to show that $1-\Pr(\limsup _{n\to \infty }E_{n})=0.$
Noting that: ${\begin{aligned}1-\Pr(\limsup _{n\to \infty }E_{n})&=1-\Pr \left(\{E_{n}{\text{ i.o.}}\}\right)=\Pr \left(\{E_{n}{\text{ i.o.}}\}^{c}\right)\\&=\Pr \left(\left(\bigcap _{N=1}^{\infty }\bigcup _{n=N}^{\infty }E_{n}\right)^{c}\right)=\Pr \left(\bigcup _{N=1}^{\infty }\bigcap _{n=N}^{\infty }E_{n}^{c}\right)\\&=\Pr \left(\liminf _{n\to \infty }E_{n}^{c}\right)=\lim _{N\to \infty }\Pr \left(\bigcap _{n=N}^{\infty }E_{n}^{c}\right),\end{aligned}}$ it is enough to show: Pr(⋂$_{n=N}$$^∞$E$_n$$^c$)=0{\textstyle \Pr \left(\bigcap _{n=N}^{\infty }E_{n}^{c}\right)=0}. Since the $(E_{n})_{n=1}^{\infty }$ are independent: ${\begin{aligned}\Pr \left(\bigcap _{n=N}^{\infty }E_{n}^{c}\right)&=\prod _{n=N}^{\infty }\Pr(E_{n}^{c})\\&=\prod _{n=N}^{\infty }(1-\Pr(E_{n})).\end{aligned}}$ The convergence test for infinite products guarantees that the product above is 0, if ∑$_{n=N}$$^∞$Pr(E$_n$){\textstyle \sum _{n=N}^{\infty }\Pr(E_{n})} diverges. This completes the proof.

## Counterpart

Another related result is the so-called counterpart of the Borel–Cantelli lemma. It is a counterpart of the Lemma in the sense that it gives a necessary and sufficient condition for the limsup to be 1 by replacing the independence assumption by the completely different assumption that $(A_{n})$ is monotone increasing for sufficiently large indices. This Lemma says:
Let $(A_{n})$ be such that $A_{k}\subseteq A_{k+1}$, and let ${\bar {A}}$ denote the complement of $A$. Then the probability of infinitely many $A_{k}$ occur (that is, at least one $A_{k}$ occurs) is one if and only if there exists a strictly increasing sequence of positive integers $(t_{k})$ such that $\sum _{k}\Pr(A_{t_{k+1}}\mid {\bar {A}}_{t_{k}})=\infty .$This simple result can be useful in problems such as for instance those involving hitting probabilities for stochastic process with the choice of the sequence $(t_{k})$ usually being the essence.

## Kochen–Stone

Let $(A_{n})$ be a sequence of events with ∑Pr(A$_n$)=∞{\textstyle \sum \Pr(A_{n})=\infty } and lim sup$_{k→∞}$ (∑$_{n=1}$$^k$Pr(A$_n$))$^2$/∑$_{1≤m, n≤k}$Pr(A$_m$∩A$_n$) >0.{\textstyle \limsup _{k\to \infty }{\frac {\left(\sum _{n=1}^{k}\Pr(A_{n})\right)^{2}}{\sum _{1\leq m, n\leq k}\Pr(A_{m}\cap A_{n})}}>0.} Then there is a positive probability that $A_{n}$ occur infinitely often.

### Proof

Let $S_{m,n}=\sum _{i=m}^{n}\mathbf {1} _{A_{i}}$. Then, note that $E[S_{m,n}]^{2}=\left(\sum _{i=m}^{n}\Pr(A_{i})\right)^{2}$ and $E[S_{m,n}^{2}]=\sum _{1\leq i\leq j\leq n}\Pr(A_{i}\cap A_{j}).$ Hence, we know that $\limsup _{n\to \infty }{\frac {\mathbb {E} [S_{1,n}]^{2}}{\mathbb {E} [S_{1,n}^{2}]}}>0.$ We have that $\Pr \left(\bigcup _{i=m}^{n}A_{i}\right)=\Pr(S_{m,n}>0).$ Now, notice that by the Cauchy-Schwarz Inequality, $\mathbb {E} [X]^{2}\leq \mathbb {E} [X\mathbf {1} _{\{X>0\}}]^{2}\leq \mathbb {E} [X^{2}]\Pr(X>0),$ therefore, $\Pr(S_{m,n}>0)\geq {\frac {\mathbb {E} [S_{m,n}]^{2}}{\mathbb {E} [S_{m,n}^{2}]}}.$ We then have ${\frac {\mathbb {E} [S_{m,n}]^{2}}{\mathbb {E} [S_{m,n}^{2}]}}\geq {\frac {E[S_{1,n}-S_{1,m-1}]^{2}}{E[S_{1,n}^{2}]}}.$ Given $m$, since $\lim _{n\to \infty }\mathbb {E} [S_{1,n}]=\infty$, we can find $n$ large enough so that ${\biggr |}{\frac {\mathbb {E} [S_{1,n}]-\mathbb {E} [S_{1,m-1}]}{\mathbb {E} [S_{1,n}]}}-1{\biggr |}<\epsilon ,$ for any given $\epsilon >0$. Therefore, $\lim _{m\to \infty }\sup _{n\geq m}\Pr \left(\bigcup _{i=m}^{n}A_{i}\right)\geq \lim _{m\to \infty }\sup _{n\geq m}{\frac {E[S_{1,n}]^{2}}{E[S_{1,n}^{2}]}}>0.$ But the left side is precisely the probability that the $A_{n}$ occur infinitely often since $\{A_{k}{\text{ i.o.}}\}=\{\omega \in \Omega :\forall m,\exists n\geq m{\text{ s.t. }}\omega \in A_{n}\}.$ We're done now, since we've shown that $P(A_{k}{\text{ i.o.}})>0.$