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

__________________________________________________________________________

Almost Sure Events

_______________________________________________________________________

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

Consider an infinite sequence of coin flips. What probability would you assign to the sequence that has a Head on its initial flip and then any sequence of Heads and Tails on all the subsequent flips? What probability would you assign to the sequence of flips that is alternately Heads and Tails, continuing indefinitely?

_______________________________________________________________________________________________

Key Concepts

Key Concepts

  1. A subset A Ω is of finite type if there exists an n = n(A) 1 and a subset A Ω n so that A = ω Ω : ω(n) A, where ω(n) = (ω 1,,ωn).
  2. N Ω is a negligible event (that is, an event of probability measure 0) if for every 𝜖 > 0 there exists a countable set Ak : k 1 of finite type events so that N k1Ak and k1 Ak < 𝜖.
  3. Every countable union of negligible sets is negligible.
  4. If p0, 1, every countable subset of Ω is negligible.
  5. The set of events Ai iI are independent if
    k=1nA ik = k=1n A ik

    for every finite set of distinct indexes i1,,in I.

  6. Events determined by coordinates with disjoint sets of indexes are independent.
  7. The set of sequences that are periodic after a certain index is negligible.
  8. A set E is called a tail event if E is not a finite type event.
  9. Let Bn be a sequence of sets in Ω.
    Bn i.o.  = lim mn=mB n.

    (i.o. stands for “infinitely often.”)

  10. The Kolmogorov 0-1 Law says that if B1,B2, are independent, and if E = Bn i.o. , then E = 0 or E = 1.

__________________________________________________________________________

Vocabulary

Vocabulary

  1. A subset A Ω is of finite type or is a finite type event if there exists an n = n(A) 1 and a subset A Ω n so that A = ω Ω : ω(n) A, where ω(n) = (ω 1,,ωn).
  2. N Ω is a negligible event (that is, an event of probability measure 0) if for every 𝜖 > 0 there exists a countable set Ak : k 1 of finite type events so that N k1Ak and k1 Ak < 𝜖.
  3. An event A Ω is an almost sure event if Ac = Ω A is negligible.
  4. The set of events Ai iI are independent if
    k=1nA ik = k=1n A ik

    for every finite set of distinct indexes i1,,in I.

  5. A set E is called a tail event if E is not a finite type event.

__________________________________________________________________________

Mathematical Ideas

Mathematical Ideas

The Strong Law of Large Numbers says “it is certain” that Snn approaches the probability of success p as the number of tosses n approaches infinity. To be rigorous, we need to make the statement “it is certain” precise. The problem is that there exist infinite sequences of heads and tails such that the proportion of heads does not converge to p, such as the sequence consisting of all tails. In fact, there exist sequences of heads and tails where the proportion of heads does not converge at all. However, we can exclude such events by defining the concept of an almost sure event. The Strong Law of Large Numbers then tells us that the sequence Snn converges almost surely to p. This fundamental idea is due to E. Borel in 1909, [1].

Finite Type Events

First we consider the subset of elements in Ω defined by a condition depending on only finitely many coordinates. The realization or non-realization of such an event is determined after a fixed and finite number of elementary trials.

Recall (Binomial Distribution.) that a composite experiment consists of repeating an elementary Bernoulli trial n times. The sample space, denoted Ωn, is the set of all possible sequences of n 0’s and 1’s representing all possible outcomes of the composite experiment. We denote an element of Ωn as ω = (ω1,,ωn), where each ωk = 0 or 1. That is, Ωn = 0, 1 n. We assign a probability measure n on Ωn by multiplying the probabilities of each Bernoulli trial in the composite experiment according to the principle of independence. Thus, for k = 1,,n,

1 ωk = 0 = q and 1 ωk = 1 = p

and inductively for each (e1,e2,,en) 1, 0 n

n+1 ωn+1 = 1 and (ω1,,ωk) = (e1,,en) = 1 ωn+1 = 1 × n (ω1,,ωn) = (e1,,en)

Definition. Consider the space

Ω = ω = (ωn)n=1 : ω n = 0, 1 for all n.

Define Sn := ω1 + + ωn. A subset A Ω is of finite type or is a finite type event if there exists an n = n(A) 1 and a subset A Ω n so that A = ω Ω : ω(n) A, where ω(n) = (ω 1,,ωn) is the projection of the infinite sequence ω onto the finite head of length n.

If A is of finite type, then we define the probability to be

A = n(A) A = ω(n)ApSn(ω)qnSn(ω).

This probability is well-defined, see the Problems.

Definition. Note that has the property of invariance under shifting, that is, if A is an event, and k is a positive integer, then the event ω Ω : (ωk,ωk+1,ωk+2,, ) A has the same probability as the event A.

