Law of Large Numbers

Let $\{X_i{\}}_{i=1}^n$ be iid Random Variables with mean $\mu$. Denote $\overline{X}={\sum }_{i=1}^n{X}_i/n$. Then

$$\overline{X}\stackrel{P}{\to }\mu ,$$

where $\stackrel{P}{\to }$ means convergence in probability. This is the weak law of large numbers (WLLN).

Substituting the Convergence in Probability with the Strong Convergence gives the strong law of large numbers (SLLN) under the same condition (finite mean):

$$\overline{X}\stackrel{\text{a.s.}}{\to }\mu .$$

Proof

WLLN Assuming Finite Variance

• ❗️ The following proof only works for r.v. with finite variance.

• 💡 prerequisite: Chebyshev Inequality.

Suppose $X_i$ has finite variance ${\sigma }^2$. For any $\epsilon >0$, by Chebyshev Inequality,

$$\begin{gathered} \mathbf{P}\left(\left|\bar{X}-\mu \right|>\epsilon \right)⩽\frac{1}{{\epsilon }^2}\mathbb{E}|\bar{X}-\mu {|}^2 \\ =\frac{{\sigma }^2}{n{\epsilon }^2}\to 0,\text{ as }n\to +\infty . \end{gathered}$$

WLLN with General Case

• 💡 prerequisite: Characteristic Function

We now remove the condition of finite variance. Since $X_n$ are independent,

$${\varphi }_{\overline{X}}(t)={\varphi }_{X_1/n}(t{)}^n={\varphi }_{X_1}(t/n{)}^n.$$

By the Taylor expansion and the fact that ${\varphi }_{X_1}(0)=1,{\varphi }_{X_1}^{\prime }(0)=i\mu$,

$${\varphi }_{\overline{X}}(t)=(1+i\mu t/n+o(t/n){)}^n\to e^{i\mu t}.$$

Since $e^{i\mu t}$ is also the CF of the constant $\mu$, by the inverse property and Convergence of Characteristic Functions, ${\sum }_i{X}_i/n\stackrel{d}{\to }\mu$. And since $\mu$ is a constant, convergence in distribution implies convergence in probability.

Comparison with Proof

Both using the Characteristic Function, the proof of WLLN only uses the first order Taylor expansion, while the proof of Central Limit Theorem uses the second order expansion. This is because WLLN concerns only about what the convergence point is (mean), while CLT characterizes how the sequence converges (variance). In this sense, WLLN is less informative than CLT, while requires weaker assumptions.

SLLN

• 💡 prerequisite: Borel-Cantelli Lemma

• 📎 Reference: Etemadi, N. An elementary proof of the strong law of large numbers. Z. Wahrscheinlichkeitstheorie verw Gebiete 55, 119–122 (1981) and Terance Tao: The strong law of large numbers.

Note that the almost sure convergence is equivalent to

$$\begin{array}{rl}& \mathbb{P}(\underset{n\to \infty }{\lim }{\overline{X}}_n=\mu )=1\\ ⟺& \mathbb{P}(\underset{n\to \infty }{\lim }{\overline{X}}_n\ne \mu )=0\\ ⟺& \mathbb{P}(\underset{n\to \infty }{\mathrm{limsup}}|{\overline{X}}_n-\mu |>ϵ)=0,\forall ϵ>0\\ ⟺& \mathbb{P}({\cap }_{m=1}^{\infty }{\cup }_{n=m}^{\infty }\{|{\overline{X}}_n-\mu |>ϵ\})=0,\forall ϵ>0,\end{array}$$

where in the second equivalence, we say the event is true if ${\overline{X}}_n$ does not converge. This hints us to use the Borel-Cantelli Lemma.

Before invoking the lemma, we make several reductions. First, let $X_i^{+}=\max \{X_i,0\}$ and $X_i^{-}=-\min \{X_i,0\}$. Then, if ${\overline{X}}_n^{+}:=\frac{1}{n}{\sum }_{i=1}^n\stackrel{\text{a.s.}}{\to }\mathbb{E}{X}_1^{+}$ and ${\overline{X}}_n^{-}:=\frac{1}{n}{\sum }_{i=1}^n\stackrel{\text{a.s.}}{\to }\mathbb{E}{X}_1^{-}$, by the property of Convergence under Transformations, we have

