# Borel–Cantelli lemma

__: Theorem in probability__

**Short description**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.^{[1]}^{[2]} 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:^{[3]}

**Borel–Cantelli lemma** — If the sum of the probabilities of the events {*E*_{n}} is finite
[math]\displaystyle{ \sum_{n=1}^\infty \Pr(E_n)\lt \infty, }[/math]
then the probability that infinitely many of them occur is 0, that is,
[math]\displaystyle{ \Pr\left(\limsup_{n\to\infty} E_n\right) = 0. }[/math]

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,
[math]\displaystyle{ \limsup_{n\to\infty} E_n = \bigcap_{n=1}^\infty \bigcup_{k = n}^\infty E_k. }[/math]

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 [math]\displaystyle{ \left\{\bigcup_{n=N}^\infty E_n\right\}^\infty_{N=1} }[/math] is non-increasing: [math]\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. }[/math]

By continuity from above, [math]\displaystyle{ \Pr(\limsup_{n \to \infty} E_n) = \lim_{N\to\infty}\Pr\left(\bigcup_{n=N}^\infty E_n\right). }[/math]

By subadditivity, [math]\displaystyle{ \Pr\left(\bigcup_{n=N}^\infty E_n\right) \leq \sum^\infty_{n=N} \Pr(E_n). }[/math]

By original assumption, [math]\displaystyle{ \sum_{n=1}^\infty \Pr(E_n)\lt \infty. }[/math] As the series [math]\displaystyle{ \sum_{n=1}^\infty \Pr(E_n) }[/math] converges,
[math]\displaystyle{ \lim_{N\to\infty} \sum^\infty_{n=N} \Pr(E_n)=0, }[/math]
as required.^{[4]}

## 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
[math]\displaystyle{ \sum_{n=1}^\infty\mu(A_n)\lt \infty, }[/math]
then
[math]\displaystyle{ \mu\left(\limsup_{n\to\infty} A_n\right) = 0. }[/math]

## 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 [math]\displaystyle{ \sum^{\infty}_{n = 1} \Pr(E_n) = \infty }[/math] and the events [math]\displaystyle{ (E_n)^{\infty}_{n = 1} }[/math] are independent, then [math]\displaystyle{ \Pr(\limsup_{n \to \infty} E_n) = 1. }[/math]

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

### Example

The infinite monkey theorem, that endless typing at random will, with probability 1, eventually produce every finite text (such as the works of Shakespeare), amounts to the statement that a (not necessarily fair) coin tossed infinitely often will eventually come up Heads. This is a special case of the second Lemma.

The lemma can be applied to give a covering theorem in **R**^{n}. Specifically (Stein 1993), if *E*_{j} is a collection of Lebesgue measurable subsets of a compact set in **R**^{n} such that
[math]\displaystyle{ \sum_j \mu(E_j) = \infty, }[/math]
then there is a sequence *F*_{j} of translates
[math]\displaystyle{ F_j = E_j + x_j }[/math]
such that
[math]\displaystyle{ \lim\sup F_j = \bigcap_{n=1}^\infty \bigcup_{k=n}^\infty F_k = \mathbb{R}^n }[/math]
apart from a set of measure zero.

## Proof

Suppose that [math]\displaystyle{ \sum_{n = 1}^\infty \Pr(E_n) = \infty }[/math] and the events [math]\displaystyle{ (E_n)^\infty_{n = 1} }[/math] 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
[math]\displaystyle{ 1-\Pr(\limsup_{n \to \infty} E_n) = 0. }[/math]

Noting that: [math]\displaystyle{ \begin{align} 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{align} }[/math] it is enough to show: [math]\displaystyle{ \Pr\left(\bigcap_{n=N}^{\infty} E_n^{c}\right) = 0 }[/math]. Since the [math]\displaystyle{ (E_n)^{\infty}_{n = 1} }[/math] are independent: [math]\displaystyle{ \begin{align} \Pr\left(\bigcap_{n=N}^\infty E_n^c\right) &= \prod^\infty_{n=N} \Pr(E_n^c) \\ &= \prod^\infty_{n=N} (1-\Pr(E_n)) \\ &\leq\prod^\infty_{n=N} \exp(-\Pr(E_n))\\ &=\exp\left(-\sum^\infty_{n=N} \Pr(E_n)\right)\\ &= 0. \end{align} }[/math]

This completes the proof. Alternatively, we can see [math]\displaystyle{ \Pr\left(\bigcap_{n=N}^\infty E_n^c \right) = 0 }[/math] by taking negative the logarithm of both sides to get: [math]\displaystyle{ \begin{align} -\log\left(\Pr\left(\bigcap_{n=N}^{\infty}E_n^{c}\right)\right) &= -\log\left(\prod^{\infty}_{n=N} (1-\Pr(E_n))\right) \\ &= - \sum^\infty_{n=N}\log(1-\Pr(E_n)). \end{align} }[/math]

Since −log(1 − *x*) ≥ *x* for all *x* > 0, the result similarly follows from our assumption that [math]\displaystyle{ \sum^\infty_{n = 1} \Pr(E_n) = \infty. }[/math]^{[4]}

## 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 [math]\displaystyle{ (A_n) }[/math] is monotone increasing for sufficiently large indices. This Lemma says:

Let [math]\displaystyle{ (A_n) }[/math] be such that [math]\displaystyle{ A_k \subseteq A_{k+1} }[/math], and let [math]\displaystyle{ \bar A }[/math] denote the complement of [math]\displaystyle{ A }[/math]. Then the probability of infinitely many [math]\displaystyle{ A_k }[/math] occur (that is, at least one [math]\displaystyle{ A_k }[/math] occurs) is one if and only if there exists a strictly increasing sequence of positive integers [math]\displaystyle{ ( t_k) }[/math] such that [math]\displaystyle{ \sum_k \Pr( A_{t_{k+1}} \mid \bar A_{t_k}) = \infty. }[/math]

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 [math]\displaystyle{ (t_k) }[/math] usually being the essence.

## Kochen–Stone

Let [math]\displaystyle{ A_n }[/math] be a sequence of events with [math]\displaystyle{ \sum\Pr(A_n)=\infty }[/math] and [math]\displaystyle{ \liminf_{k\to\infty} \frac{\sum_{1\le m,n \le k} \Pr(A_m\cap A_n)} {\left(\sum_{n=1}^k\Pr(A_n)\right)^2} \lt \infty, }[/math] then there is a positive probability that [math]\displaystyle{ A_n }[/math] occur infinitely often.

## See also

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

## References

- ↑ E. Borel, "Les probabilités dénombrables et leurs applications arithmetiques"
*Rend. Circ. Mat. Palermo*(2)**27**(1909) pp. 247–271. - ↑ F.P. Cantelli, "Sulla probabilità come limite della frequenza",
*Atti Accad. Naz. Lincei*26:1 (1917) pp.39–45. - ↑ Klenke, Achim (2006).
*Probability Theory*. Springer-Verlag. ISBN 978-1-84800-047-6. - ↑
^{4.0}^{4.1}"Romik, Dan. Probability Theory Lecture Notes, Fall 2009, UC Davis.". http://www.math.ucdavis.edu/~romik/teaching/lectures.pdf.

- Hazewinkel, Michiel, ed. (2001), "Borel–Cantelli lemma",
*Encyclopedia of Mathematics*, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4, https://www.encyclopediaofmath.org/index.php?title=B/b017040 - 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.

## External links

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

Original source: https://en.wikipedia.org/wiki/Borel–Cantelli lemma.
Read more |