Example. The set A consisting of the sequences with a Head on its initial flip and then any sequence of Heads and Tails on all the subsequent flips is a finite type event. Taking a 1 to represent a Head and a 0 to represent a tail, the integer n(A) = 1 and the subset A = 1 so A Ω 1 = 0, 1. Then A = ω Ω : ω(1) A = 1

Definition. A set of subsets of some universal set is a field if it is closed under finite unions, finite intersections, and complements.

Define to be the set of finite type events. Note that , Ω . The set is closed under taking complements and also closed under finite unions and finite intersections. Thus, we see that is a field. This follows by direct verification, see the Problems.

Note that : [0, 1] and Ω = 1 and = 0 and A B = A + B if A B = .

Definition. A set of subsets of some universal set is a Borel field if it is closed under complements, and countable intersections and unions. For any set C of subsets of Ω, denote by (C) the smallest Borel field containing C.

Negligible and Almost Sure Events

Definition. We say that N Ω is a negligible event, that is, an event of probability measure 0, if for every 𝜖 > 0 there exists a countable set Ak : k 1 of finite type events so that N k1Ak and k1 Ak < 𝜖 and we write [ A] a.s. .

An event A Ω is an almost sure event if Ac = Ω A is negligible.

Proposition 1.

  1. Every subset of Ω that is contained in a negligible event is negligible.
  2. Every countable union of negligible sets is negligible.
  3. If p0, 1, every countable subset of Ω is negligible.

Proof.

  1. Suppose that A is negligible and B A. Then there exist Ak Ω, a set of finite type events, so that A k1Ak. Then we see that B k1Ak and k1 Ak 𝜖. Thus, B is negligible.
  2. Let Nn n=1 be a countable set of negligible sets. Fix 𝜖 > 0 and find (by definition) a set of negligible events An,k k=1 so that Nn k1An,k and An,k 𝜖 2n. Then
    N = n1Nn n1 k1 An,k

    and n1 k1 An,k 𝜖.

  3. Suppose that p0, 1. First prove that the singleton set ω is negligible. Note that ω ω Ω : ω(n) = ω(n) = A n and
    An max pn, (1 p)n .

    For n 0 so that pn, (1 p)n 𝜖, then we see that ω An and An 𝜖. Thus we see that ω is negligible and by part (2), we see that a countable union of singletons is negligible.

Definition. The set of events Ai iI are independent if

k=1nA ik = k=1n A ik

for every finite set of distinct indexes i1,,in .

Remark. The sets Ai are independent if and only if the sets Aic are independent. This follows because

A1C A 2c = (A 1 A2)c = 1 A1 A2 = 1 A1 A2 + A1 A2 = 1 A1 A2 + A1 A2 = (1 A1)(1 A2).

Proposition 2.   Let Ai iI be a family of events. If for each i I there exists a finite subset Ei and a subset Ai 0, 1 Ei such that Ei Ej = if ij and Ai = ω Ω : (ωn)nEi Ai. Then the events Ai iI are independent.

Remark. This proposition means that events that are determined by coordinates with disjoint sets of indexes are independent.

Example. Let Ai be the event that the ith coin flip is heads. Let Ei = i and Ai be the set so that ωi = 1. Certainly, Ei Ej = for ij. Also,

Ai = ω Ω : (ωn)nEi Ai = ω Ω : ω i = 1.

Note Ai = p and k=1nA k = pn. Thus, we see that k=1nA k = k=1n A k.

Proposition 3. Let b be a word from the alphabet 0, 1; i.e., b is a finite sequence of 0’s and 1’s. The set

A = ω Ω : b is not found in ω

is negligible.

Proof.

  1. Let b be a word of length j > 0. For all m 0, let Am be the set of all ω Ω so that (ωmj+1,,ω(m+1)j)b. In other words, we are dividing ω into consecutive non-overlapping blocks of length j.
  2. Note that A0 < 1 and the property of invariance under shifting tells us that Am < 1.
  3. The Ai are independent by Proposition 3 and so
    kmAk = A0 m+1.

  4. This value can be made arbitrarily small by choosing a large enough m.
  5. Let Bn = ω Ω : (ωn+1,,ωn+j)b kmAk.
  6. Thus, we see that the probability of Bn can be made arbitrarily small.
  7. Note that A Bn and so A is negligible.

Corollary 1. All possible words almost surely appear in the sequence ω.

Proof. (of Corollary 1)

The set of all possible words is countable, so let bi be an enumeration of the set of possible words. By Proposition 3 the set

Abi = ω Ω : bi is not found in ω

