Steven R. Dunbar
Department of Mathematics
203 Avery Hall
University of Nebraska-Lincoln
Lincoln, NE 68588-0130
http://www.math.unl.edu
Voice: 402-472-3731
Fax: 402-472-8466

Topics in
Probability Theory and Stochastic Processes
Steven R. Dunbar

__________________________________________________________________________

Borel-Cantelli Lemmas with Examples

_______________________________________________________________________

Note: These pages are prepared with MathJax. MathJax is an open source JavaScript display engine for mathematics that works in all browsers. See http://mathjax.org for details on supported browsers, accessibility, copy-and-paste, and other features.

_______________________________________________________________________________________________

Rating

Rating

Mathematicians Only: prolonged scenes of intense rigor.

_______________________________________________________________________________________________

Section Starter Question

Section Starter Question

How would you define events that happen infinitely often in a sequence?

_______________________________________________________________________________________________

Key Concepts

Key Concepts

  1. The first, or “easy”, Borel-Cantelli lemma gives a criterion that an event happens infinitely often with probability 0 in terms of a convergent series.
  2. The second Borel-Cantelli lemma gives a criterion that independent events happens infinitely often with probability 1 in terms of a divergent series.
  3. The Borel-Cantelli Lemmas are the first examples of 0-1 Laws.
  4. The Borel-Cantelli Lemmas are the basis for several interesting results.

__________________________________________________________________________

Vocabulary

Vocabulary

  1. The Borel-Cantelli lemmas give a criterion for events to happen infinitely often with probability 0 or 1 in terms of an infinite series.
  2. The Borel-Cantelli Lemmas are the first examples of 0-1 Laws.

__________________________________________________________________________

Mathematical Ideas

Mathematical Ideas

Borel-Cantelli Lemmas

Definition. In probability space Ω with σ-field and probability measure , (Ω,, ), let (An)n=1 . Then the set

{An i.o.} = n=1 knAk = lim n knAk.

Recall that i.o. stands for “infinitely often.”

Lemma 1. An element ω {An i.o.} if and only if ω An for infinitely many n if and only if for all n there exists k n so that ω Ak.

The first of the two Borel-Cantelli lemmas is sometimes called the easy half, or the direct half.

Theorem 2 (First Borel-Cantelli Lemma). If

n=1 A n < ,

then

{An i.o.} = 0.

Proof. Let 𝜖 > 0 be given.

{An i.o.} = lim n knAk = lim n knAk k=n A k < 𝜖