$${\overline{X}}_n={\overline{X}}_n^{+}-{\overline{X}}_n^{-}\stackrel{\text{a.s.}}{\to }\mathbb{E}{X}_1^{+}-\mathbb{E}{X}_1^{-}=\mathbb{E}{X}_1.$$

Thus, WLOG, we assume $X_i\ge 0$.

Second, instead of considering all $n$, we consider the subsequence $k_j={\alpha }^j$ for $\alpha >1$. Denote $S_n:={\sum }_{i=1}^n{X}_i$. We know $S_n$ is monotonic. Therefore, for any $n\in \mathbb{N}$, let $j$ such that $k_j\le n<k_{j+1}$, we have

$$\frac{S_n}{n}\le \frac{S_{k_{j+1}}}{n}\le \frac{S_{k_{j+1}}}{k_j}=\frac{S_{k_{j+1}}}{k_{j+1}}\cdot \alpha =\alpha {\overline{X}}_{k_{j+1}}.$$

Similarly, we have $S_n/n\ge {\alpha }^{-1}{\overline{X}}_{k_j}$. If ${\overline{X}}_{k_j}$ converges to $\mu$ almost surely, by the arbitrariness of $\alpha$, we get the desired result. Thus, we focus on the subsequence ${\overline{X}}_{k_j}$.

Third, we focus on a truncated sequence of ${\overline{X}}_{k_j}$. Let $Y_i:=X_i\mathrm{𝟙}\{X_i\le i\}$ and $S_n^{\prime }:={\sum }_{i=1}^n{Y}_i$. Then, $Y_i$ has finite second moment and we can apply Chebyshev Inequality. Importantly, the error due to truncation is negligible because of the property of Expectation:

$$\begin{array}{rl}\sum _{i=1}^{\infty }\mathbb{P}(Y_i\ne X_i)& =\sum _{i=1}^{\infty }\mathbb{P}(X_i>i)\\ & =\sum _{i=1}^{\infty }\sum _{j=i}^{\infty }\mathbb{P}(j<X_i\le j+1)\\ & =\sum _{i=1}^{\infty }i\mathbb{P}(i<X_i\le i+1)\\ & \le \sum _{i=1}^{\infty }{\int }_i^{i+1}x\mathrm{d}\mathbb{P}(x)\\ & =\mathbb{E}{X}_1<\infty .\end{array}$$

Therefore, by the Borel-Cantelli Lemma, $Y_i$ only differs from $X_i$ finitely many times almost surely. Thus, we can focus on the truncated sequence $Y_i$.

Finally, we apply Chebyshev Inequality and Borel-Cantelli Lemma to the truncated subsequence:

$$\begin{array}{rl}& \sum _{j=1}^{\infty }\mathbb{P}\left(\left|\frac{S_{k_j}^{\prime }-\mathbb{E}{S}_{k_j}^{\prime }}{k_j}\right|>ϵ\right)\\ \le & \sum _{j=1}^{\infty }\frac{\mathrm{Var}(S_{k_j}^{\prime })}{k_j^2{ϵ}^2}\\ \le & \sum _{j=1}^{\infty }\frac{{\sum }_{i=1}^{k_j}\mathrm{Var}(Y_i)}{k_j^2{ϵ}^2}\\ =& \sum _{i=1}^{k_1}\mathrm{Var}(Y_i)\cdot \frac{1}{k_1^2{ϵ}^2}\frac{1}{1-{\alpha }^{-2}}+\sum _{i=k_1+1}^{k_2}\mathrm{Var}(Y_i)\cdot \frac{1}{k_2^2{ϵ}^2}\frac{1}{1-{\alpha }^{-2}}+\cdots \\ \le & \frac{1}{{ϵ}^2(1-{\alpha }^{-2})}\left(\sum _{i=1}^{k_1}\frac{\mathrm{Var}(Y_i)}{i^2}+\sum _{i=k_1+1}^{k_2}\frac{\mathrm{Var}(Y_i)}{i^2}+\cdots \right)\\ =& \frac{1}{{ϵ}^2(1-{\alpha }^{-2})}\sum _{i=1}^{\infty }\frac{\mathrm{Var}(Y_i)}{i^2}\\ \le & \frac{1}{{ϵ}^2(1-{\alpha }^{-2})}\sum _{i=1}^{\infty }\frac{\mathbb{E}{Y}_i^2}{i^2}\\ =& \frac{1}{{ϵ}^2(1-{\alpha }^{-2})}\sum _{i=1}^{\infty }{i}^{-2}{\int }_{x=0}^i{x}^2\mathrm{d}\mathbb{P}(x)\\ =& \frac{1}{{ϵ}^2(1-{\alpha }^{-2})}\sum _{i=1}^{\infty }{i}^{-2}\sum _{j=0}^{i-1}{\int }_j^{j+1}{x}^2\mathrm{d}\mathbb{P}(x)\\ =& \frac{1}{{ϵ}^2(1-{\alpha }^{-2})}\sum _{i=1}^{\infty }\left(\sum _{j=i}^{\infty }{j}^{-2}\right){\int }_{i-1}^i{x}^2\mathrm{d}\mathbb{P}(x)\\ \le & \frac{1}{{ϵ}^2(1-{\alpha }^{-2})}\sum _{i=1}^{\infty }\frac{2}{i}{\int }_{i-1}^i{x}^2\mathrm{d}\mathbb{P}(x)\\ \le & \frac{2}{{ϵ}^2(1-{\alpha }^{-2})}\sum _{i=1}^{\infty }{\int }_{i-1}^{i}x\mathrm{d}\mathbb{P}(x)\\ =& \frac{2}{{ϵ}^2(1-{\alpha }^{-2})}\mathbb{E}{X}_1<\infty .\end{array}\text{\hspace{1em}(1)(2)(3)(4)(5)(6)}$$

