Almost sure convergence and the strong law of large numbers

$$In this post I’m going to introduce almost sure convergence for sequences of random variables, compare it with convergence in probability, and prove a form of the strong law of large numbers (SLLN). I’ll finish with an application to random walks.

Let $(\mathrm{\Omega },\mathcal{F},P)$ be a probability space and let $\{X_n:n\in \mathbb{N}\}$ be a collection of random variables from $\mathrm{\Omega }$ to $\mathbb{R}$. The sequence $(X_n)$ is defined to converge almost surely (“a.s.”) to some limiting random variable $X$, denoted $X_n\stackrel{\text{a.s.}}{\to }X$, if for almost all $\omega \in \mathrm{\Omega }$ $\underset{n\to \mathrm{\infty }}{lim}{X}_n(\omega )$ exists and is equal to $X(\omega )$. More succinctly,
$$X_n\stackrel{\text{a.s.}}{\to }X⟺P(lim{X}_n=X)=1.$$

Thinking of $\{X_n:n\in \mathbb{N}\}$ as a discrete time stochastic process, $X_n\stackrel{\text{a.s.}}{\to }X$ means that almost all sample paths converge to the output of a measurable function $X$. In the simplest case the limiting distribution is a.s. constant and this just means almost all sample paths have the same limit. The figure below gives an example of this: each of the three lines represents a single sample path $(X_1(\omega ),X_2(\omega ),\dots )$ coming from a process with $X_n\stackrel{\text{a.s.}}{\to }1$, and indeed all three paths can be seen to converge to that limit. These were generated by taking the cumulative mean of iid $\mathcal{N}(1,1)$ random variables so the a.s. convergence is a consequence of the SLLN.

I’ll start by proving that $lim{X}_n$ is a measurable function when it exists.

Result 1: if $Y_1,Y_2,\dots$ is a sequence of Borel functions from $\mathrm{\Omega }$ to $\mathbb{R}$, then $S:\mathrm{\Omega }\to \mathbb{R}$ with $S(\omega )=lim sup{Y}_n(\omega )$ is Borel.

Pf: I will prove this by showing that $\{S\le c\}:=\{\omega \in \mathrm{\Omega }:S(\omega )\le c\}$ for arbitrary $c\in \mathbb{R}$ is equal to a countable union and intersection of measurable sets. The closure of $\sigma$-algebras w.r.t. such operations then guarantees $\{S\le c\}$ to be measurable. Since $\{(-\mathrm{\infty },c]:c\in \mathbb{R}\}$ generates the Borel $\sigma$-algebra this is sufficient for the result (and also necessary).

Fix $c\in \mathbb{R}$ and consider the preimage $\{S\le c\}$. If this set is empty then it is measurable, so WLOG I can assume I can choose some arbitrary $\omega \in \{S\le c\}$.

I have $S(\omega )=lim sup{Y}_n(\omega )$ so by definition
$$S(\omega )=\underset{n\to \mathrm{\infty }}{lim}\underset{k\ge n}{sup}{Y}_k(\omega ).$$
By the definition of a limit this means $\mathrm{\forall }\epsilon >0$ there is an $N\in \mathbb{N}$ such that $n\ge N⟹|\underset{k\ge n}{sup}{Y}_k(\omega )–S(\omega )|<\epsilon$.

The sequence of “upper tail” suprema $\{\underset{k\ge n}{sup}{Y}_k(\omega ):n\in \mathbb{N}\}$ is nonincreasing since at each step $n$ I’ll either keep the supremum the same (if it comes from values past $Y_n(k)$) or it’ll decrease (if $Y_n(\omega )$ was the sole value responsible for the supremum). This monotonicity means
$$|\underset{k\ge n}{sup}{Y}_k(\omega )–S(\omega )|=\underset{k\ge n}{sup}{Y}_k(\omega )–S(\omega )$$
so for $n\ge N$ I have
$$\underset{k\ge n}{sup}{Y}_k(\omega )<S(\omega )+\epsilon \le c+\epsilon$$
where the 2nd inequality is because of my particular choice of $\omega$.