for sufficiently large n. Hence {An i.o. = 0. □

The next Borel-Cantelli Lemma is sometimes called the hard half or the independent half. It is a partial converse to the first Borel-Cantelli Lemma.

Theorem 3 (Second Borel-Cantelli Lemma). If An is a sequence of independent events and if n=1 A n = , then

{An i.o.} = 1.

Proof. Using DeMorgan’s Law, note that

k=nA k = 1 k=nA kc .

The proof needs to show that k=nA kc = 0. Note that

k=nA kc = k=n A kc = k=n1 A n .

Taking the logarithm and using log(1 x) x gives

log k=n1 A k = k=n log 1 A k k=n A k = .

Therefore

k=nmA kc = exp k=nm A k

can be made arbitrarily small by choosing a large enough m, so k=nA kc is a negligible event. □

Remark. The Borel-Cantelli Lemmas are examples of 0-1 Laws. Some other examples include the Kolmogorov 0-1 Law and the Hewitt-Savage 0-1 Law.

Examples and Applications

Theorem 4. Let s be any finite sequence of k heads or tails (H or T). If An = {ω : (ωn,,ωn+k1) = s} and 0 < p =  Heads = ωn = 1 < 1. Then {An i.o.} = 1.

Proof. Let

B1 := {ω : (ω1,,ωk) = s} B2 := {ω : (ωk+1,,ω2k) = s} B3 := {ω : (ω2k+1,,ω3k) = s}

The Bk’s are independent and {An i.o.}{Bn i.o.}. Note that n=1 B n = n=1(p, 1 p)s = , so {Bn i.o.} = 1. □

Example. Let

k1 = 1 1 = 1 k2 = 2 2 = 2 k3 = 4 3 = 4

Set An = {ω Ω : ωkn = ωkn+1 = = ωkn+n1 = 1}. Then An i.o. = 0.

Example. Let

k1 = 1 1 = 1 k2 = 4 2 = 1 k3 = 16 3 = 1 k4 = 64 4 = 1

Set An = {ω Ω : ωkn = = ωkn+n1 = 1}. Then An i.o. = 1.

Example. Consider three independent sequences of fair coin flips: Y n(1),Y n(2),Y n(3), that is Y n(i) = ±1 = 1 2. The associated cumulative fortunes are Mn(1),M n(2),M n(3). Then

M2n(1) = M 2n(2) = M 2n(3) i.o. = 0.

Proof. Consider the probability of the event M2n(i) = 0 for all i i.o. The proof for other values is similar. Note that

M2n(i) = 0 = 2n n 1 2 2n 1 πn.

Using independence

M2n(1) = M 2n(2) = M 2n(3) = 0 1 πn32

so

n M2n(1) = M 2n(2) = M 2n(3) = 0 .

Hence

M2n(1) = M 2n(2) = M 2n(3) = 0 i.o. = 0.

Example. Let x = x0 + i=0xi 10i be a decimal expansion of x; i.e., x0 and xi {0,, 9} for i 1. Define Ln(x) = i=1nx i10i. For instance,

L1(π) = 10,L2(π) = 410,L3(π) = 1410,

and

L1(e) = 70,L2(e) = 170,L3(e) = 8170,.

This is a natural way to associate a sequence of real numbers to a real number through its decimal expansion. Given 𝜖n so that 𝜖n < , then for almost every x (with Lebesgue measure) there exists n(x) so that Ln(x) 𝜖n10n+1 for every n n(x).

Proposition 1. Let (Xn)n1 be a sequence of random variables. If n=1 |X n| > 𝜖 < for all 𝜖 > 0 then lim nXn = 0 almost surely.

Proof.

  1. Set An = |Xn| > 𝜖.
  2. An i.o. = 0, so for every 𝜖 > 0 there exists n0(ω,𝜖) 0 so that |Xn(ω)| 𝜖 for all n n0(ω,𝜖) almost surely.
  3. Take a sequence 𝜖 = 1 m for m . Throw out a negligible set for each 𝜖 = 1 m.
  4. Almost surely, then for ω there exists n0(ω0, 1 m) 0 and |Xn(ω)| 1 m for all n n0(ω, 1 m).
  5. |Xn| converges to 0 almost surely and so Xn converges to 0 almost surely.

Corollary 2. Let (Xn)n0 be a sequence of random variables. If n=1𝔼 |X n| converges, then Xn converges to zero, almost surely.

Proof. Recall that Markov’s Inequality says that

|Xn| a 𝔼 |Xn| a ,

and is sufficient to prove the corollary. □

Theorem 5 (Breiman, page 42, 3.17). Let Y i = ±1 = 2Xi 1 and set Mn = k=1nY i. If H1 2 (p = ωn = 1 1 2), then {Mn = 0 i.o.} = 0.

Proof.

M2n = 0 = 2n n pn(1 p)n 1 πnen2

by the Local Limit Theorem. Recall that the Local Limit Theorem (for k = 0) says

n M2n = 0 = 2 π p 1 p02 2p(1 p) 2n 2n exp 02 2(2n) + o(1) = K a2n n 1 + o(1) Ka2n n,

where

a = 2p(1 p) = 1,p = 1 2 < 1, p1 2.

Then M2n = 0 = 1 πn 1 + o(1). □

Theorem 6 (Breiman, page 42, 3.18). If p = 12, then {M2n = 0 i.o.} = 1.

Proof. Note that A2n = [M2n = 0] are not independent. Consider a subsequence n1 < n2 < n3 < . Select mk so that nk < mk < nk+1. Let Ck = {Y nk+1 + + Y mk nk}{Y mk+1 + + Y nk+1 mk}. Then Mnk = Y 1 + + Y nk nk because each Y i = ±1. If ω Ck, then Mmk 0 and Mnk+1 0; i.e., ω Ck implies that Mn = 0 at least once for nk + 1 n nk+1.

Remark. This is a standard trick in probability theory of considering stretches n1,n2, so far apart that the effect of what happened previously to nk is small compared to the amount Mn can change between nk and nk+1

Note that {Ck i.o.}{Mn = 0 i.o.} The proof needs to show that nk and mk can be selected so that k=1 C k = . Now the claim is: Given any 0 < α < 1 and any k 1 there exists an integer ϕ(k) so that |Mϕ(k)| < k α. In other words, most of our paths will be outside the band k Mn k after the point ϕ(k).

For fixed j note that Mn = j 0 as n Fix k so that |j|<k Mn = j 0 as n . Take ϕ(k) so large that |j|<k Mϕ(k) = j α. Let n1 = 1 and mk = nk + ϕ(nk) and nk+1 = mk + ϕ(mk). Then

Ck = Y nk+1 + + Y mk nk Y mk+1 + + Y nk+1 mk .

By symmetry,

Ck = 1 4 Y nk+1 + + Y mk nk Y mk+1 + + Y nk+1 mk = 1 4 Y 1 + + Y ϕ(nk) nk Y 1 + + Y ϕ(mk) mk = 1 4 1 α2.

Now adding all infinitely many of these fixed finite values gives an infinite value, so done by the Borel-Cantelli Lemma. □

The following proof is a slightly different version of the Borel-Cantelli proof of the Strong Law of Large Numbers in the previous section.

Proof. (of Strong Law with Borel Cantelli)

Consider coin flips with H = 1 = p and T = 0 = 1 p. Set Xn = ωn p so 𝔼[Xn] = 0 for the sequence of independent random variables(Xn)n=1.

𝔼 Sn n p4 = 𝔼 Sn np n 4 = 1 n4𝔼 i=14X i 4 = 1 n4 1i,j,k,ln𝔼 XiXjXkXl = 1 n4 i=1n𝔼 X i4 + 6 1i<jn𝔼 Xi2X j2 .

This last line came from the fact that if ij,k,l then

𝔼 XiXjXkXl = 𝔼 Xi 𝔼 XjXkXl = 0

where the first equality is by independence. Note that |Xi| = p or 1 p and both are less than 1. Then 𝔼 X14 1 and 𝔼 Xi2X j2 1 and so 𝔼 Sn n p4 1 n4 n + 3n(n 1) K n2 for a suitable value of K. By Corollary 11.11, 𝔼 Sn n p4 < and so Sn n p4 0 almost surely, which means that Sn n p 0 almost surely. □

Sources

This section is adapted from: Heads or Tails, by Emmanuel Lesigne, Student Mathematical Library Volume 28, American Mathematical Society, Providence, 2005, Chapter 11.5, pages 89-96, [2]. Theorems 5 and 6 and following remarks are adapted from Probability by Leo Breiman, Addison-Wesley, Reading MA, 1968, Chapters 1 and 3. [1].

_______________________________________________________________________________________________

Algorithms, Scripts, Simulations

Algorithms, Scripts, Simulations

Algorithm

Scripts

__________________________________________________________________________

Problems to Work

Problems to Work for Understanding

  1. Let k1 = 1 1 = 1 k2 = 2 2 = 2 k3 = 4 3 = 4

    Set An = {ω Ω : ωkn = ωkn+1 = = ωkn+n1 = 1}. Show that An i.o. = 0.

  2. Let k1 = 1 1 = 1 k2 = 4 2 = 1 k3 = 16 3 = 1 k4 = 64 4 = 1

    Set An = {ω Ω : ωkn = = ωkn+n1 = 1}. Show that An i.o. = 1.

  3. Let x = x0 + i=0xi 10i be a decimal expansion of x; i.e., x0 and xi {0,, 9} for i 1. Define Ln(x) = i=1nx i10i. For instance,
    L1(π) = 10,L2(π) = 410,L3(π) = 1410,

    and

    L1(e) = 70,L2(e) = 170,L3(e) = 8170,

    Show that, given 𝜖n so that 𝜖n < , then for almost every x (with Lebesgue measure) there exists n(x) so that Ln(x) 𝜖n10n+1 for every n n(x).

__________________________________________________________________________

Books

Reading Suggestion:

References

[1]   Leo Breiman. Probability. Addison Wesley, 1968.

[2]   Emmanuel Lesigne. Heads or Tails: An Introduction to Limit Theorems in Probability, volume 28 of Student Mathematical Library. American Mathematical Society, 2005.

__________________________________________________________________________

Links

Outside Readings and Links:

__________________________________________________________________________

I check all the information on each page for correctness and typographical errors. Nevertheless, some errors may occur and I would be grateful if you would alert me to such errors. I make every reasonable effort to present current and accurate information for public use, however I do not guarantee the accuracy or timeliness of information on this website. Your use of the information from this website is strictly voluntary and at your risk.

I have checked the links to external sites for usefulness. Links to external websites are provided as a convenience. I do not endorse, control, monitor, or guarantee the information contained in any external website. I don’t guarantee that the links are active at all times. Use the links here with the same caution as you would all information on the Internet. This website reflects the thoughts, interests and opinions of its author. They do not explicitly represent official positions or policies of my employer.

Information on this website is subject to change without notice.

Steve Dunbar’s Home Page, http://www.math.unl.edu/~sdunbar1

Email to Steve Dunbar, sdunbar1 at unl dot edu

Last modified: Processed from LATEX source on October 10, 2017