Steven R. Dunbar
Department of Mathematics
203 Avery Hall
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

Mathematicians Only: prolonged scenes of intense rigor.

_______________________________________________________________________________________________

### Section Starter Question

Consider an inﬁnite sequence of coin ﬂips. What probability would you assign to the sequence that has a Head on its initial ﬂip and then any sequence of Heads and Tails on all the subsequent ﬂips? What probability would you assign to the sequence of ﬂips that is alternately Heads and Tails, continuing indeﬁnitely?

_______________________________________________________________________________________________

### Key Concepts

1. A subset $A\subseteq \Omega$ is of ﬁnite type if there exists an $n=n\left(A\right)\ge 1$ and a subset ${A}^{\prime }\subseteq {\Omega }_{n}$ so that $A=\left\{\omega \in \Omega \phantom{\rule{0.3em}{0ex}}:\phantom{\rule{0.3em}{0ex}}{\omega }^{\left(n\right)}\in {A}^{\prime }\right\}$, where ${\omega }^{\left(n\right)}=\left({\omega }_{1},\dots ,{\omega }_{n}\right)$.
2. $N\subseteq \Omega$ is a negligible event (that is, an event of probability measure $0$) if for every $𝜖>0$ there exists a countable set $\left\{{A}_{k}\phantom{\rule{0.3em}{0ex}}:\phantom{\rule{0.3em}{0ex}}k\ge 1\right\}$ of ﬁnite type events so that $N\subseteq {\cup }_{k\ge 1}{A}_{k}$ and ${\sum }_{k\ge 1}ℙ\left[{A}_{k}\right]<𝜖$.
3. Every countable union of negligible sets is negligible.
4. If $p\ne 0,1$, every countable subset of $\Omega$ is negligible.
5. The set of events ${\left\{{A}_{i}\right\}}_{i\in I}$ are independent if
$ℙ\left[\bigcap _{k=1}^{n}{A}_{{i}_{k}}\right]=\prod _{k=1}^{n}ℙ\left[{A}_{{i}_{k}}\right]$

for every ﬁnite set of distinct indexes ${i}_{1},\dots ,{i}_{n}\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 ﬁnite type event.
9. Let ${B}_{n}$ be a sequence of sets in $\Omega$.

(i.o. stands for “inﬁnitely often.”)

10. The Kolmogorov 0-1 Law says that if ${B}_{1},{B}_{2},\dots$ are independent, and if , then $ℙ\left[E\right]=0$ or $ℙ\left[E\right]=1$.

__________________________________________________________________________

### Vocabulary

1. A subset $A\subseteq \Omega$ is of ﬁnite type or is a ﬁnite type event if there exists an $n=n\left(A\right)\ge 1$ and a subset ${A}^{\prime }\subseteq {\Omega }_{n}$ so that $A=\left\{\omega \in \Omega \phantom{\rule{0.3em}{0ex}}:\phantom{\rule{0.3em}{0ex}}{\omega }^{\left(n\right)}\in {A}^{\prime }\right\}$, where ${\omega }^{\left(n\right)}=\left({\omega }_{1},\dots ,{\omega }_{n}\right)$.
2. $N\subseteq \Omega$ is a negligible event (that is, an event of probability measure $0$) if for every $𝜖>0$ there exists a countable set $\left\{{A}_{k}\phantom{\rule{0.3em}{0ex}}:\phantom{\rule{0.3em}{0ex}}k\ge 1\right\}$ of ﬁnite type events so that $N\subseteq {\cup }_{k\ge 1}{A}_{k}$ and ${\sum }_{k\ge 1}ℙ\left[{A}_{k}\right]<𝜖$.
3. An event $A\subseteq \Omega$ is an almost sure event if ${A}^{c}=\Omega \setminus A$ is negligible.
4. The set of events ${\left\{{A}_{i}\right\}}_{i\in I}$ are independent if
$ℙ\left[\bigcap _{k=1}^{n}{A}_{{i}_{k}}\right]=\prod _{k=1}^{n}ℙ\left[{A}_{{i}_{k}}\right]$

