Strong Law of Large numbers

The Strong Law of Large Numbers (SLLN) is a fundamental result in probability theory that describes the long-term behavior of the average of a sequence of random variables. Let

X_1, X_2, \ldots

be a sequence of i.i.d. random variables with a finite first moment, i.e.,

\mathbb{E} |X_1| < \infty

. The SLLN asserts that the sample average of these variables converges almost surely to the expected value:

\begin{equation*}\frac{X_1 + X_2 + \dots + X_n}{n} \xrightarrow{\text{a. s.}} \mathbb{E} X_1 \;, \text{ as n} \rightarrow \infty.\end{equation*}

This means that as the number of observations

n

increases, the sample average will almost surely converge to the true mean

\mathbb{E} X_1

Motivation

Coin Flip Experiment

Fair coin flip experiment

Consider a fair coin flip experiment where we assign:

\begin{equation*}X_i= \begin{cases}1, & \text{if heads}, \\ 0, & \text{if tails} .\end{cases}\end{equation*}

The expected value is clearly

\mathbb{E}[X_i] = \frac{1}{2}

. But what happens when we perform this experiment repeatedly?

In our animation, we observe:

The horizontal line at $y = 0.5$ represents $\mathbb{E}[X_i]$
The blue path shows $\frac{S_n}{n}$ as $n$ increases
Early fluctuations are larger due to the $\frac{1}{n}$ scaling
As $n \to \infty$ , the path stabilizes near $\mathbb{E}[X_i] = 0.5$

Monte-Carlo Method

Calculating

\pi

with Monte-Carlo

One of the most important applications of the SLLN is in the Monte Carlo method, which is used to numerically estimate quantities that are difficult or impossible to calculate analytically. The accuracy of Monte Carlo method depends on the convergence of the sample averages to the true values, which is guaranteed by the SLLN.

Let's define a random variable

X

based on randomly chosen points

(U_1, U_2)

in a

6 \times 6

square:

\begin{equation*}X = \begin{cases} 1, & \text{if } U_1^2 + U_2^2 \leq 9 \\ 0, & \text{otherwise} \end{cases}\end{equation*}

where

U_1, U_2 \sim \text{Uniform}(-3, 3)

The expected value of

X

is:

\begin{equation*}\mathbb{E}[X] = \mathbb{P}(U_1^2 + U_2^2 \leq 9) = \frac{\text{Area of Circle}}{\text{Area of Square}} = \frac{\pi r^2}{(2r)^2} = \frac{\pi}{4}\end{equation*}

Let

X_1, \ldots, X_n

be i.i.d. copies of

X

. By the Strong Law of Large Numbers:

\begin{equation*}\frac{1}{n}\sum_{i=1}^n X_i \xrightarrow{a.s.} \mathbb{E}[X] = \frac{\pi}{4} \quad \Longrightarrow \quad 4 \cdot \frac{1}{n}\sum_{i=1}^n X_i \xrightarrow{a.s.} \pi\end{equation*}

Strong Law of Large Numbers with finite 4th moment

The following example is Durrett [Durrett2019], Theorem 2.3.5, p. 59.

One of the earliest results in this direction is the following theorem, which can be easily proved with Chebyshev inequality and Borel-Cantelli lemma.

CANTELLI

Let

X_1, X_2, \ldots

be i.i.d. with

\mathbb{E}X_1^4 < \infty

. If

S_n = X_1 + \cdots + X_n

, then

\begin{equation*}\mathbb{E}X_1^4 < \infty \quad \Longrightarrow \quad \frac{S_n}{n} \xrightarrow{\text{a.s.}} \mathbb{E}X_1\end{equation*}

\quad

Proof. By letting

X_i' = X_i - \mathbb{E}X_1

, we can suppose without loss of generality that

\mathbb{E}X_1 = 0

. Now

\begin{equation*}\mathbb{E}S_n^4 = \mathbb{E}\left( \sum_{i=1}^n X_i \right)^4 = \mathbb{E} \sum_{1 \leq i,j,k,l \leq n} X_i X_j X_k X_l\end{equation*}

Terms in the sum of the form

\mathbb{E}(X_i^3 X_j)

\mathbb{E}(X_i^2 X_j X_k)

, and

\mathbb{E}(X_i X_j X_k X_l)

are

0

(if

i,j,k,l

are distinct) since the expectation of the product is the product of the expectations because of the independence, and in each case one of the terms has expectation 0. The only terms that do not vanish are those of the form