is negligible. Then consider A = biAbi. By Proposition 1, the set A is negligible. Finally consider ω AC = Ω A and an arbitrary word b. The word b must appear in AC, and AC is an almost sure event. □

Corollary 2. The set of sequences that are periodic after a certain index is negligible.

Proof. (of Corollary 2)

  1. Let Pi,j be the set of all ω that begin periodicity at index i and the period has length j.
  2. First, show that the set P1,j of purely periodic sequences is negligible. Let bj = 0j be the word of length j with all zeros. There is only sequence ωbj in P1,j which starts with the word b and so we see that
    Pi,j = ωbj ω : not containing bj .

    Note that the first set is negligible since it is a singleton and the second set is a subset of a negligible set by Proposition 3. So P1,j is negligible.

  3. Next, for i 2 the set Pi,j is negligible. For n = 0,, 2i1 1 let bn be the binary representation with length i 1 of the number n.
  4. For n = 0,, 2i1 1 let Pbn,j be the set of sequences which start with b and are periodic with period j starting at index i. By the property of invariance under shifting, Pbn,j = P1,j and so Pbi,j is negligible. Finally,
    Pi,j = n=02i11P bn,j

    and so Pi,j is negligible.

Tail Events

Definition. A set E is called a tail event if E is not a finite type event. That is, whether or not ω E does not depend on the first n coordinates of ω no matter how large n is. Some authors refer to a tail event as a remote event.

Example. Consider the set E of coin-tossing sequences such that Sn n does not converge to p. This set cannot depend on the first n coordinates of ω no matter how large n is, hence it is a tail event.

Remark. E (Ω) is a tail event if E (Xn,Xn+1,) for all n. Here (Ω) is the Borel field of Ω and (Xn,Xn+1,) is the smallest Borel field containing all possible sequences beginning at the nth index.

Remark. This definition may seem quite abstract, but it captures in a formal way the sense in which certain events do not depend on any finite number of their coordinates. For example, consider the set E of coin-tossing sequences such that Sn n does not converge to p. That is,

E = ω : X1 + + Xn n ↛p.

Then for any k 1,

E = ω : Xk + + Xn n ↛p.

so that E (Xn,Xn+1,) for all k 1, E is a tail event.

Definition. Let Bn be a sequence of sets in Ω.

Bn i.o. = lim mn=mB n.

(i.o. stands for “infinitely often.”)

So ω Bn i.o. if and only if ω Bn for infinitely many n.

Proposition 4. Given an n=1 with lim nan = +, then

limsup nann Sn n p = +

almost surely.

Remark. If an a, then

lim nn an Sn n p < c = lim nn an Sn pn n < c = lim nn ap(1 p) Sn pn p(1 p)n < c = lim nn Sn pn p(1 p)n < c ap(1 p) = c ap(1p) c ap(1p) 1 2πex22dx

by the Central Limit Theorem and this is a finite value.

On the other hand, the Moderate Deviations Theorem says that if

  1. (an) is a sequence of real numbers,
  2. an as n and
  3. lim n an n16 = 0.

then

n Sn n p p(1 p) an n = n n an Sn n p p(1 p) 1 an2πean22.

This pair of previous results, together with the Proposition show how finely balanced around p is the sequence n Sn n p.

Proof.

  1. Set Am = ω : limsup nann Sn n p < m for all m > 0. For any ω Am is an N (possibly depending on ω ) such that for every n > N we have ann Sn n p < m.
  2. Let Ak,m = ω : akk Sk(ω) k p < m. For ω Am there exists k so that ω Ak,m.
  3. Note that Am kAk,m.
  4. Ak,m m akp1p m akp1p ex22 2π dx

  5. Given 𝜖 2j, because ak there exists kj so that Ak,m < 𝜖 2j and we can choose the kj as an increasing sequence. Thus,
    k=1 A kj,m < 𝜖

    and Am j=1A kj,m. Thus, Am is negligible. This is true for any value m and so

    limsup nann Sn n p =  a.s.

Sources

This section is adapted from: Heads or Tails, by Emmanuel Lesigne, Student Mathematical Library Volume 28, American Mathematical Society, Providence, 2005, Chapter 11.1, pages 78-82. [3]. Some of the remarks and examples are also adapted from Probability by Leo Breiman, Addison-Wesley, Reading MA, 1968, Chapters 1 and 3. [2]

_______________________________________________________________________________________________

Algorithms, Scripts, Simulations

Algorithms, Scripts, Simulations

Algorithm

AlmostSureEvents-Simulation
 
Comment Post: Observation that any coin flip sequence

selected by a pseudo-random-number-generator

has scaled deviations which exceed a sequence of integers,

suggesting the almost sure result of 4

Comment Post: Indexes and values of a million flip coin-flip

