Borel–Cantelli lemma

Let E₁,E₂,... be a sequence of events in some probability space. The Borel–Cantelli lemma states:[3]

If the sum of the probabilities of the event E_n is finite

${\displaystyle \sum _{n=1}^{\infty }\Pr(E_{n})<\infty ,}$

then the probability that infinitely many of them occur is 0, that is,

${\displaystyle \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,

${\displaystyle \limsup _{n\to \infty }E_{n}=\bigcap _{n=1}^{\infty }\bigcup _{k\geq n}^{\infty }E_{k}.}$

The set lim sup E_n is sometimes denoted {E_n i.o. }. 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.

Let (E_n) be a sequence of events in some probability space.

The sequence of events ${\textstyle \left\{\bigcup _{n=N}^{\infty }E_{n}\right\}_{N=1}^{\infty }}$ is non-increasing:

${\displaystyle \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,

${\displaystyle \Pr(\limsup _{n\to \infty }E_{n})=\lim _{N\to \infty }\Pr \left(\bigcup _{n=N}^{\infty }E_{n}\right).}$

By subadditivity,

${\displaystyle \Pr \left(\bigcup _{n=N}^{\infty }E_{n}\right)\leq \sum _{n=N}^{\infty }\Pr(E_{n}).}$

By original assumption, ${\textstyle \sum _{n=1}^{\infty }\Pr(E_{n})<\infty .}$ As the series ${\textstyle \sum _{n=1}^{\infty }\Pr(E_{n})}$ converges,

${\displaystyle \lim _{N\to \infty }\sum _{n=N}^{\infty }\Pr(E_{n})=0,}$

as required.

For general measure spaces, the Borel–Cantelli lemma takes the following form:

Let μ be a (positive) measure on a set X, with σ-algebra F, and let (A_n) be a sequence in F. If

${\displaystyle \sum _{n=1}^{\infty }\mu (A_{n})<\infty ,}$

then

${\displaystyle \mu \left(\limsup _{n\to \infty }A_{n}\right)=0.}$

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:

If ${\displaystyle \sum _{n=1}^{\infty }\Pr(E_{n})=\infty }$ and the events ${\displaystyle (E_{n})_{n=1}^{\infty }}$ are independent, then ${\displaystyle \Pr(\limsup _{n\rightarrow \infty }E_{n})=1.}$

The assumption of independence can be weakened to pairwise independence, but in that case the proof is more difficult.

Suppose that ${\displaystyle \sum _{n=1}^{\infty }\Pr(E_{n})=\infty }$ and the events ${\displaystyle (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

${\displaystyle 1-\Pr(\limsup _{n\rightarrow \infty }E_{n})=0.}$

Noting that:

${\displaystyle {\begin{aligned}1-\Pr(\limsup _{n\rightarrow \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\rightarrow \infty }E_{n}^{c}\right)=\lim _{N\rightarrow \infty }\Pr \left(\bigcap _{n=N}^{\infty }E_{n}^{c}\right)\end{aligned}}}$

it is enough to show: ${\displaystyle \Pr \left(\bigcap _{n=N}^{\infty }E_{n}^{c}\right)=0}$. Since the ${\displaystyle (E_{n})_{n=1}^{\infty }}$ are independent:

${\displaystyle {\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}))\\&\leq \prod _{n=N}^{\infty }\exp(-\Pr(E_{n}))\\&=\exp \left(-\sum _{n=N}^{\infty }\Pr(E_{n})\right)\\&=0.\end{aligned}}}$

This completes the proof. Alternatively, we can see ${\displaystyle \Pr \left(\bigcap _{n=N}^{\infty }E_{n}^{c}\right)=0}$ by taking negative the logarithm of both sides to get:

${\displaystyle {\begin{aligned}-\log \left(\Pr \left(\bigcap _{n=N}^{\infty }E_{n}^{c}\right)\right)&=-\log \left(\prod _{n=N}^{\infty }(1-\Pr(E_{n}))\right)\\&=-\sum _{n=N}^{\infty }\log(1-\Pr(E_{n})).\end{aligned}}}$

Since −log(1 − x) ≥ x for all x > 0, the result similarly follows from our assumption that ${\displaystyle \sum _{n=1}^{\infty }\Pr(E_{n})=\infty .}$

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 ${\displaystyle (A_{n})}$ is monotone increasing for sufficiently large indices. This Lemma says:

Let ${\displaystyle (A_{n})}$ be such that ${\displaystyle A_{k}\subseteq A_{k+1}}$, and let ${\displaystyle {\bar {A}}}$ denote the complement of ${\displaystyle A}$. Then the probability of infinitely many ${\displaystyle A_{k}}$ occur (that is, at least one ${\displaystyle A_{k}}$ occurs) is one if and only if there exists a strictly increasing sequence of positive integers ${\displaystyle (t_{k})}$ such that

${\displaystyle \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 ${\displaystyle (t_{k})}$ usually being the essence.

Let ${\displaystyle A_{n}}$ be a sequence of events with ${\displaystyle \sum \Pr(A_{n})=\infty }$ and ${\displaystyle \liminf _{k\to \infty }{\frac {\sum _{1\leq m,n\leq k}\Pr(A_{m}\cap A_{n})}{\left(\sum _{n=1}^{k}\Pr(A_{n})\right)^{2}}}<\infty ,}$ then there is a positive probability that ${\displaystyle A_{n}}$ occur infinitely often.

• Lévy's zero–one law
• Kuratowski convergence
• Infinite monkey theorem

• Prokhorov, A.V. (2001) [1994], "Borel–Cantelli lemma", Encyclopedia of Mathematics, EMS Press
• Feller, William (1961), An Introduction to Probability Theory and Its Application, John Wiley & Sons.
• Stein, Elias (1993), Harmonic analysis: Real-variable methods, orthogonality, and oscillatory integrals, Princeton University Press.
• Bruss, F. Thomas (1980), "A counterpart of the Borel Cantelli Lemma", J. Appl. Probab., 17: 1094–1101.
• Durrett, Rick. "Probability: Theory and Examples." Duxbury advanced series, Third Edition, Thomson Brooks/Cole, 2005.

• Planet Math Proof Refer for a simple proof of the Borel Cantelli Lemma