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
Strong Law of Large Numbers
Mathematicians Only: prolonged scenes of intense rigor.
Explain what is meant by the “law of averages” and how it applies to an inﬁnite sequence of coin ﬂips.
This section presents three diﬀerent proofs of Borel’s Strong Law of Large Numbers. The ﬁrst uses the set theory of negligible sets and the Large Deviations estimate to show that the pointwise convergence fails on a negligible set. The second proof uses a carefully chosen subsequence and elementary estimates. The third proof uses the Borel-Cantelli Lemma and a fourth-moment condition.
Proof. Let . The sequence fails to approach if and only if . That is, fails to approach if and only if there is an depending on such for that for each there exists a satisfying . Therefore, the set of points in the sample space not satisfying is contained in
The goal is to show that this set is a negligible event. Since a countable union of negligible sets is negligible, it suﬃces to show that
is negligible for each .
For each , let . By the Large Deviations Estimate, there is a constant such that . Since the series converges, for every there is an such that . Because ,
This proves that each is a negligible set. □
Here is another proof of Borel’s Strong Law of Large Numbers, adapted from Theorem 1.21, in [1, page 11].
Before the proof, ﬁrst give a quick deﬁnition.
Deﬁnition. Suppose . Then . Also, if , then .
Proof. Break the proof into a sequence of simple steps.
To see this, ﬁrst note that the implication from the limit of the full sequence to the subsequential limit along the squares is immediate. For the other direction, for any , ﬁnd so that , or . Then
The term at the second line comes from estimating . Since , the largest the diﬀerence could be would be having each for , thus the diﬀerence could be at most . Then the claim that implies follows by the triangle inequality.
Note that each of these sets depends only on the coordinates , so is of ﬁnite type.
Note that is the set of ’s for which at least once for .
if and only if for any there exists so that . That is,
for all . Notice that and so consider . Again the claim is that
Let and then note that .
Remark. At steps6,7 and9 a limit is pulled through the probability measure. This is valid if given a sequence of ﬁnite probability measures deﬁned on a ﬁeld of ﬁnite type events , there exists a well-deﬁned probability measure deﬁned on ,the smallest -ﬁeld containing agreeing with on . That is true from the following theorem, with proof deferred to another section.
Deﬁnition. Let be a sequence of random variables and a sequence of Borel sets in . The event “ is in inﬁnitely often” denoted is deﬁned as
Remark. Note that the complementary event to the event in the Borel-Cantelli Lemma is
This is exactly the event , that is, the event that inﬁnitely many of the events occur. Thus the direct half of the Borel-Cantelli Lemma can be expressed as
The converse half of the Borel-Cantelli Lemma can be expressed as
But obviously, implies .
The complement of the set is . Then the goal is to show this is a negligible set. It is enough to show that each set is negligible. Temporarily ﬁx and for each , let be the event , so that .
Because the events are independent
This can be made arbitrarily small by choosing suﬃciently large , so by deﬁnition, is negligible.
with probability .
Proof. We can assume without loss of generality that , otherwise just consider . Expansion of , then using the independence and identical distribution assumptions shows
Then adapting the proof of the Markov and Chebyshev inequalities with fourth moments,
Then from the comparison theorem for series convergence
and the direct half of the Borel-Cantelli Lemma applies to show that
with probability . □
Example. Bernstein’s example of pairwise independence that are not all independent.
Consider ﬂipping a quarter and a dime. Let if the quarter is heads, if the dime is heads, and if the quarter is the same as the dime. First, for . Next note the following probabilities:
for all . In other words, almost surely.
Proof. Let and note that pairwise independence says
Note that we have
The Chebyshev inequality gives us that
and so . Since , by Corollary1 almost surely, and hence almost surely. Now let ; i.e., . Then almost surely. This gives
Using Corollary1 again□
The following proposition says that the asymptotic proportion of any outcome in an inﬁnite sequence of trials is “almost surely” the probability of that outcome for a single trial. This is sometimes referred as the “Law of Averages”.
Proposition 8 (The Law of Averages). Let be a sequence of equiprobable independent random events with probability . The asymptotic empirical probability that these event will occur is almost surely ; that is,
Proof. For each create a sequence of ’s and ’s by setting if and otherwise. The proof is to show
For each and each let , then
Now the same proof used to show that almost surely converges to can be applied to complete the proof that the convergence of (1) is almost sure. □
Proof. Since the event is of ﬁnite type, depends only on the coordinates with index less than or equal to for some positive integer . Equivalently, there exists an such that
For each integer from to consider the sequence of events deﬁned by
For ﬁxed and varying , the events are independent and each has probability . Let be the number of integers between and such that . The Proposition implies that
almost surely. Also,
The corollary then follows from the inequality
which holds for every from to . □
Deﬁnition. If is a word constructed from the alphabet and we say that is the probability of the word .
Proof. This is a special case of Proposition 2 □
This proof of the Strong Law for sum of Bernoulli random variables is adapted from: Heads or Tails, by Emmanuel Lesigne, Student Mathematical Library Volume 28, American Mathematical Society, Providence, 2005, Chapter 11.2, pages 82-85. . The proof based on subsequential limits and the Borel Cantelli Lemma and following remarks is adapted from Probability by Leo Breiman, Addison-Wesley, Reading MA, 1968, Chapters 1 and 3.  The proof using the fourth-moment and the Borel-Cantelli Lemma is adapted from Varadhan, .
́Comment Post: Observation that any coin ﬂip sequence
selected by a pseudo-random-number-generator
has the average number of heads converge to the probability of heads,
suggesting the Strong Law of Large Numbers.
́Comment Post: The average number of heads sampled at an exponential sequence of indices, to suggest the Strong Law of Large Numbers.
1́Set probability of success .
2́Set length of coin-ﬂip sequence .
3́Initialize and ﬁll length array of coin ﬂips.
4́Use vectorization to sum the cumulative sequence of heads.
5́Use vectorization to compute an exponential sequence of indices for sampling.
6́Use vectorization to compute the average number of heads along the exponential sequence of indices.
7́Print the averages.
R script for Strong Law..
Octave script for Strong Law..
Perl PDL script for Strong Law..
Scientiﬁc Python script for Strong Law..
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 20, 2017