for every ﬁnite set of distinct indexes ${i}_{1},\dots ,{i}_{n}\in I$.

5. A set $E$ is called a tail event if $E$ is not a ﬁnite type event.

__________________________________________________________________________

### Mathematical Ideas

The Strong Law of Large Numbers says “it is certain” that ${S}_{n}∕n$ approaches the probability of success $p$ as the number of tosses $n$ approaches inﬁnity. To be rigorous, we need to make the statement “it is certain” precise. The problem is that there exist inﬁnite 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 deﬁning the concept of an almost sure event. The Strong Law of Large Numbers then tells us that the sequence ${S}_{n}∕n$ 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 $\Omega$ deﬁned by a condition depending on only ﬁnitely many coordinates. The realization or non-realization of such an event is determined after a ﬁxed and ﬁnite number of elementary trials.

Recall (Binomial Distribution.) that a composite experiment consists of repeating an elementary Bernoulli trial $n$ times. The sample space, denoted ${\Omega }_{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 ${\Omega }_{n}$ as $\omega =\left({\omega }_{1},\dots ,{\omega }_{n}\right)$, where each ${\omega }_{k}=0$ or $1$. That is, ${\Omega }_{n}={\left\{0,1\right\}}^{n}$. We assign a probability measure $ℙn\left[\cdot \right]$ on ${\Omega }_{n}$ by multiplying the probabilities of each Bernoulli trial in the composite experiment according to the principle of independence. Thus, for $k=1,\dots ,n$,

and inductively for each $\left({e}_{1},{e}_{2},\dots ,{e}_{n}\right)\in {\left\{1,0\right\}}^{n}$

Deﬁnition. Consider the space

Deﬁne ${S}_{n}:={\omega }_{1}+\cdots +{\omega }_{n}$. A subset $A\subseteq \Omega$ is of ﬁnite type or is a ﬁnite type event if there exists an $n=n\left(A\right)\ge 1$ and a subset ${A}^{\prime }\subseteq {\Omega }_{n}$ so that $A=\left\{\omega \in \Omega \phantom{\rule{0.3em}{0ex}}:\phantom{\rule{0.3em}{0ex}}{\omega }^{\left(n\right)}\in {A}^{\prime }\right\}$, where ${\omega }^{\left(n\right)}=\left({\omega }_{1},\dots ,{\omega }_{n}\right)$ is the projection of the inﬁnite sequence $\omega$ onto the ﬁnite head of length $n$.

If $A$ is of ﬁnite type, then we deﬁne the probability to be

$ℙ\left[A\right]=ℙn\left({A}^{\prime }\right)\left[{A}^{\prime }\right]=\sum _{{\omega }^{\left(n\right)}\in {A}^{\prime }}{p}^{{S}_{n}\left(\omega \right)}{q}^{\left(n-{S}_{n}\left(\omega \right)\right)}.$

This probability is well-deﬁned, see the Problems.

Deﬁnition. Note that $ℙ\left[\cdot \right]$ has the property of invariance under shifting, that is, if $A$ is an event, and $k$ is a positive integer, then the event $\left\{\omega \in \Omega \phantom{\rule{0.3em}{0ex}}:\phantom{\rule{0.3em}{0ex}}\left({\omega }_{k},{\omega }_{k+1},{\omega }_{k+2},\dots ,\right)\in A\right\}$ has the same probability as the event $A$.

Example. The set $A$ consisting of the sequences with a Head on its initial ﬂip and then any sequence of Heads and Tails on all the subsequent ﬂips is a ﬁnite type event. Taking a $1$ to represent a Head and a $0$ to represent a tail, the integer $n\left(A\right)=1$ and the subset ${A}^{\prime }=\left\{1\right\}$ so ${A}^{\prime }\subseteq {\Omega }_{1}=\left\{0,1\right\}$. Then $A=\left\{\omega \in \Omega \phantom{\rule{0.3em}{0ex}}:\phantom{\rule{0.3em}{0ex}}{\omega }^{\left(1\right)}\in {A}^{\prime }=\left\{1\right\}\right\}$

Deﬁnition. A set of subsets of some universal set is a ﬁeld if it is closed under ﬁnite unions, ﬁnite intersections, and complements.

Deﬁne $\mathsc{ℰ}$ to be the set of ﬁnite type events. Note that $\varnothing \in \mathsc{ℰ}$, $\Omega \in \mathsc{ℰ}$. The set $\mathsc{ℰ}$ is closed under taking complements and also closed under ﬁnite unions and ﬁnite intersections. Thus, we see that $\mathsc{ℰ}$ is a ﬁeld. This follows by direct veriﬁcation, see the Problems.

Note that $ℙ:\mathsc{ℰ}\to \left[0,1\right]$ and $ℙ\left[\Omega \right]=1$ and $ℙ\left[\varnothing \right]=0$ and $ℙ\left[A\cup B\right]=ℙ\left[A\right]+ℙ\left[B\right]$ if $A\cap B=\varnothing$.

Deﬁnition. A set of subsets of some universal set is a Borel ﬁeld if it is closed under complements, and countable intersections and unions. For any set $C$ of subsets of $\Omega$, denote by $\mathsc{ℱ}\left(C\right)$ the smallest Borel ﬁeld containing $C$.

#### Negligible and Almost Sure Events

Deﬁnition. We say that $N\subseteq \Omega$ is a negligible event, that is, an event of probability measure $0$, if for every $𝜖>0$ there exists a countable set $\left\{{A}_{k}\phantom{\rule{0.3em}{0ex}}:\phantom{\rule{0.3em}{0ex}}k\ge 1\right\}$ of ﬁnite type events so that $N\subseteq {\cup }_{k\ge 1}{A}_{k}$ and ${\sum }_{k\ge 1}ℙ\left[{A}_{k}\right]<𝜖$ and we write .

An event $A\subseteq \Omega$ is an almost sure event if ${A}^{c}=\Omega \setminus A$ is negligible.

Proposition 1.

1. Every subset of $\Omega$ that is contained in a negligible event is negligible.
2. Every countable union of negligible sets is negligible.
3. If $p\ne 0,1$, every countable subset of $\Omega$ is negligible.

Proof.

1. Suppose that $A$ is negligible and $B\subseteq A$. Then there exist ${A}_{k}\subseteq \Omega$, a set of ﬁnite type events, so that $A\subseteq {\cup }_{k\ge 1}{A}_{k}$. Then we see that $B\subseteq {\cup }_{k\ge 1}{A}_{k}$ and ${\sum }_{k\ge 1}ℙ\left[{A}_{k}\right]\le 𝜖$. Thus, $B$ is negligible.
2. Let ${\left\{{N}_{n}\right\}}_{n=1}^{\infty }$ be a countable set of negligible sets. Fix $𝜖>0$ and ﬁnd (by deﬁnition) a set of negligible events ${\left\{{A}_{n,k}\right\}}_{k=1}^{\infty }$ so that ${N}_{n}\subseteq {\cup }_{k\ge 1}{A}_{n,k}$ and $ℙ\left[{A}_{n,k}\right]\le \frac{𝜖}{{2}^{n}}$. Then
$N={\cup }_{n\ge 1}{N}_{n}\subseteq {\cup }_{\begin{array}{c}n\ge 1\\ k\ge 1\end{array}}{A}_{n,k}$

and ${\sum }_{\begin{array}{c}n\ge 1\\ k\ge 1\end{array}}ℙ\left[{A}_{n,k}\right]\le 𝜖$.

3. Suppose that $p\ne 0,1$. First prove that the singleton set $\left\{\omega \right\}$ is negligible. Note that $\left\{\omega \right\}\subseteq \left\{{\omega }^{\prime }\in \Omega \phantom{\rule{0.3em}{0ex}}:\phantom{\rule{0.3em}{0ex}}{\omega {}^{\prime }}^{\left(n\right)}={\omega }^{\left(n\right)}\right\}={A}_{n}$ and
$ℙ\left[{A}_{n}\right]\le max\left\{{p}^{n},{\left(1-p\right)}^{n}\right\}.$

For $n\gg 0$ so that ${p}^{n},{\left(1-p\right)}^{n}\le 𝜖$, then we see that $\left\{\omega \right\}\subseteq {A}_{n}$ and $ℙ\left[{A}_{n}\right]\le 𝜖$. Thus we see that $\left\{\omega \right\}$ is negligible and by part (2), we see that a countable union of singletons is negligible.

Deﬁnition. The set of events ${\left\{{A}_{i}\right\}}_{i\in I}$ are independent if

$ℙ\left[\bigcap _{k=1}^{n}{A}_{{i}_{k}}\right]=\prod _{k=1}^{n}ℙ\left[{A}_{{i}_{k}}\right]$

for every ﬁnite set of distinct indexes ${i}_{1},\dots ,{i}_{n}\in ℕ$.

Remark. The sets ${A}_{i}$ are independent if and only if the sets ${A}_{i}^{c}$ are independent. This follows because

$\begin{array}{llll}\hfill ℙ\left[{A}_{1}^{C}\cap {A}_{2}^{c}\right]& =ℙ\left[{\left({A}_{1}\cup {A}_{2}\right)}^{c}\right]\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & =1-ℙ\left[{A}_{1}\cup {A}_{2}\right]\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & =1-ℙ\left[{A}_{1}\right]-ℙ\left[{A}_{2}\right]+ℙ\left[{A}_{1}\cap {A}_{2}\right]\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & =1-ℙ\left[{A}_{1}\right]-ℙ\left[{A}_{2}\right]+ℙ\left[{A}_{1}\right]ℙ\left[{A}_{2}\right]\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & =\left(1-ℙ\left[{A}_{1}\right]\right)\left(1-ℙ\left[{A}_{2}\right]\right).\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\end{array}$

Proposition 2.   Let ${\left\{{A}_{i}\right\}}_{i\in I}$ be a family of events. If for each $i\in I$ there exists a ﬁnite subset ${E}_{i}\subseteq ℕ$ and a subset ${A}_{i}^{\prime }\subseteq {\left\{0,1\right\}}^{{E}_{i}}$ such that ${E}_{i}\cap {E}_{j}=\varnothing$ if $i\ne j$ and ${A}_{i}=\left\{\omega \in \Omega \phantom{\rule{0.3em}{0ex}}:\phantom{\rule{0.3em}{0ex}}{\left({\omega }_{n}\right)}_{n\in {E}_{i}}\in {A}_{i}^{\prime }\right\}$. Then the events ${\left\{{A}_{i}\right\}}_{i\in I}$ are independent.

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

Example. Let ${A}_{i}$ be the event that the $i$th coin ﬂip is heads. Let ${E}_{i}=\left\{i\right\}$ and ${A}_{i}^{\prime }$ be the set so that ${\omega }_{i}=1$. Certainly, ${E}_{i}\cap {E}_{j}=\varnothing$ for $i\ne j$. Also,

${A}_{i}=\left\{\omega \in \Omega \phantom{\rule{0.3em}{0ex}}:\phantom{\rule{0.3em}{0ex}}{\left({\omega }_{n}\right)}_{n\in {E}_{i}}\in {A}_{i}^{\prime }\right\}=\left\{\omega \in \Omega \phantom{\rule{0.3em}{0ex}}:\phantom{\rule{0.3em}{0ex}}{\omega }_{i}=1\right\}.$

Note $ℙ\left[{A}_{i}\right]=p$ and $ℙ\left[{\cap }_{k=1}^{n}{A}_{k}\right]={p}^{n}$. Thus, we see that $ℙ\left[{\cap }_{k=1}^{n}{A}_{k}\right]={\prod }_{k=1}^{n}ℙ\left[{A}_{k}\right]$.

Proposition 3. Let $b$ be a word from the alphabet $\left\{0,1\right\}$; i.e., $b$ is a ﬁnite sequence of $0$’s and $1$’s. The set

is negligible.

Proof.

1. Let $b$ be a word of length $j>0$. For all $m\ge 0$, let ${A}_{m}$ be the set of all $\omega \in \Omega$ so that $\left({\omega }_{mj+1},\dots ,{\omega }_{\left(m+1\right)j}\right)\ne b$. In other words, we are dividing $\omega$ into consecutive non-overlapping blocks of length $j$.
2. Note that $ℙ\left[{A}_{0}\right]<1$ and the property of invariance under shifting tells us that $ℙ\left[{A}_{m}\right]<1$.
3. The ${A}_{i}$ are independent by Proposition 3 and so
$ℙ\left[\bigcap _{k\le m}{A}_{k}\right]={\left(ℙ\left[{A}_{0}\right]\right)}^{m+1}.$

4. This value can be made arbitrarily small by choosing a large enough $m$.
5. Let ${B}_{n}=\left\{\omega \in \Omega \phantom{\rule{0.3em}{0ex}}:\phantom{\rule{0.3em}{0ex}}\left({\omega }_{n+1},\dots ,{\omega }_{n+j}\right)\ne b\right\}\subseteq {\cap }_{k\le m}{A}_{k}$.
6. Thus, we see that the probability of ${B}_{n}$ can be made arbitrarily small.
7. Note that $A\subseteq \cup {B}_{n}$ and so $A$ is negligible.

Corollary 1. All possible words almost surely appear in the sequence $\omega$.

Proof. (of Corollary 1)

The set of all possible words is countable, so let ${b}_{i}$ be an enumeration of the set of possible words. By Proposition 3 the set

is negligible. Then consider $A={\cup }_{{b}_{i}}{A}_{{b}_{i}}$. By Proposition 1, the set $A$ is negligible. Finally consider $\omega \in {A}^{C}=\Omega \setminus A$ and an arbitrary word $b$. The word $b$ must appear in ${A}^{C}$, and ${A}^{C}$ 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 ${P}_{i,j}$ be the set of all $\omega$ that begin periodicity at index $i$ and the period has length $j$.
2. First, show that the set ${P}_{1,j}$ of purely periodic sequences is negligible. Let ${b}_{j}={\stackrel{\to }{0}}_{j}$ be the word of length $j$ with all zeros. There is only sequence ${\omega }_{{b}_{j}}$ in ${P}_{1,j}$ which starts with the word $b$ and so we see that

Note that the ﬁrst set is negligible since it is a singleton and the second set is a subset of a negligible set by Proposition 3. So ${P}_{1,j}$ is negligible.

3. Next, for $i\ge 2$ the set ${P}_{i,j}$ is negligible. For $n=0,\dots ,{2}^{i-1}-1$ let ${b}_{n}$ be the binary representation with length $i-1$ of the number $n$.
4. For $n=0,\dots ,{2}^{i-1}-1$ let ${P}_{{b}_{n},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, $ℙ\left[{P}_{{b}_{n},j}\right]=ℙ\left[{P}_{1,j}\right]$ and so ${P}_{{b}_{i},j}$ is negligible. Finally,
${P}_{i,j}=\bigcup _{n=0}^{{2}^{i-1}-1}{P}_{{b}_{n},j}$

and so ${P}_{i,j}$ is negligible.

#### Tail Events

Deﬁnition. A set $E$ is called a tail event if $E$ is not a ﬁnite type event. That is, whether or not $\omega \in E$ does not depend on the ﬁrst $n$ coordinates of $\omega$ 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 $\frac{{S}_{n}}{n}$ does not converge to $p$. This set cannot depend on the ﬁrst $n$ coordinates of $\omega$ no matter how large $n$ is, hence it is a tail event.

Remark. $E\subseteq \mathsc{ℱ}\left(\Omega \right)$ is a tail event if $E\in \mathsc{ℱ}\left({X}_{n},{X}_{n+1},\dots \phantom{\rule{0.3em}{0ex}}\right)$ for all $n$. Here $\mathsc{ℱ}\left(\Omega \right)$ is the Borel ﬁeld of $\Omega$ and $\mathsc{ℱ}\left({X}_{n},{X}_{n+1},\dots \phantom{\rule{0.3em}{0ex}}\right)$ is the smallest Borel ﬁeld containing all possible sequences beginning at the $n$th index.

Remark. This deﬁnition may seem quite abstract, but it captures in a formal way the sense in which certain events do not depend on any ﬁnite number of their coordinates. For example, consider the set $E$ of coin-tossing sequences such that $\frac{{S}_{n}}{n}$ does not converge to $p$. That is,

$E=\left\{\omega \phantom{\rule{0.3em}{0ex}}:\phantom{\rule{0.3em}{0ex}}\frac{{X}_{1}+\cdots +{X}_{n}}{n}\to ̸p\right\}.$

Then for any $k\ge 1$,

$E=\left\{\omega \phantom{\rule{0.3em}{0ex}}:\phantom{\rule{0.3em}{0ex}}\frac{{X}_{k}+\cdots +{X}_{n}}{n}\to ̸p\right\}.$

so that $E\in \mathsc{ℱ}\left({X}_{n},{X}_{n+1},\dots \phantom{\rule{0.3em}{0ex}}\right)$ for all $k\ge 1$, $E$ is a tail event.

Deﬁnition. Let ${B}_{n}$ be a sequence of sets in $\Omega$.

(i.o. stands for “inﬁnitely often.”)

So if and only if $\omega \in {B}_{n}$ for inﬁnitely many $n$.

Proposition 4. Given ${\left\{{a}_{n}\right\}}_{n=1}^{\infty }$ with $\underset{n\to \infty }{lim}{a}_{n}=+\infty$, then

$\underset{n\to \infty }{limsup}{a}_{n}\sqrt{n}\left|\frac{{S}_{n}}{n}-p\right|=+\infty$

almost surely.

Remark. If ${a}_{n}\equiv a$, then

$\begin{array}{llll}\hfill \underset{n\to \infty }{lim}ℙn\left[a\sqrt{n}\left|\frac{{S}_{n}}{n}-p\right|

by the Central Limit Theorem and this is a ﬁnite value.

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

1. $\left({a}_{n}\right)$ is a sequence of real numbers,
2. ${a}_{n}\to \infty$ as $n\to \infty$ and
3. $\underset{n\to \infty }{lim}\frac{{a}_{n}}{{n}^{1∕6}}=0$.

then

$\begin{array}{llll}\hfill ℙn\left[\frac{{S}_{n}}{n}-p\ge \sqrt{p\left(1-p\right)}\frac{{a}_{n}}{\sqrt{n}}\right]& =ℙn\left[\frac{\sqrt{n}}{{a}_{n}}\left(\frac{{S}_{n}}{n}-p\right)\ge \sqrt{p\left(1-p\right)}\right]\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & \sim \frac{1}{{a}_{n}\sqrt{2\mathrm{\pi }}}{\mathrm{e}}^{-{a}_{n}^{2}∕2}.\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & \phantom{\rule{2em}{0ex}}& \hfill \end{array}$

This pair of previous results, together with the Proposition show how ﬁnely balanced around $p$ is the sequence $\sqrt{n}\left(\frac{{S}_{n}}{n}-p\right)$.

Proof.

1. Set ${A}_{m}=\left\{\omega \phantom{\rule{0.3em}{0ex}}:\phantom{\rule{0.3em}{0ex}}{limsup}_{n\to \infty }{a}_{n}\sqrt{n}\left|\frac{{S}_{n}}{n}-p\right| for all $m>0$. For any $\omega \in {A}_{m}$ is an $N$ (possibly depending on $\omega$ ) such that for every $n>N$ we have ${a}_{n}\sqrt{n}\left|\frac{{S}_{n}}{n}-p\right|.
2. Let ${A}_{k,m}=\left\{\omega \phantom{\rule{0.3em}{0ex}}:\phantom{\rule{0.3em}{0ex}}{a}_{k}\sqrt{k}\left|\frac{{S}_{k}\left(\omega \right)}{k}-p\right|. For $\omega \in {A}_{m}$ there exists $k$ so that $\omega \in {A}_{k,m}$.
3. Note that ${A}_{m}\subseteq {\cup }_{k}{A}_{k,m}$.
4. $ℙ\left[{A}_{k,m}\right]\approx {\int }_{-\frac{m}{{a}_{k}p\sqrt{1-p}}}^{\frac{m}{{a}_{k}p\sqrt{1-p}}}\frac{{e}^{-{x}^{2}∕2}}{\sqrt{2\pi }}\phantom{\rule{0.3em}{0ex}}dx$

5. Given $\frac{𝜖}{{2}^{j}}$, because ${a}_{k}\to \infty$ there exists ${k}_{j}$ so that $ℙ\left[{A}_{k,m}\right]<\frac{𝜖}{{2}^{j}}$ and we can choose the ${k}_{j}$ as an increasing sequence. Thus,
$\sum _{k=1}^{\infty }ℙ\left[{A}_{{k}_{j},m}\right]<𝜖$

and ${A}_{m}\subseteq {\cup }_{j=1}^{\infty }{A}_{{k}_{j},m}$. Thus, ${A}_{m}$ is negligible. This is true for any value $m$ and so

#### 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

#### Algorithm

AlmostSureEvents-Simulation

 Comment Post: Observation that any coin ﬂip 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 ﬂip coin-ﬂip

 sequence where scaled deviations from $p$ exceed

 the counting sequence.

 1 Set probability of success $p$

 2 Set length of coin-ﬂip sequence $n$

 3 Initialize and ﬁll length $n$ array of coin ﬂips

 4 Use vectorization to sum to get the cumulative sequence ${S}_{n}$ of heads

 5 Use vectorization to compute the scaling factor array ${a}_{n}$

 6 Use vectorization to compute the array of scaled deviations ${a}_{n}\sqrt{n}\left|{S}_{n}∕n-p\right|$

 7 Initialize the subsequence index $k$ to $1$

 8 while any scaled deviations exceed $k$

 9 Set ${N}_{k}$ as the ﬁrst index where the scaled deviations exceed $k$

 10 Print $k$, ${S}_{{N}_{k}}$ and scaled deviation ${a}_{{N}_{k}}\sqrt{{N}_{k}}\left|{S}_{{N}_{k}}∕{N}_{k}-p\right|$.

#### Scripts

R
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
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
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
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 for Understanding

1. Show that the deﬁnition that if $A$ is of ﬁnite type, then we deﬁne the probability to be
$ℙ\left[A\right]=ℙn\left({A}^{\prime }\right)\left[{A}^{\prime }\right]=\sum _{{\omega }^{\left(n\right)}\in {A}^{\prime }}{p}^{{S}_{n}\left(\omega \right)}{q}^{\left(n-{S}_{n}\left(\omega \right)\right)}$

is well-deﬁned. That is, if ${A}^{\prime }\subseteq {\Omega }_{n\left({A}^{\prime }\right)}$ and ${A}^{″}\subseteq {\Omega }_{n\left({A}^{″}\right)}$ are two events such that $A=\left\{\omega \in \Omega \phantom{\rule{0.3em}{0ex}}:\phantom{\rule{0.3em}{0ex}}{\omega }^{\left(n\right)}\in {A}^{\prime }\right\}$ and $A=\left\{\omega \in \Omega \phantom{\rule{0.3em}{0ex}}:\phantom{\rule{0.3em}{0ex}}{\omega }^{\left(n\right)}\in {A}^{″}\right\}$, then

$ℙ\left[A\right]=ℙn\left({A}^{\prime }\right)\left[{A}^{\prime }\right]=ℙn\left({A}^{″}\right)\left[{A}^{″}\right].$

2. Show that:
1. $\varnothing \in \mathsc{ℰ}$.
2. $\Omega \in \mathsc{ℰ}$.
3. The set $\mathsc{ℰ}$ is closed under taking complements.
4. The set $\mathsc{ℰ}$ is closed under ﬁnite unions and ﬁnite intersections.
3. Show that $ℙ\left[\cdot \right]$ has the property of invariance under shifting.
4. Show that $ℙ\left[\cdot \right]$ is monotone, that is, if $A\subseteq B$ then $ℙ\left[A\right]\le ℙ\left[B\right]$.
5. Is a singleton set $\left\{\omega \right\}$ is a tail event?
6. Is the set of tail events is countable?

__________________________________________________________________________

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

__________________________________________________________________________

__________________________________________________________________________

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.