See Details for the derivation of $(1)$-$(7)$. Thus, by the Borel-Cantelli Lemma,

$$\mathbb{P}\left(\underset{j\to \infty }{\mathrm{limsup}}\left|\frac{S_{k_j}^{\prime }-\mathbb{E}{S}_{k_j}^{\prime }}{k_j}\right|>ϵ\right)=\mathbb{P}\left(\bigcap _{i=1}^{\infty }\bigcup _{j=i}^{\infty }\left\{\left|\frac{S_{l_j}^{\prime }-\mathbb{E}{S}_{k_j}^{\prime }}{k_j}\right|>ϵ\right\}\right)=0,\forall ϵ>0.$$

Finally, we claim that

$$\underset{j\to \infty }{\lim }\frac{\mathbb{E}{S}_{k_j}^{\prime }}{k_j}=\mathbb{E}{X}_1=\mu .\text{\hspace{1em}(7)}$$

Thus, $S_{k_j}^{\prime }/k_j\stackrel{\text{a.s.}}{\to }\mu$. Unrolling the reductions we made gives the desired result:

$${\overline{X}}_n\stackrel{\text{a.s.}}{\to }\mu .$$

Details

1. By Chebyshev Inequality.
2. By the independence of $Y_i$, inherited from $X_i$.
3. By the definition of $k_j$ and geometric series.
4. Central moment is smaller than the raw moment.
5. By the truncation of $Y_i$.
6. Note that ${\sum }_{j=1}^{\infty }{j}^{-2}={\pi }^2/6\le 2$ and for $i\ge 2$:

$$\sum _{j=i}^{\infty }\frac{1}{j^2}\le \sum _{j=i}^{\infty }\frac{1}{j(j-1)}=\sum _{j=i}^{\infty }\frac{1}{j-1}-\frac{1}{j}=\frac{1}{i-1}\le \frac{2}{i}.$$

7. First we have

$$\mathbb{E}{X}_1=\underset{i\to \infty }{\lim }{\int }_0^{i}x\mathrm{d}\mathbb{P}(x)=\underset{i\to \infty }{\lim }\mathbb{E}{Y}_i.$$

Thus, for any $ϵ>0$, there exists $i_0\in \mathbb{N}$ such that for all $i\ge i_0$, $\mathbb{E}{X}_1-\mathbb{E}{Y}_i\le ϵ$. Then, for all $i\ge i_0$, we have

$$\mathbb{E}{X}_1-\frac{\mathbb{E}{S}_i^{\prime }}{i}\le \mathbb{E}{X}_1-\frac{{\sum }_{j=i_0}^i{\mathbb{E}}_{Y_j}}{i}\le \frac{i_0}{i}\mu +\frac{i-i_0}{i}ϵ,$$

which gives

$$\underset{i\to \infty }{\lim }\mathbb{E}{X}_1-\frac{\mathbb{E}{S}_i^{\prime }}{i}\le ϵ.$$

By the arbitrariness of $ϵ$, we conclude ${\lim }_{i\to \infty }\mathbb{E}{S}_i^{\prime }/i=\mu$.