When the $sup$ of a collection is bounded from above then every element in turn is, so I now have that, for my arbitrary $c\in \mathbb{R}$ and $\omega \in \{S\le c\}$, for any $j\in {\mathbb{N}}_{+}$ (this is now playing the role of $\epsilon$ and removes the dependency on an arbitrary constant) there is some $N_j\in \mathbb{N}$ such that
$$Y_k(\omega )\le c+j^{-1}\mathrm{\forall }k\ge N_j.$$
Let
$$A_c:=\bigcap _{j\ge 1}\bigcup _{N\ge 1}\bigcap _{k\ge N}\{Y_k\le c+j^{-1}\}.$$
I just showed that for every $j\ge 1$ there is an $N\in \mathbb{N}$ such that $\omega \in \{Y_k\le c+j^{-1}\}$ for all $k\ge N$, which means $\omega \in A_c$ so $\{S\le c\}\subseteq A_c$.

Alternatively, let $\omega \in A_c$. Then by the same reasoning I know $\mathrm{\forall }j\ge 1$ there is at least one $N\in \mathbb{N}$ such that $k\ge N⟹Y_k(\omega )\le c+j^{-1}$. This means $\underset{k\ge N}{sup}{Y}_k(\omega )\le c+j^{-1}$ therefore
$$S(\omega )=lim sup{Y}_k(\omega )\le c$$
by monotonicity. This shows that $A_c\subseteq \{S\le c\}$, so $A_c=\{S\le c\}$. $A_c$ is built entirely out of Borel sets so this shows that $\{S\le c\}$ is Borel.

$\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg"\; loading="lazy">}$

I’ll use without proof the analogous result that $\omega \mapsto lim inf{Y}_n(\omega )$ is also measurable.

I now want to prove the following result:

