$\newcommand{\br}{\\}$ $\newcommand{\R}{\mathbb{R}}$ $\newcommand{\Q}{\mathbb{Q}}$ $\newcommand{\Z}{\mathbb{Z}}$ $\newcommand{\N}{\mathbb{N}}$ $\newcommand{\C}{\mathbb{C}}$ $\newcommand{\P}{\mathbb{P}}$ $\newcommand{\F}{\mathbb{F}}$ $\newcommand{\L}{\mathcal{L}}$ $\newcommand{\spa}[1]{\text{span}(#1)}$ $\newcommand{\dist}[1]{\text{dist}(#1)}$ $\newcommand{\max}[1]{\text{max}(#1)}$ $\newcommand{\min}[1]{\text{min}(#1)}$ $\newcommand{\supr}[0]{\text{sup}}$ $\newcommand{\infi}[0]{\text{inf}}$ $\newcommand{\ite}[1]{\text{int}(#1)}$ $\newcommand{\ext}[1]{\text{ext}(#1)}$ $\newcommand{\bdry}[1]{\partial #1}$ $\newcommand{\argmax}[1]{\underset{#1}{\text{argmax }}}$ $\newcommand{\argmin}[1]{\underset{#1}{\text{argmin }}}$ $\newcommand{\set}[1]{\left\{#1\right\}}$ $\newcommand{\emptyset}{\varnothing}$ $\newcommand{\tilde}{\text{~}}$ $\newcommand{\otherwise}{\text{ otherwise }}$ $\newcommand{\if}{\text{ if }}$ $\newcommand{\proj}{\text{proj}}$ $\newcommand{\union}{\cup}$ $\newcommand{\intercept}{\cap}$ $\newcommand{\abs}[1]{\left| #1 \right|}$ $\newcommand{\norm}[1]{\left\lVert#1\right\rVert}$ $\newcommand{\pare}[1]{\left(#1\right)}$ $\newcommand{\brac}[1]{\left[#1\right]}$ $\newcommand{\t}[1]{\text{ #1 }}$ $\newcommand{\head}{\text H}$ $\newcommand{\tail}{\text T}$ $\newcommand{\d}{\text d}$ $\newcommand{\limu}[2]{\underset{#1 \to #2}\lim}$ $\newcommand{\limd}[3]{\underset{#1 \to #2; #3}\lim}$ $\newcommand{\der}[2]{\frac{\d #1}{\d #2}}$ $\newcommand{\derw}[2]{\frac{\d #1^2}{\d^2 #2}}$ $\newcommand{\pder}[2]{\frac{\partial #1}{\partial #2}}$ $\newcommand{\pderw}[2]{\frac{\partial^2 #1}{\partial #2^2}}$ $\newcommand{\pderws}[3]{\frac{\partial^2 #1}{\partial #2 \partial #3}}$ $\newcommand{\inv}[1]{{#1}^{-1}}$ $\newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $\newcommand{\nullity}[1]{\text{nullity}(#1)}$ $\newcommand{\rank}[1]{\text{rank }#1}$ $\newcommand{\nullspace}[1]{\mathcal{N}\pare{#1}}$ $\newcommand{\range}[1]{\mathcal{R}\pare{#1}}$ $\newcommand{\var}[1]{\text{var}\pare{#1}}$ $\newcommand{\cov}[2]{\text{cov}(#1, #2)}$ $\newcommand{\tr}[1]{\text{tr}(#1)}$ $\newcommand{\oto}{\text{ one-to-one }}$ $\newcommand{\ot}{\text{ onto }}$ $\newcommand{\ipto}{\overset{\text{i.p.}}\longrightarrow}$ $\newcommand{\asto}{\overset{\text{a.s.}}\longrightarrow}$ $\newcommand{\expdist}[1]{\text{ ~ Exp}(#1)}$ $\newcommand{\unifdist}[1]{\text{ ~ Unif}(#1)}$ $\newcommand{\normdist}[2]{\text{ ~ N}(#1,#2)}$ $\newcommand{\poissondist}[1]{\text{ ~ Poisson}(#1)}$ $\newcommand{\ceil}[1]{\lceil#1\rceil}$ $\newcommand{\floor}[1]{\lfloor#1\rfloor}$ $\newcommand{\Re}[1]{\text{Re}(#1)}$ $\newcommand{\Im}[1]{\text{Im}(#1)}$ $\newcommand{\dom}[1]{\text{dom}(#1)}$ $\newcommand{\fnext}[1]{\overset{\sim}{#1}}$ $\newcommand{\transpose}[1]{{#1}^{\text{T}}}$ $\newcommand{\b}[1]{\boldsymbol{#1}}$ $\newcommand{\None}[1]{}$ $\newcommand{\Vcw}[2]{\begin{bmatrix} #1 \br #2 \end{bmatrix}}$ $\newcommand{\Vce}[3]{\begin{bmatrix} #1 \br #2 \br #3 \end{bmatrix}}$ $\newcommand{\Vcr}[4]{\begin{bmatrix} #1 \br #2 \br #3 \br #4 \end{bmatrix}}$ $\newcommand{\Vct}[5]{\begin{bmatrix} #1 \br #2 \br #3 \br #4 \br #5 \end{bmatrix}}$ $\newcommand{\Vcy}[6]{\begin{bmatrix} #1 \br #2 \br #3 \br #4 \br #5 \br #6 \end{bmatrix}}$ $\newcommand{\Vcu}[7]{\begin{bmatrix} #1 \br #2 \br #3 \br #4 \br #5 \br #6 \br #7 \end{bmatrix}}$ $\newcommand{\vcw}[2]{\begin{matrix} #1 \br #2 \end{matrix}}$ $\newcommand{\vce}[3]{\begin{matrix} #1 \br #2 \br #3 \end{matrix}}$ $\newcommand{\vcr}[4]{\begin{matrix} #1 \br #2 \br #3 \br #4 \end{matrix}}$ $\newcommand{\vct}[5]{\begin{matrix} #1 \br #2 \br #3 \br #4 \br #5 \end{matrix}}$ $\newcommand{\vcy}[6]{\begin{matrix} #1 \br #2 \br #3 \br #4 \br #5 \br #6 \end{matrix}}$ $\newcommand{\vcu}[7]{\begin{matrix} #1 \br #2 \br #3 \br #4 \br #5 \br #6 \br #7 \end{matrix}}$ $\newcommand{\Mqw}[2]{\begin{bmatrix} #1 & #2 \end{bmatrix}}$ $\newcommand{\Mqe}[3]{\begin{bmatrix} #1 & #2 & #3 \end{bmatrix}}$ $\newcommand{\Mqr}[4]{\begin{bmatrix} #1 & #2 & #3 & #4 \end{bmatrix}}$ $\newcommand{\Mqt}[5]{\begin{bmatrix} #1 & #2 & #3 & #4 & #5 \end{bmatrix}}$ $\newcommand{\Mwq}[2]{\begin{bmatrix} #1 \br #2 \end{bmatrix}}$ $\newcommand{\Meq}[3]{\begin{bmatrix} #1 \br #2 \br #3 \end{bmatrix}}$ $\newcommand{\Mrq}[4]{\begin{bmatrix} #1 \br #2 \br #3 \br #4 \end{bmatrix}}$ $\newcommand{\Mtq}[5]{\begin{bmatrix} #1 \br #2 \br #3 \br #4 \br #5 \end{bmatrix}}$ $\newcommand{\Mqw}[2]{\begin{bmatrix} #1 & #2 \end{bmatrix}}$ $\newcommand{\Mwq}[2]{\begin{bmatrix} #1 \br #2 \end{bmatrix}}$ $\newcommand{\Mww}[4]{\begin{bmatrix} #1 & #2 \br #3 & #4 \end{bmatrix}}$ $\newcommand{\Mqe}[3]{\begin{bmatrix} #1 & #2 & #3 \end{bmatrix}}$ $\newcommand{\Meq}[3]{\begin{bmatrix} #1 \br #2 \br #3 \end{bmatrix}}$ $\newcommand{\Mwe}[6]{\begin{bmatrix} #1 & #2 & #3\br #4 & #5 & #6 \end{bmatrix}}$ $\newcommand{\Mew}[6]{\begin{bmatrix} #1 & #2 \br #3 & #4 \br #5 & #6 \end{bmatrix}}$ $\newcommand{\Mee}[9]{\begin{bmatrix} #1 & #2 & #3 \br #4 & #5 & #6 \br #7 & #8 & #9 \end{bmatrix}}$
Definition: Almost Sure Convergence

To say that the sequence $Y_n$ (not necessarily independent) converges almost surely or almost everywhere or with probability 1 or strongly towards $X$ means that

$$P(\limu{ n }{ \infty } Y_n = c) = 1 $$

This means that the values $Y_n$ approach the value of $c$,

Definition: The Strong Law of Large Number

Let $X_1, X_2, … $ be a sequence of i.i.d. random variables with mean $\mu $. Then, the sequence of sample means $M_n = (X_1, _2, …, _n) / n$ converges to $\mu $ with probability $1 $.

Or we can simply say that

$$M_n \asto \mu $$

Example

Let $X_1, X_2, … $ be a sequence of i.i.d. random variables that are uniformly distributed in $[0, 1] $, and let $Y_n = \min{ X_1, X_2, …, X_n } $. We wish to show that $Y_n $ converges to $0 $ with probability $1$.

Observe that $Y_{n + 1} \leq Y_n$ for all $n $.

Since this sequence is bounded below by zero, it must have a limit, which we denote by $Y$.

Fix $\epsilon > 0 $. We have $Y \geq \epsilon$ if and only if $X_i \geq \epsilon$ for all $i $.

$$P(Y \geq \epsilon) = P(X_1 \geq \epsilon … X_n \geq \epsilon) = (1 - \epsilon)^n$$

Since this is true for all $n $. We must have

$$P(Y \geq \epsilon) \leq \limu{ n }{ \infty }(1 - \epsilon)^n = 0 $$

This shows that $P(Y \geq \epsilon) = 0 $, $\forall \epsilon > 0$.

We conclude that $P(Y > 0) = 0 $ which implies that $P(Y = 0) = 1 $. Since $Y $ is the limit of $Y_n$, we see that $Y_n \asto 1$.

Theorem : Almost Sure Convergence Implies Convergence in Probability

$$Y \asto c \implies Y \ipto c $$

Example: A discrete-time Arrival process

Consider a discrete-time arrival process.
The set of times is partitioned into consecutive intervals of the form $I_k = \set{ 2^k, 2^k +1, …, 2^{k+1} - 1 }$. Note that the length of $I_k $ is $2^k $, which increases with $k $. During each interval $I_k $, there is exactly one arrival, and all times within an interval are equally likely. The arrival times within different intervals are assumed to be independent. Let us define $Y_n = 1 $ if there is an arrival at time $n $, and $Y_n = 0 $ if there is no arrival.

We have $P(Y_n \neq 0) = \frac{ 1 }{ 2^k } $, if $n \in I_k $. Note that as $n $ increases, it belongs to intervals $I_k $ with increasingly large indices $k $. Consequently,

$$\limu{ n }{ \infty } P(Y_n \neq 0) = \limu{ k }{ \infty } \frac{ 1 }{ 2^k } = 0$$

i.e.

$$Y_n \ipto 0$$

However, when we carry out the experiment, the total number of arrivals is infinite (one arrival during each interval $I_k$). Therefore, $Y_n$ is unity for infinitely many values of $n$, the event $\set{ \limu{ n }{ \infty } Y_n = 0}$ has zero probability, and we do not have convergence with probability 1.

At any given time, there is only a, small, diminishing with $n$, probability of a substantial deviation from $0$, which implies convergence in probability.

On the other hand, given enough time, a substantial deviation from 0 is certain to occur and for this reason, we do not have convergence with probability 1.