Borel Cantelli Lemma Proof Using Continuity

Theorem in probability

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 [edit]

Let E ₁,E ₂,... 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

$${\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 supE _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=n}^{\infty }E_{k}.}$$

The set lim supE _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 [edit]

Suppose (X _n ) is a sequence of random variables with Pr(X _n = 0) = 1/n ² 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 π ²/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 manyn.

Proof [edit]

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.^[4]

General measure spaces [edit]

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

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

then

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

Converse result [edit]

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 ${\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\to \infty }E_{n})=1.}$

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

Example [edit]

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 ⁿ . Specifically (Stein 1993, Lemma X.2.1), if E _j is a collection of Lebesgue measurable subsets of a compact set in R ⁿ such that

$${\displaystyle \sum _{j}\mu (E_{j})=\infty ,}$$

then there is a sequence F _j of translates

$${\displaystyle F_{j}=E_{j}+x_{j}}$$

such that

$${\displaystyle \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 [edit]

Suppose that ${\textstyle \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\to \infty }E_{n})=0.}$$

Noting that:

$${\displaystyle {\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: ${\textstyle \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})).\end{aligned}}}$$

The convergence test for infinite products guarantees that the product above is 0, if ${\textstyle \sum _{n=N}^{\infty }\Pr(E_{n})}$ diverges. This completes the proof.

Counterpart [edit]

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.

Kochen–Stone [edit]

Let ${\displaystyle A_{n}}$ be a sequence of events with ${\textstyle \sum \Pr(A_{n})=\infty }$ and ${\textstyle \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.

See also [edit]

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

References [edit]

1. ^ E. Borel, "Les probabilités dénombrables et leurs applications arithmetiques" Rend. Circ. Mat. Palermo (2) 27 (1909) pp. 247–271.
2. ^ F.P. Cantelli, "Sulla probabilità come limite della frequenza", Atti Accad. Naz. Lincei 26:1 (1917) pp.39–45.
3. ^ Klenke, Achim (2006). Probability Theory. Springer-Verlag. ISBN978-1-84800-047-6.
4. ^ "Romik, Dan. Probability Theory Lecture Notes, Fall 2009, UC Davis" (PDF). Archived from the original (PDF) on 2010-06-14.

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

External links [edit]

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

whiteleggehopearabits.blogspot.com

Source: https://en.wikipedia.org/wiki/Borel%E2%80%93Cantelli_lemma

Share this post