Skip to content

Strong Law of Large Numbers

The strong law of large numbers (SLLN) describes the long-term behavior of the average.
STRONG LAW OF LARGE NUMBERS, KOLMOGOROV
Let X1,X2,…X_1,X_2,\ldots be independent, identically distributed random variables with E∣X1∣<∞\mathbb{E}|X_1|<\infty and Sn=X1+⋯+XnS_n=X_1+\cdots+X_n. Then
Snn=X1+⋯+Xnn→n→∞a.s.EX1.\begin{equation*}\frac{S_n}{n}=\frac{X_1+\cdots+X_n}{n}\xrightarrow[n\to\infty]{\mathrm{a.s.}}\mathbb{E}X_1.\end{equation*}

Motivation

Coin Flip Experiment

Let X1,…,XnX_1,\ldots,X_n represent independent tosses of a fair coin, with heads assigned 11 and tails assigned 00. Each XiX_i has the distribution
Xi={1,12,0,12.\begin{equation*}X_i=\begin{cases}1, & \frac{1}{2}, \\0, & \frac{1}{2}.\end{cases}\end{equation*}
By independence, the sample average Sn/nS_n/n has mean and variance
E ⁣[Snn]=EX1=12,Var⁡ ⁣(Snn)=Var⁡(X1)n=14n.\begin{align*}\mathbb{E}\!\left[\frac{S_n}{n}\right] &= \mathbb{E}X_1 = \frac{1}{2}, \\\operatorname{Var}\!\left(\frac{S_n}{n}\right) &= \frac{\operatorname{Var}(X_1)}{n} = \frac{1}{4n}.\end{align*}
For every ε>0\varepsilon>0, Chebyshev's inequality gives
P ⁣(∣Snn−12∣≥ε)≤Var⁡ ⁣(Snn)ε2=14nε2.\begin{equation*}\mathbb{P}\!\Biggl(\biggl|\frac{S_n}{n}-\frac{1}{2}\biggr|\geq\varepsilon\Biggr)\leq \frac{\operatorname{Var}\!\left(\frac{S_n}{n}\right)}{\varepsilon^2} = \frac{1}{4n\varepsilon^2}.\end{equation*}
So, the average Snn \frac{S_n}{n} converges to the the mean 12 \frac{1}{2} in probability and can be proved that convergence almost surely takes place using Borel–Cantelli lemma.

Monte-Carlo Method

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.
Define XiX_i using independently sampled points (U1,U2)(U_1, U_2) in the square [−1,1]2[-1,1]^2:
Xi={1,if U12+U22≤10,otherwise\begin{equation*}X_i = \begin{cases} 1, & \text{if } U_1^2 + U_2^2 \leq 1 \\ 0, & \text{otherwise} \end{cases}\end{equation*}
where U1U_1 and U2U_2 are independent and uniformly distributed on [−1,1][-1,1].
The expected value of X1X_1 is:
E[X1]=P(U12+U22≤1)=Area of CircleArea of Square=π22=π4\begin{equation*}\mathbb{E}[X_1] = \mathbb{P}(U_1^2 + U_2^2 \leq 1) = \frac{\text{Area of Circle}}{\text{Area of Square}} = \frac{\pi}{2^2} = \frac{\pi}{4}\end{equation*}
By the Strong Law of Large Numbers:
1n∑i=1nXi→a.s.E[X1]=π4⟹4⋅1n∑i=1nXi→a.s.π\begin{equation*}\frac{1}{n}\sum_{i=1}^n X_i \xrightarrow{a.s.} \mathbb{E}[X_1] = \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.
We first prove the strong law of large numbers under the stronger assumption that the fourth moment is finite. By Jensen's inequality,
(E∣X1∣)4≤E∣X1∣4<∞.\begin{equation*}\left(\mathbb{E}|X_1|\right)^4 \leq \mathbb{E}|X_1|^4 < \infty.\end{equation*}
Thus this assumption implies the integrability required by the general theorem. It also allows a short proof using Markov's inequality applied to the fourth power of the centered sum, followed by the Borel–Cantelli lemma.
CANTELLI
Let X1,X2,…X_1, X_2, \ldots be i.i.d. with EX14<∞\mathbb{E}X_1^4 < \infty. If Sn=X1+⋯+XnS_n = X_1 + \cdots + X_n, then
EX14<∞⟹Snn→a.s.EX1\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 Xi′=Xi−EX1X_i' = X_i - \mathbb{E}X_1, we can suppose without loss of generality that EX1=0\mathbb{E}X_1 = 0. Now
ESn4=E(∑i=1nXi)4=E∑1≤i,j,k,l≤nXiXjXkXl\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 E(Xi3Xj)\mathbb{E}(X_i^3 X_j), E(Xi2XjXk)\mathbb{E}(X_i^2 X_j X_k), and E(XiXjXkXl)\mathbb{E}(X_i X_j X_k X_l) are 00 (if i,j,k,li,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 EXi′4\mathbb{E}X_i'^4 and EXi′2Xj′2=(EXi′2)2\mathbb{E}X_i'^2 X_j'^2 = (\mathbb{E}X_i'^2)^2. There are nn and 3n(n−1)3n(n - 1) of these terms, respectively. In the second case, we can pick the two indices in n(n−1)/2n(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}\{ 1, 2\}, \{ 1, 3\}, \{ 1, 4\}, \{ 2, 3\}, \{ 2, 4\} and {3,4}\{ 3, 4\}. The last observation implies
ESn4=nEXi4+3(n2−n)(EXi2)2≤Cn2\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<∞C < \infty. Chebyshev’s inequality gives us
P(∣Sn∣n>ϵ)≤ChebyshevE(Sn4)(nϵ)4≤Cn2ϵ4⟹Borel-Cantelli∃n0, ∀n≥n0  ∣Sn∣n≤ϵ\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 {xn}n≥1\{x_n\}_{n\geq 1} converge to a limit.
TOEPLITZ
Let {an}\{a_n\} be a sequence of nonnegative numbers, bn=∑i=1naib_n = \sum_{i=1}^n a_i, b1=a1>0b_1 = a_1 > 0, and bn↗∞b_n \nearrow \infty, n→∞n \to \infty. Let {xn}n≥1\{x_n\}_{n\geq 1} be a sequence of numbers converging to xx. Then
xn→x⟹1bn∑j=1najxj→x\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 an=1,  n≥1a_n = 1, \; n \geq 1 and bn=nb_n = n then
an=1,n≥1 and bn=n⟹x1+…+xnn→x.\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 ε>0\varepsilon > 0, and let n0=n0(ε)n_0 = n_0(\varepsilon) be such that ∣xn−x∣≤ε/2\left|x_n - x\right| \leq \varepsilon/2 for all n≥n0n \geq n_0. Choose n1>n0n_1 > n_0 such that
1bn1∑j=1n0∣xj−x∣<ε2.\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>n1n > n_1,
∣1bn∑j=1najxj−x∣=∣1bn∑j=1najxj−bnxbn∣=∣1bn∑j=1najxj−∑j=1najxbn∣=1bn∣∑j=1najxj−∑j=1najx∣\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 n0n_0
≤1bn∑j=1naj∣xj−x∣=1bn∑j=1n0aj∣xj−x∣+1bn∑j=n0+1naj∣xj−x∣≤≤bn1≤bn1bn1∑j=1n0aj∣xj−x∣⏟≤ε2+1bn∑j=n0+1naj∣xj−x∣⏟≤ε2≤ε2+bn−bn0bnε2≤ε.\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 {bn}\{b_n\} be a sequence of positive increasing numbers, bn↗∞b_n \nearrow \infty as n→∞n \to \infty, and let {xn}\{x_n\} be a sequence of numbers such that ∑xn\sum x_n converges. Then
∑n=1∞xn converges ⟹1bn∑j=1nbjxj→0,n→∞.\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 b0=0b_0 = 0, S0=0S_0 = 0, Sn=∑j=1nxjS_n = \sum_{j=1}^n x_j. Then from xj=Sj−Sj−1x_j = S_j - S_{j-1}
∑j=1nbjxj=∑j=1nbj(Sj−Sj−1)=bnSn−b0S0−∑j=1nSj−1(bj−bj−1)⏟aj⟹1bn∑j=1nbjxj=Sn−1bn∑j=1nSj−1aj,\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 Sn→xS_n \rightarrow x, then, by Toeplitz's lemma,
1bn∑j=1nSj−1aj→x⟹1bn∑j=1nbjxj=Sn⏟→x−1bn∑j=1nSj−1aj⏟→x→0□\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
If bn=n b_n = n , xn=yn/n x_n = y_n / n and ∑(yn/n) \sum (y_n / n) converges, then
y1+…+ynn→0,n→∞.\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 X1,X2,…X_1, X_2, \ldots be i.i.d. with E∣X1∣<∞\mathbb{E} | X_1 | < \infty. If Sn=X1+⋯+XnS_n = X_1 + \cdots + X_n, then
E∣X1∣<∞⟹Snn→a.s.EX1\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 {Xn′}\{X_n^{\prime}\}, noting that the convergence of Sn/nS_n/n is equivalent to the convergence of Sn′/nS_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 EX1\mathbb{E}X_1 and define the truncate random variable Xn′X_n^{\prime}
Xn′={Xn,∣Xn∣≤n,0,∣Xn∣>n.\begin{equation*}X_n^{\prime}=\begin{cases}X_n, & |X_n| \leq n, \\0, & |X_n| > n.\end{cases}\end{equation*}
Then
∑n=1∞P{Xn′≠Xn}=∑n=1∞P{∣X1∣>n}≤∫0∞P{∣X1∣>t}dt=defE∣X∣<∞.\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 P{Xn′≠Xn\mathbb{P}\left\{X_n^{\prime} \neq X_n\right. i.o. }=0\}=0, and so Xn′=XnX_n^{\prime}=X_n for all but finitely many n∈Nn \in \mathrm{N} a.s.

Equivalent convergence of the truncated sequence

Because of Xn′=XnX_n^{\prime}=X_n for all but finitely many n∈Nn \in \mathrm{N} a.s., we have
X1+X2⋯+Xnn→a.s.0⟺X1′+X2′⋯+Xn′n→a.s.0\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 X^n≠0 \hat{X}_n \neq 0 , but
EX^n=EX^n1{∣X^n∣<n}=EX^11{∣X^1∣<n}→EX1=0.\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 an=1,  n≥1a_n = 1, \; n \geq 1 and bn=nb_n = n,
an=1,bn=n and EX^n→n→∞0⟹Toeplitz1n∑k=1nEX^k→n→∞0.\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*}∑n=1∞Xn′n converges a.s. ,bn=n⟹KroneckerX1′+X2′⋯+Xn′n→a.s.0\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 X^n:=Xn′−EXn′\hat{X}_n := X_n^{\prime} - \mathbb{E}X_n^{\prime}. It therefore remains to show that
∑n=1∞Var⁡(X^n)n2<∞.\begin{equation*}\sum_{n=1}^{\infty} \frac{\operatorname{Var}(\hat{X}_n)}{n^2} < \infty.\end{equation*}∑n=1∞Var⁡(X^n)n2<∞⟹Kolmogorov and Khinchin Theorem∑n=1∞X^nn converges a.s.\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 {Xn}n≥1\{ X_n \}_{n\geq1} are i.i.d and Xn′≤nX_n^{\prime} \leq n
∑n=1∞Var⁡(X^n)n2≤Var⁡(X^n)≤E((Xn′)2)∑n=1∞E(Xn′2)n2=∑n=1∞1n2E(Xn21{∣Xn∣≤n})=i.i.d.∑n=1∞1n2∑k=1nE(X121{k−1≤∣X1∣<k})=\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:
=∑k=1∞E(X121{k−1≤∣X1∣<k})⋅∑n=k∞1n2≤∑n=k∞1n2≤2k2∑k=1∞1kE(X121{k−1≤∣X1∣<k})≤≤X12≤∣X1∣⋅k on {k−1≤∣X1∣<k}2∑k=1∞E(∣X1∣1{k−1≤∣X1∣<k})=2E∣X1∣<∞.\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.