\mathbb{E}X_i'^4

and

\mathbb{E}X_i'^2 X_j'^2 = (\mathbb{E}X_i'^2)^2

. There are

n

and

3n(n - 1)

of these terms, respectively. In the second case, we can pick the two indices in

n(n - 1)/2

ways, and with the indices fixed, the term can arise in a total of six ways:

\{ 1, 2\}, \{ 1, 3\}, \{ 1, 4\}, \{ 2, 3\}, \{ 2, 4\}

and

\{ 3, 4\}

. The last observation implies

\begin{equation*}\mathbb{E}S_n^4 = n\mathbb{E}X_i^4 + 3(n^2 - n)(\mathbb{E}X_i^2)^2 \leq Cn^2\end{equation*}

where

C < \infty

. Chebyshev’s inequality gives us

\begin{equation*}\mathbb{P}\left(\frac{|S_n|}{n} > \epsilon\right) \overset{\text{Chebyshev}}{\leq} \frac{\mathbb{E}(S_n^4)}{(n\epsilon)^4} \leq \frac{C}{n^2 \epsilon^4}\quad \overset{\text{Borel-Cantelli}}{\Longrightarrow} \quad\exists n_0, \, \forall n \geq n_0 \; \frac{|S_n|}{n} \leq \epsilon\end{equation*}

Since

\epsilon

is arbitrary, the proof is complete.

\Box

Toeplitz and Kronecker Lemmas

In this section, we introduce the Toeplitz and Kronecker Lemmas, which play crucial roles in proving the Strong Law of Large Numbers with finite absolute first monent.

Toeplitz Lemma

The Toeplitz Lemma provides conditions under which the averages of a sequence

\{x_n\}_{n\geq 1}

converge to a limit.

TOEPLITZ

Let

\{a_n\}

be a sequence of nonnegative numbers,

b_n = \sum_{i=1}^n a_i

b_1 = a_1 > 0

, and

b_n \nearrow \infty

n \to \infty

. Let

\{x_n\}_{n\geq 1}

be a sequence of numbers converging to

x

. Then

\begin{equation*}x_n \to x \quad \Longrightarrow \quad \frac{1}{b_n} \sum_{j=1}^n a_j x_j \to x\end{equation*}

In particular, if

a_n = 1, \; n \geq 1

and

b_n = n

then

\begin{equation*}a_n = 1, n \geq 1 \text{ and } b_n = n \quad \Longrightarrow \quad \frac{x_1 + \ldots + x_n}{n} \to x.\end{equation*}

\quad

Proof. Let

\varepsilon > 0

, and let

n_0 = n_0(\varepsilon)

be such that

\left|x_n - x\right| \leq \varepsilon/2

for all

n \geq n_0

. Choose

n_1 > n_0

such that

\begin{equation*}\frac{1}{b_{n_1}} \sum_{j=1}^{n_0} \left| x_j - x \right| < \frac{\varepsilon}{2}.\end{equation*}

Then, for any

n > n_1

\begin{equation*}\left|\frac{1}{b_n} \sum_{j=1}^n a_j x_j - x\right| = \left|\frac{1}{b_n} \sum_{j=1}^n a_j x_j - \frac{b_n x}{b_n} \right| = \left|\frac{1}{b_n} \sum_{j=1}^n a_j x_j - \frac{\sum_{j=1}^n a_j x}{b_n} \right| =\frac{1}{b_n} \left| \sum_{j=1}^n a_j x_j - \sum_{j=1}^n a_j x\right|\end{equation*}

Then using the triangle inequality and splitting sum ut to

n_0

\begin{align*}& \leq \frac{1}{b_n} \sum_{j=1}^n a_j \left|x_j - x\right| = \frac{1}{b_n} \sum_{j=1}^{n_0} a_j \left|x_j - x\right| + \frac{1}{b_n} \sum_{j=n_0 + 1}^n a_j \left|x_j - x\right| \leq \\&\stackrel{b_{n_1} \leq b_n }{\leq} \underbrace{\frac{1}{b_{n_1}} \sum_{j=1}^{n_0} a_j \left|x_j - x\right|}_{\leq \frac{\varepsilon}{2}} + \frac{1}{b_n} \sum_{j=n_0 + 1}^n a_j \underbrace{\left|x_j - x\right|}_{\leq \frac{\varepsilon}{2}} \leq \frac{\varepsilon}{2} + \frac{b_n - b_{n_0}}{b_n} \frac{\varepsilon}{2} \leq \varepsilon.\end{align*}

Kronecker Lemma

SERIES AND AVERAGES, KRONECKER

Let

\{b_n\}

be a sequence of positive increasing numbers,

b_n \nearrow \infty

n \to \infty

, and let

\{x_n\}

be a sequence of numbers such that

\sum x_n

converges. Then

\begin{equation*}\sum_{n=1}^{\infty} x_n \text{ converges }\Longrightarrow\frac{1}{b_n} \sum_{j=1}^n b_j x_j \to 0, \quad n \to \infty.\end{equation*}

\quad

Proof. Let

b_0 = 0

S_0 = 0

S_n = \sum_{j=1}^n x_j

. Then from

x_j = S_j - S_{j-1}

\begin{equation*}\sum_{j=1}^n b_j x_j = \sum_{j=1}^n b_j (S_j - S_{j-1}) = b_n S_n - b_0 S_0 - \sum_{j=1}^n S_{j-1} \underbrace{(b_j - b_{j-1})}_{a_j}\quad \Longrightarrow \quad\frac{1}{b_n} \sum_{j=1}^n b_j x_j = S_n-\frac{1}{b_n} \sum_{j=1}^n S_{j-1} a_j,\end{equation*}

since, if

S_n \rightarrow x

, then, by Toeplitz's lemma,

\begin{equation*}\frac{1}{b_n} \sum_{j=1}^n S_{j-1} a_j \rightarrow x\quad \Longrightarrow \quad \frac{1}{b_n} \sum_{j=1}^n b_j x_j =\underbrace{S_n}_{\to x}-\underbrace{\frac{1}{b_n} \sum_{j=1}^n S_{j-1} a_j}_{\to x} \rightarrow 0 \qquad \Box\end{equation*}

REMARK

b_n = n

x_n = y_n / n

and

\sum (y_n / n)

converges, then

\begin{equation*}\frac{y_1 + \ldots + y_n}{n} \to 0, \quad n \to \infty.\end{equation*}

Proof of Strong Law of Large Numbers

The following proof is taken from Shiryaev [Shiryaev2019], pp. 16–17.

Here we present the strongest version of the SLLN, which was proved by Kolmogorov and require the finitnes of the expectation of the absolute value.

STRONG LAW OF LARGE NUMBERS, KOLMOGOROV

Let

X_1, X_2, \ldots

be i.i.d. with

\mathbb{E} | X_1 | < \infty

. If

S_n = X_1 + \cdots + X_n

, then

\begin{equation*}\mathbb{E}| X_1 | < \infty \quad \Longrightarrow \quad \frac{S_n}{n} \xrightarrow{\text{a.s.}} \mathbb{E}X_1\end{equation*}

We break down the proof of the theorem in several steps. First, we consider the truncated sequence

\{X_n^{\prime}\}

, noting that the convergence of

S_n/n

is equivalent to the convergence of

S_n^{\prime}/n

. Next, we apply Kronecker's Lemma and Kolmogorov's Two-Series Theorem to derive the final result.

Truncated sequence

\quad

Proof. Let's suppose without a loss of generality

\mathbb{E}X_1

and define the truncate random variable

X_n^{\prime}

\begin{equation*}X_n^{\prime}=\begin{cases}X_n, & |X_n| \leq n, \\0, & |X_n| > n.\end{cases}\end{equation*}

Then

\begin{equation*}\sum_{n=1}^{\infty} \mathbb{P}\left\{X_n^{\prime} \neq X_n\right\} =\sum_{n=1}^{\infty} \mathbb{P}\left\{|X_1|>n\right\} \leq \int_0^{\infty} \mathbb{P}\left\{|X_1|>t\right\} d t \stackrel{\text{def}}{=} \mathbb{E}|X|<\infty .\end{equation*}

Hence, the Borel-Cantelli lemma yields

\mathbb{P}\left\{X_n^{\prime} \neq X_n\right.

i.o.

\}=0

, and so

X_n^{\prime}=X_n

for all but finitely many

n \in \mathrm{N}

a.s.

Equivalent convergence of the truncated sequence

Because of

X_n^{\prime}=X_n

for all but finitely many

n \in \mathrm{N}

a.s., we have

\begin{equation*}\frac{X_1 + X_2 \cdots + X_n}{n} \xrightarrow{\text{a.s.}} 0\quad \Longleftrightarrow \quad\frac{X_1^{\prime} + X_2^{\prime} \cdots + X_n^{\prime}}{n} \xrightarrow{\text{a.s.}} 0\end{equation*}

Note that in general

\hat{X}_n \neq 0

, but

\begin{equation*}\mathbb{E}\hat{X}_n = \mathbb{E}\hat{X}_n \mathbf{1}_{\{|\hat{X}_n| < n\}} = \mathbb{E}\hat{X}_1 \mathbf{1}_{\{|\hat{X}_1| < n\}} \to \mathbb{E}X_1 = 0.\end{equation*}

Hence, by Toeplitz Lemma, for

a_n = 1, \; n \geq 1

and

b_n = n

\begin{equation*}a_n = 1, b_n = n \text{ and } \mathbb{E}\hat{X}_n \xrightarrow{n\to\infty} 0\quad \overset{\text{Toeplitz}}{\Longrightarrow} \quad\frac{1}{n} \sum_{k=1}^n \mathbb{E}\hat{X}_k \xrightarrow{n\to\infty} 0.\end{equation*}

By Kronecker Lemma if

\begin{equation*}\sum_{n=1}^{\infty} \frac{X_n^{\prime}}{n} \text{ converges a.s. }, b_n = n \quad \overset{\text{Kronecker}}{\Longrightarrow} \quad \frac{X_1^{\prime} + X_2^{\prime} \cdots + X_n^{\prime}}{n} \xrightarrow{\text{a.s.}} 0\end{equation*}

The convergence of variances

Define the centered truncated variable

\hat{X}_n := X_n^{\prime} - \mathbb{E}X_n^{\prime}

. It therefore remains to show that

\begin{equation*}\sum_{n=1}^{\infty} \frac{\operatorname{Var}(\hat{X}_n)}{n^2} < \infty.\end{equation*}

Indeed, by the Kolmogorov and Khinchin Theorem,

\begin{equation*}\sum_{n=1}^{\infty} \frac{\operatorname{Var}(\hat{X}_n)}{n^2} < \infty\overset{\text{Kolmogorov and Khinchin Theorem}}{\Longrightarrow}\sum_{n=1}^{\infty}\frac{\hat{X}_n}{n} \text{ converges a.s.}\end{equation*}

We can estimate, where we use that

\{ X_n \}_{n\geq1}

are i.i.d and

X_n^{\prime} \leq n

\begin{equation*}\sum_{n=1}^{\infty} \frac{\operatorname{Var}(\hat{X}_n)}{n^2}\overset{\operatorname{Var}(\hat{X}_n)\le \mathbb{E}((X_n')^2)}{\leq}\sum_{n=1}^{\infty} \frac{\mathbb{E}({X_n^{\prime}}^2)}{n^2} = \sum_{n=1}^{\infty} \frac{1}{n^2} \mathbb{E}\left(X_n^2 \mathbf{1}_{\{|X_n| \leq n\}}\right) \overset{\text{i.i.d.}}{=}\sum_{n=1}^{\infty} \frac{1}{n^2} \sum_{k=1}^n \mathbb{E}\left(X^2_{1} \mathbf{1}_{\{k-1 \leq |X_1| < k\}}\right) =\end{equation*}

We now interchange the order of summation, this is allowed because all terms are nonnegative:

\begin{align*}= \sum_{k=1}^{\infty} \mathbb{E}\left(X^2_{1} \mathbf{1}_{\{k-1 \leq |X_1| < k\}}\right) \cdot \sum_{n=k}^{\infty} \frac{1}{n^2}&\overset{\sum_{n=k}^{\infty} \frac{1}{n^2} \leq \frac{2}{k}}{\leq}2 \sum_{k=1}^{\infty} \frac{1}{k} \mathbb{E}\left(X^2_{1} \mathbf{1}_{\{k-1 \leq |X_1| < k\}}\right) \leq \\&\overset{X_1^2\le |X_1|\cdot k \text{ on } \{k-1 \leq |X_1| < k\}}{\leq}2 \sum_{k=1}^{\infty} \mathbb{E}\left(|X_1| \mathbf{1}_{\{k-1 \leq |X_1| < k\}}\right)= 2\mathbb{E} |X_1| < \infty.\end{align*}

References

[Shiryaev2019]Shiryaev, Albert N. Probability-2. Third edition. Springer, 2019.
[Durrett2019]Durrett, Rick. Probability: Theory and Examples. Fifth edition. Cambridge University Press, 2019. PDF.