sequence where scaled deviations from p exceed

the counting sequence.

1 Set probability of success p

2 Set length of coin-flip sequence n

3 Initialize and fill length n array of coin flips

4 Use vectorization to sum to get the cumulative sequence Sn of heads

5 Use vectorization to compute the scaling factor array an

6 Use vectorization to compute the array of scaled deviations ann Snn p

7 Initialize the subsequence index k to 1

8 while any scaled deviations exceed k

9 Set Nk as the first index where the scaled deviations exceed k

10 Print k, SNk and scaled deviation aNkNk SNkNk p.

Scripts

Scripts

R

R script for Almost Sure Events..

1p <- 0.5 
2n <- 1e+6 
3coinFlips <- (runif(n) <= p) 
4S <- cumsum(coinFlips) 
5 
6an <- (1:n)^(1/6) 
7deviations <- an*sqrt(1:n)*(abs( S/(1:n) - p )) 
8 
9k <- 1 
10while ( length(which(deviations > k)) > 0 ) { 
11  Nk <- min(which(deviations > k)) 
12  cat("Index:", Nk, "Sum:", S[Nk], "Scaled Deviation:", deviations[Nk], "\n") 
13  k <- k+1 
14}
0cAp0x1-1300015:
Octave

Octave script for Almost Sure Events..

1p = 0.5; 
2n = 1e+6; 
3coinFlips = rand(1,n) <= p; 
4S = cumsum(coinFlips); 
5 
6an = (1:n).^(1/6); 
7deviations = an.*sqrt(1:n).*(abs( S./(1:n) - p*ones(1,n))); 
8 
9k = 1; 
10while ( any(deviations > k) ) 
11    Nk = find( deviations > k)(1); 
12    printf("Index: %i, Sum: %i, Scaled deviation: %f \n", 
13     Nk, S(Nk), deviations(Nk)) 
14    k = k+1; 
15endwhile
0cAp1x1-1300016:
Perl

Perl PDL script for Almost Sure Events..

1$p         = 0.5; 
2$n         = 1e+6; 
3$coinFlips = random($n) <= $p; 
4$S         = cumusumover($coinFlips); 
5 
6$narray     = zeros($n)->xlinvals( 1, $n ); 
7$an         = $narray**( 1 / 6 ); 
8$deviations = $an * sqrt($narray) * ( abs( $S / ($narray) - $p ) ); 
9 
10$k = 1; 
11while ( any $deviations > $k ) { 
12    $Nk = ( ( which $deviations > $k )->range(0) ); 
13    print "Index:", $Nk, "Sum:", $S->range([$Nk]), "Scaled Deviation:", 
14        $deviations->range([$Nk]), "\n"; 
15    $k = $k + 1; 
16}
0cAp2x1-1300017:
SciPy

Scientific Python script for Almost Sure Events..

1import scipy 
2 
3p = 0.5 
4n = 1e+6 
5coinFlips = scipy.random.random(n) <= p 
6 
7# Note Booleans True for Heads and False for Tails 
8 
9S = scipy.cumsum(coinFlips, axis=0) 
10 
11# Note how Booleans act as 0 (False) and 1 (True) 
12 
13narray = scipy.arange(1, n + 1, dtype=float) 
14an = narray ** (1. / 6.) 
15deviations = an * scipy.sqrt(narray) * scipy.absolute(S / narray - p) 
16 
17k = 1 
18while scipy.any(deviations > k): 
19    Nk = scipy.nonzero(deviations > k)[0][0] 
20    print Index:, Nk, Sum:, S[Nk], Scaled Deviation:, \ 
21        deviations[Nk] 
22    k = k + 1
0cAp3x1-1300023:

__________________________________________________________________________

Problems to Work

Problems to Work for Understanding

  1. Show that the definition that if A is of finite type, then we define the probability to be
    A = n(A) A = ω(n)ApSn(ω)qnSn(ω)

    is well-defined. That is, if A Ω n(A) and A Ωn(A) are two events such that A = ω Ω : ω(n) A and A = ω Ω : ω(n) A, then

    A = n(A) A = n(A) A.

  2. Show that:
    1. .
    2. Ω .
    3. The set is closed under taking complements.
    4. The set is closed under finite unions and finite intersections.
  3. Show that has the property of invariance under shifting.
  4. Show that is monotone, that is, if A B then A B.
  5. Is a singleton set {ω} is a tail event?
  6. Is the set of tail events is countable?

__________________________________________________________________________

Books

Reading Suggestion:

References

[1]   E. Borel. Sur les probabilités démombrables et leurs applications arithmétiques. Rediconti del Circolo Math. di Palermo, 26:247–271, 1909.

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

[3]   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 September 25, 2017