Steven R. Dunbar
Department of Mathematics
203 Avery Hall
University of Nebraska-Lincoln
Lincoln, NE 68588-0130
Probability Theory and Stochastic Processes
Steven R. Dunbar
Borel-Cantelli Lemmas with Examples
Mathematicians Only: prolonged scenes of intense rigor.
How would you deﬁne events that happen inﬁnitely often in a sequence?
Deﬁnition. In probability space with -ﬁeld and probability measure , , let . Then the set
Recall that i.o. stands for “inﬁnitely often.”
The ﬁrst of the two Borel-Cantelli lemmas is sometimes called the easy half, or the direct half.
Proof. Let be given.
for suﬃciently large . Hence . □
The next Borel-Cantelli Lemma is sometimes called the hard half or the independent half. It is a partial converse to the ﬁrst Borel-Cantelli Lemma.
Proof. Using DeMorgan’s Law, note that
The proof needs to show that . Note that
Taking the logarithm and using gives
can be made arbitrarily small by choosing a large enough , so is a negligible event. □
Remark. The Borel-Cantelli Lemmas are examples of - Laws. Some other examples include the Kolmogorov - Law and the Hewitt-Savage - Law.
The ’s are independent and . Note that so . □
Set . Then .
Set . Then .
Example. Consider three independent sequences of fair coin ﬂips: , that is . The associated cumulative fortunes are . Then
Proof. Consider the probability of the event for all i.o. The proof for other values is similar. Note that
Example. Let be a decimal expansion of ; i.e., and for . Deﬁne . For instance,
This is a natural way to associate a sequence of real numbers to a real number through its decimal expansion. Given so that , then for almost every (with Lebesgue measure) there exists so that for every .
Proof. Recall that Markov’s Inequality says that
and is suﬃcient to prove the corollary. □
by the Local Limit Theorem. Recall that the Local Limit Theorem (for ) says
Then . □
Proof. Note that are not independent. Consider a subsequence . Select so that . Let . Then because each . If , then and ; i.e., implies that .
Remark. This is a standard trick in probability theory of considering stretches so far apart that the eﬀect of what happened previously to is small compared to the amount can change between and
Note that The proof needs to show that and can be selected so that . Now the claim is: Given any and any there exists an integer so that . In other words, most of our paths will be outside the band after the point .
For ﬁxed note that as Fix so that as . Take so large that . Let and and . Then
Now adding all inﬁnitely many of these ﬁxed ﬁnite values gives an inﬁnite value, so done by the Borel-Cantelli Lemma. □
The following proof is a slightly diﬀerent 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 ﬂips with and . Set so for the sequence of independent random variables.
This last line came from the fact that if then
where the ﬁrst equality is by independence. Note that or and both are less than . Then and and so for a suitable value of . By Corollary 11.11, and so almost surely, which means that almost surely. □
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, . Theorems 5 and 6 and following remarks are adapted from Probability by Leo Breiman, Addison-Wesley, Reading MA, 1968, Chapters 1 and 3. .
Set . Show that .
Set . Show that .
Show that, given so that , then for almost every (with Lebesgue measure) there exists so that for every .
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 eﬀort 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 reﬂects the thoughts, interests and opinions of its author. They do not explicitly represent oﬃcial 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 modiﬁed: Processed from LATEX source on October 10, 2017