Result 2: For any collection of Borel functions $\{Y_n:n\in \mathbb{N}\}$ both the set
$$E:=\{\omega \in \mathrm{\Omega }:\underset{n\to \mathrm{\infty }}{lim}{Y}_n(\omega )\text{ exists}\}$$
and the function $Z:\mathrm{\Omega }\to \mathbb{R}$ defined by
$$Z(\omega )=\{\begin{array}{ll}\underset{n\to \mathrm{\infty }}{lim}{Y}_n(\omega )& \omega \in E\\ Y_1(\omega )& \text{o.w.}\end{array}$$
are measurable.

This result is good because it means that I don’t have to worry about measurability when I have something like $P(lim{X}_n=X)=1$ since there’s only a null set where the limit may not exist and I can just send those to $X_1(\omega )$ without affecting anything.

Pf: $lim{Y}_n(\omega )$ existing is equivalent to $lim sup{Y}_n(\omega )=lim inf{Y}_n(\omega )$. Both of these functions are measurable so the function $h:\mathrm{\Omega }\to \mathbb{R}$ given by $h(\omega )=lim sup{Y}_n(\omega )–lim inf{Y}_n(\omega )$ is also measurable. $\{0\}$ is a Borel set so
$$h^{-1}(\{0\})=E\in \mathcal{F}.$$
For $Z$, I will first prove the following. Let $f$ and $g$ be Borel and define
$$h(\omega )=\{\begin{array}{ll}f(\omega )& \omega \in A\\ g(\omega )& \text{o.w.}\end{array}$$
for some $A\in \mathcal{F}$. Fix $c\in \mathbb{R}$ and take $H=\{h\le c\}\subseteq \mathrm{\Omega }$. Then
$$H=H\cap (A\cup A^c)=(H\cap A)\cup (H\cap A^c).$$
By construction $H\cap A=\{\omega \in A:h(\omega )\le c\}$ and for all of these $\omega$ I have $h(\omega )=f(\omega )$, so $H\cap A=\{f\le c\}\cap A$ and that is measurable. The same argument applied to $H\cap A^c$ shows that set is also measurable, so $H$ is the union of two measurable sets and by the closure of $\mathcal{F}$ $H$ is also measurable.

Applying this to $Z$, on $E$ I have $\underset{n}{lim}{Y}_n=lim sup{Y}_n$ which is measurable, and $Y_1$ is also measurable, so this means that my above result with $h$ applies to $Z$ and $Z$ is therefore Borel.

$\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg"\; loading="lazy">}$

I will compare this to convergence in probability, which as a reminder (see e.g. my post here) is defined by
$$X_n\stackrel{\text{p}}{\to }X⟺\mathrm{\forall }\epsilon >0\underset{n}{lim}P(|X_n–X|>\epsilon )=0.$$
Convergence in probability measures the size of the subset of $\mathrm{\Omega }$ leading to $|X_n–X|>\epsilon$, and requires that the measure of these sets heads to zero as I advance along the sequence. The big difference between convergence a.s. and convergence in probability is that $X_n\stackrel{\text{p}}{\to }X$ isn’t about the individual trajectories. It can be the case that $lim{X}_n$ exists almost nowhere and yet $X_n$ still converges in probability to something. The next result gives an explicit example of this.

Result 3: $X_n\stackrel{\text{p}}{\to }X$ does not imply $X_n\stackrel{\text{a.s.}}{\to }X$.

Pf: I’ll prove this by explicitly constructing a sequence of random variables with these properties. Take $\mathrm{\Omega }=[0,1)$, $\mathcal{F}={\mathbb{B}}_{[0,1)}$ (so it’s the Borel $\sigma$-algebra generated by the open subsets of $[0,1)$), and $P=\lambda$, i.e. the Lebesgue measure (which is a probability measure on this sample space).

Now for each positive $n\in \mathbb{N}$ let ${\mathcal{P}}_n$ be the partition of $\mathrm{\Omega }$ formed by cutting $\mathrm{\Omega }$ up into $2^n$ adjacent half-open intervals, so ${\mathcal{P}}_n$ contains $2^n$ sets of the form $A_{nk}:=[k/2^n,(k+1)/2^n)$ for $k=0,\dots ,2^n-1$. Now I’ll create a triangular array of random variables $\{X_{nk}:n=1,2,\dots ,k=0,\dots ,2^n-1\}$ with $X_{nk}={\mathbf{1}}_{A_{nk}}$ (all of the $A_{nk}$ are Borel so the $X_{nk}$ are all Borel too). I’ll flatten this into a sequence $(Y_m)$ by enumerating first along $k$ within each value of $n$ and then along $n$, so
$$(Y_m)=(X_{10},X_{11},X_{20},X_{21},X_{22},X_{23},X_{30},\dots ).$$

Fix $\epsilon >0$. Then $P(|Y_m|>\epsilon )=P(Y_m=1)=P(A_{nk})=2^{-n}$ for the corresponding $n$. $m\to \mathrm{\infty }$ implies $n\to \mathrm{\infty }$ so $P(|Y_m|>\epsilon )\to 0$ for this arbitrary $\epsilon >0$, which shows $Y_m\stackrel{\text{p}}{\to }0$.

But for almost sure convergence there’s a problem. For any $\omega \in \mathrm{\Omega }$ it will be in exactly one element of each ${\mathcal{P}}_n$, so in each row of the triangular array (I’m thinking of $n$ indexing rows and $k$ columns) I’ll have all of the $X_{nk}(\omega )=0$ except for the single one taking a value of $1$ for the piece of the partition containing $\omega$. This is the case for every $n\in \mathbb{N}$ so $(Y_m(\omega ))$ hits both $0$ and $1$ infinitely often and therefore this trajectory doesn’t converge to anything. This is true for every $\omega \in \mathrm{\Omega }$ so in fact there is not a single element of the sample space with a convergent trajectory. This means $(Y_m)$ doesn’t have a limiting distribution in the almost sure / pointwise sense.

$\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg"\; loading="lazy">}$

The crux of this proof was that convergence in probability doesn’t care about which $\omega$s it’s measuring at each time. In this case the $A_{nk}$ had monotonically decreasing measure but the particular $\omega$ in them jumped around so no individual trajectories converged even though at any given time $m$ the fraction of $\mathrm{\Omega }$ leading to $Y_m=1$ was decreasing.

The converse is true, though:

Result 4: $X_n\stackrel{\text{a.s.}}{\to }X⟹X_n\stackrel{\text{p}}{\to }X$

Pf: Fix $\epsilon >0$. Define
$$E_m=\{|X_m–X|>\epsilon \}$$
and
$$A_n=\bigcup _{m\ge n}{E}_m$$
so $A_n$ collects the $\omega$ where there is at least one $m\ge n$ such that $X_m(\omega )$ and $X(\omega )$ are at least $\epsilon$ apart. All of these sets are measurable so I don’t need to worry about that.

$A_n=E_n\cup A_{n+1}$ so the sequence $(A_n)$ is nonincreasing and settles on
$$\bigcap _{n\ge 1}{A}_n=\bigcap _{n\ge 1}\bigcup _{m\ge n}{E}_m=lim sup{E}_m.$$
$lim sup{E}_m$ is exactly the $\omega \in \mathrm{\Omega }$ that are in infinitely many of the $E_m$. If $\omega$ is in infinitely many $E_m$ then it cannot be the case that $lim{X}_n(\omega )=X(\omega )$ since $X_n(\omega )$ never settles within $\epsilon$ of $X(\omega )$. But since $X_n\stackrel{\text{a.s.}}{\to }X$ it must be that this set has measure zero, i.e. $P(lim sup{E}_n)=0$.

By the continuity of $P$ and the nesting of the $A_n$, I have
$$0=P(lim sup{E}_m)=P(lim{A}_n)=limP(A_n).$$
$P(A_n)=P(E_n\cup A_{n+1})\ge P(E_n)$ so this means
$$0=limP(E_n)=limP(|X_n–X|>\epsilon )$$
so $X_n\stackrel{\text{p}}{\to }X$.

$\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg"\; loading="lazy">}$

I’m building up to proving a form of the strong law of large numbers but I’ll need a standard helper result first:

Borel-Cantelli lemma. Let $A_1,A_2,\cdots \in \mathcal{F}$. Then
$$\sum _{n=1}^{\mathrm{\infty }}P(A_n)<\mathrm{\infty }⟹P(lim sup{A}_n)=0.$$
In other words, this result says that if the probabilities of these events decay fast enough then almost all sample outcomes are only in finitely many of them.

Pf: I’ll build a new sequence of events $B_1,B_2,\dots$ where
$$B_n=\bigcup _{m\ge n}{A}_m$$
(this is very reminiscent of the proof of Result 4).

Then $B_1\supseteq B_2\supseteq \cdots \supseteq lim sup{A}_m$. By the continuity of measure
$$limP(B_n)=P(lim sup{A}_n).$$
$$P(B_n)=P\left(\bigcup _{m\ge n}{A}_m\right)\le \sum _{m\ge n}P(A_m)$$
by subadditivity. By assumption $\sum _{n=1}^{\mathrm{\infty }}P(A_n)<\mathrm{\infty }$ so these tail sums $\sum _{m\ge n}P(A_m)$ must converge to zero. This means
$$limP(B_n)=P(lim sup{A}_n)=0.$$
$\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg"\; loading="lazy">}$

I’m now ready to prove my main result.

SLLN: Let $X_1,X_2,\dots$ be an iid sequence of random variables with $\mathrm{E}{X}_1^4<\mathrm{\infty }$, and let $S_n=\sum _{i\le n}{X}_i$. Then $S_n/n\stackrel{\text{a.s.}}{\to }\mathrm{E}{X}_1$.

The full SLLN only requires $\mathrm{E}|X_1|<\mathrm{\infty }$ but this is a much simpler proof which is why I’m just doing this one, even though it requires a stronger assumption. In a future post I’ll go through the proof of the full SLLN.

Pf: I’ll be considering terms like $|S_n/n–\mathrm{E}{X}_1|$ so WLOG I can just take $\mathrm{E}{X}_1=0$ and show $S_n/n\stackrel{\text{a.s.}}{\to }0$. So
$$P(|S_n/n|>\epsilon )=P(|S_n/n{|}^4>{\epsilon }^4)\le \frac{\mathrm{E}{S}_n^4}{n^4{\epsilon }^4}$$
by Markov’s inequality (I prove this in this post). Expanding $S_n^4$ via the multinomial theorem I have
$$S_n^4=\sum _{k_1+\cdots +k_n=4}(\genfrac{}{}{0ex}{}{4}{k_1,\dots ,k_n})\prod _{m=1}^n{X}_m^{k_m}.$$
Since the power of $4$ is small relative to the number of terms $n$ I’ll have many of these indices equal to zero. I’ll be taking the expected value of $S_n^4$ and I know $\mathrm{E}{X}_1=0$ so I only need to figure out which terms only have $X_i^2$ or $X_i^4$ in them.

4th moment terms arise when one $k_m=4$, and in those cases all the other $k_{\ell }=0$. This means I’ll have a $\sum _{i=1}^n{X}_i^4$ term (the multinomial coefficient for all of these is just $1$).

For the 2nd powers I need exactly two of the $k_m$ to be $2$, so the multinomial coefficient is $6$ and overall I get
$$\frac{1}{2}\cdot 6\sum _{i\ne j}{X}_i^2{X}_j^2$$
where the $\frac{1}{2}$ is because my indexing double counts each term.

Putting this all together I have
$$\mathrm{E}{S}_n^4=n\mathrm{E}{X}_1^4+3n(n-1)(\mathrm{E}{X}_1^2{)}^2$$
which means
$$P(|S_n/n|>\epsilon )\le \frac{n\mathrm{E}{X}_1^4+3n(n-1)(\mathrm{E}{X}_1^2{)}^2}{n^4{\epsilon }^4}\le {\epsilon }^{-4}(n^{-3}\mathrm{E}{X}_1^4+3n^{-2}(\mathrm{E}{X}_1^2{)}^2).$$
The right hand side is summable so this means
$$\sum _{n=1}^{\mathrm{\infty }}P(|S_n/n|>\epsilon )<\mathrm{\infty }.$$ Taking $A_n=\{|S_n/n|>\epsilon \}$, I can use Borel-Cantelli to conclude
$$P(lim sup{A}_n)=0.$$
But $lim sup{A}_n$ is exactly the subset of $\mathrm{\Omega }$ with $\omega$ that are in infinitely many of these events. If almost all $\omega$ are only in finitely many of them, then since $\epsilon$ is arbitrary, I have shown that almost all sample paths converge to zero so $S_n/n\stackrel{\text{a.s.}}{\to }0$.

$\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg"\; loading="lazy">}$

One way to think of this that I like is using random walks. Given an iid collection of random variables $(X_n{)}_{n\in \mathbb{N}}$, I can form a random walk $(S_n{)}_{n\in \mathbb{N}}$ by the cumulative addition of $(X_n)$ so $S_n=\sum _{i\le n}{X}_i$. Typically the idea is that $(X_n)$ represents some white noise process and I’m (discretely, in this case) integrating $(X_n)$ to get $(S_n)$ which wanders around according to the fluctuations of the $X_n$. Taking $\mathrm{E}{X}_1=0$, if I assume $\mathrm{E}|X_1|<\mathrm{\infty }$ then the SLLN applies so $S_n/n\stackrel{\text{a.s.}}{\to }0$. In terms of sample paths, this means that almost all sample space elements have trajectories that are dominated by $n$. It’s certainly not the case that all trajectories are eventually squashed to $0$, but the set of outcomes that lead to non-squashed trajectories is measure zero.

As an example, if $X_i\stackrel{\text{iid}}{\sim }\mathcal{N}(0,1)$ so $(S_n)$ is a discrete time brownian motion, then the SLLN tells me that $S_n/n\stackrel{\text{a.s.}}{\to }0$. But there are trajectories that have $X_i(\omega )\ge 2$ for all $i\in \mathbb{N}$ and lead to $S_n(\omega )/n$ not converging on $0$, or even diverging to $\pm \mathrm{\infty }$. But because $\mathrm{E}|X_1|<\mathrm{\infty }$ and the $X_i$ are iid, it’s rare enough to consistently produce large enough jumps in the same direction so that the whole collection of sample space elements with these trajectories is measure zero.

For comparison, if the $X_i$ were iid Cauchy, so $\mathrm{E}|X_1|=\mathrm{\infty }$, then the SLLN doesn’t hold and intuitively this makes sense because no matter how far along I am in a trajectory, there’s a high enough probability of a massive shock that moves me to a new location so I don’t get convergence on a large subset of my sample space. Below is a plot of one trajectory of such a random walk.

If $X\sim \text{Cauchy}(0,1)$ (i.e. location of $0$ and scale of $1$) then the characteristic function of $X$ is ${\phi }_X(t)=e^{-|t|}$ (as a total side comment, the distribution being symmetric around zero implies that the characteristic function is purely real-valued as I explore in this post). Then
$${\phi }_{S_n/n}(t)={\phi }_{S_n}(t/n)={\phi }_X(t/n{)}^n=e^{-|t|}$$
so $S_n/n\sim \text{Cauchy}(0,1)$ too. In words, the heavy tails of the Cauchy distribution are strong enough to overpower the effect of averaging and at every step in the random walk, even with division by $n$, the distribution is the same as that of $X_1$ so no convergence happens in general. This shows the importance of the $\mathrm{E}|X_1|<\mathrm{\infty }$ condition.