Law of Large Numbers

The Law of Large Numbers states that the sample mean converges to the population expectation as the sample size increases. Given $X_1,X_2,\dots ,X_n$ are i.i.d. random variables,

$${\bar{X}}_n=\frac{1}{n}\sum _{i=1}^n{X}_i\stackrel{n\to \infty }{\to }\mathbb{E}[X_i],$$

where ${\bar{X}}_n$ is the sample mean of $X_1,X_2,\dots ,X_n$.

According to the different convergence types, the Law of Large Numbers can be divided into weak law of large numbers (convergence in probability) and strong law of large numbers (almost sure convergence).

1. Mean Square LLN

Before introducing the weak and strong LLN, first consider convergence in mean square, i.e. $\frac{1}{n}{\sum }_{i=1}^n{X}_i\stackrel{m.s.}{\to }\mathbb{E}[X_i]$:

$$\begin{array}{rl}\mathbb{E}{\left|\frac{1}{n}\sum _{i=1}^n{X}_i-\mathbb{E}[X_i]\right|}^2& =\frac{1}{n^2}\mathbb{E}{\left|\sum _{i=1}^n{X}_i-n\mathbb{E}[X_i]\right|}^2\\ & =\frac{1}{n^2}\mathbb{E}\left[{\left(\sum _{i=1}^n{X}_i-n\mathbb{E}[X_i]\right)}^2\right]\\ & =\frac{1}{n^2}\sum _{i=1}^n\mathbb{E}\left[(X_i-\mathbb{E}[X_i]{)}^2\right]\\ & +\frac{2}{n^2}\sum _{i\ne j}\mathbb{E}[(X_i-\mathbb{E}[X_i])(X_j-\mathbb{E}[X_j])]\\ & =\frac{1}{n}\mathrm{Var}[X_i].\end{array}$$

If $\mathrm{Var}[X_i]<\infty$, then $\frac{1}{n}{\sum }_{i=1}^n{X}_i\stackrel{m.s.}{\to }\mathbb{E}[X_i]$.

2. Weak Law of Large Numbers

Let $X_1,X_2,\dots ,X_n$ be i.i.d. random variables with $\mathbb{E}[X_i]=\mu$ and $\mathrm{Var}[X_i]={\sigma }^2<\infty$. Denote ${\bar{X}}_n=\frac{1}{n}{\sum }_{i=1}^n{X}_i$. Then, for any $ϵ>0$,

$$\underset{n\to \infty }{\lim }\mathbb{P}(|{\bar{X}}_n-\mu |<ϵ)=1.$$

Lemma (Chebyshev inequality). For all $ϵ>0$,

$$\mathbb{P}(|X|\ge ϵ)\le \frac{\mathbb{E}[X^2]}{{ϵ}^2}.$$

Proof of Chebyshev inequality

$$\mathbb{E}|X{|}^2={\int }_{\{|X|\ge ϵ\}\cup \{|X|<ϵ\}}|x{|}^2{f}_X(x)dx\ge {\int }_{|X|\ge ϵ}{x}^2{f}_X(x)dx\ge {\int }_{|X|\ge ϵ}{ϵ}^2{f}_X(x)dx={ϵ}^2\mathbb{P}(|X|\ge ϵ).$$

Furthermore,

$$\mathbb{P}(|X-\mathbb{E}[X]|\ge ϵ)\le \frac{\mathrm{Var}[X]}{{ϵ}^2}.$$

$\square$

Proof of weak LLN

From Chebyshev inequality,

$$\begin{array}{rl}\mathbb{P}(|{\bar{X}}_n-\mu |\ge ϵ)& \le \frac{\mathrm{Var}[{\bar{X}}_n]}{{ϵ}^2}\\ & =\frac{1}{n^2{ϵ}^2}\mathrm{Var}\left[\sum _{i=1}^n{X}_i\right]\\ & \stackrel{n\to \infty }{\to }0.\end{array}$$

$\square$

Theorem (Bernoulli Weak LLN). Let $S_n=X_1+X_2+\dots +X_n$ be the count of successes in $n$ Bernoulli trials with success probability $p$. Then

$$\underset{n\to \infty }{\lim }\mathbb{P}\left(\left|\frac{S_n}{n}-p\right|<ϵ\right)=1.$$

Bernoulli Weak LLN gives a mathematical proof of the intuition that the sample proportion of successes converges to the true probability of success. In short, frequency converges to probability.

Example (Monte Carlo simulation for integration I). Consider a function $0\le f(x)\le 1$ and suppose we want to calculate $J={\int }_0^{1}f(x)dx$. We can generate uniformly random variables in region $[0,1]\times [0,1]$ and calculate the proportion of points that fall under the curve $f(x)$, i.e. $\frac{S_n}{n}$. Theoretically, the probability of falling under the curve is $\mathbf{p}=\mathbb{P}(Y\le f(X))=J$. Then, by Bernoulli Weak LLN, $\frac{S_n}{n}\stackrel{p}{\to }\mathbf{p}=J$.

More generally, if $x\in [a,b]$ and $f(x)\in [c,d]$, we can transform the region to $[0,1]\times [0,1]$ by

$$u=\frac{x-a}{b-a},g(u)=\frac{f(a+u(b-a))-c}{d-c},$$

and calculate the integral by

$${\int }_a^{b}f(x)dx=(b-a)(d-c){\int }_0^{1}g(u)du+c(b-a).$$

Note: Assumptions for weak LLN

The proof of weak LLN does not actually need the assumption of i.i.d. random variables, especially the identical distribution part. Using Chebyshev inequality, we only need the assumption of finite variance.

• Chebyshev Weak LLN. $X_1,X_2,\dots ,X_n$ are independent random variables with $\mathbb{E}[X_i]={\mu }_i$. Also, the variance of all $X_i$ exists, with common upper bound $c$, i.e. $\mathrm{Var}[X_i]\le c$. Then ${\bar{X}}_n=\frac{1}{n}{\sum }_{i=1}^n{X}_i\stackrel{p}{\to }\frac{1}{n}{\sum }_{i=1}^n{\mu }_i$.
• Markov Weak LLN. As long as for $X_1,X_2,\dots ,X_n$, $\frac{1}{n^2}\mathrm{Var}({\sum }_{i=1}^n{X}_i)\to 0$, then ${\bar{X}}_n=\frac{1}{n}{\sum }_{i=1}^n{X}_i\stackrel{p}{\to }\frac{1}{n}{\sum }_{i=1}^n\mathbb{E}[X_i]$.

Markov Weak LLN is a more general form of weak LLN, which does not require any assumption of i.i.d. random variables.

Theorem (Khintchine Weak LLN). $X_1,X_2,\dots ,X_n$ are i.i.d. random variables with $\mathbb{E}[X_i]=\mu$. Then

$${\bar{X}}_n=\frac{1}{n}\sum _{i=1}^n{X}_i\stackrel{p}{\to }\mu .$$

Corollary (Moments under Khintchine Weak LLN). If $\{X_i\}$ are i.i.d. and $\mathbb{E}|X_i{|}^k<\infty$ for $k\in \mathbb{N}$, then

$$\frac{1}{n}\sum _{i=1}^n{X}_i^k\stackrel{p}{\to }\mathbb{E}[X_i^k].$$

The proof of Khintchine Weak LLN is based on the lemma that $F_{X_n}(x)\stackrel{w}{\to }{F}_X(x)\iff {\phi }_{X_n}(t)\to {\phi }_X(t)$, where ${\phi }_X(t)$ is the characteristic function of $X$.

Proof sketch of Khintchine Weak LLN

Denote $Y=\frac{1}{n}{\sum }_{i=1}^n{X}_i$, then ${\phi }_Y(t)=[{\phi }_X(t/n){]}^n$.

By Taylor expansion,

$${\phi }_{X_i/n}(t)={\phi }_X(t/n)=1+{\phi }_X^{\prime }(0)\frac{t}{n}+o\left(\frac{1}{n}\right),$$

where ${\phi }_X^{\prime }(0)=i\mathbb{E}[X]$.

Thus,

$${\phi }_Y(t)={\left[1+i\mathbb{E}[X]\frac{t}{n}+o\left(\frac{1}{n}\right)\right]}^n\to e^{it\mathbb{E}[X]},$$

which is the characteristic function of $\mathbb{P}(X=\mathbb{E}[X])=1$, i.e. $Y\stackrel{L}{\to }\mathbb{E}[X]$. By the lemma, $Y\stackrel{p}{\to }\mathbb{E}[X]$.

$\square$

Chebyshev Weak LLN and Markov Weak LLN are more general forms of weak LLN by loosening the assumption of i.i.d. random variables and keeping the assumption of finite variance. Khintchine Weak LLN requires i.i.d. and finite expectation, but no assumption on variance.

Example (Monte Carlo simulation for integration II). Consider the integral $J={\int }_a^{b}f(x)dx$. Let $X\sim \mathcal{U}(0,1)$, then

$$\mathbb{E}[f(X)]={\int }_0^{1}f(x)dx=J.$$

Thus, we can use Monte Carlo simulation to estimate the integral by estimating $\mathbb{E}[f(X)]$. By Khintchine Weak LLN,

$$J\approx \frac{1}{n}\sum _{i=1}^{n}f(X_i).$$

Similar transformation can be applied to the case where $[a,b]$ is not $[0,1]$.

3. Strong Law of Large Numbers

Let $X_1,X_2,\dots ,X_n$ be i.i.d. random variables with $\mathbb{E}[X_i]=\mu$ and $\mathrm{Var}[X_i]={\sigma }^2<\infty$. Denote ${\bar{X}}_n=\frac{1}{n}{\sum }_{i=1}^n{X}_i$. Then, for any $ϵ>0$,

$$\mathbb{P}\left(\underset{n\to \infty }{\lim }|{\bar{X}}_n-\mu |<ϵ\right)=1.$$

Proof sketch of strong LLN

If $\{{\bar{X}}_n\}$ converges to $\mu$ almost surely, it is equivalent to say that $\mathbb{P}\left({\lim }_{n\to \infty }|{\bar{X}}_n-\mu |\ge ϵ\right)=0$ for any $ϵ>0$. Thus, we can prove SLLN by showing the set that makes the sequence diverge is of measure zero.

Denote all such $\{{\bar{X}}_k\}$ that diverge as

$$A_{\delta }=\bigcap _{n=1}^{\infty }\bigcup _{k=n}^{\infty }\{\omega :|{\bar{X}}_k(\omega )-\mu |>\delta \}.$$

Clearly the probability of $A_{\delta }$ has upper bound if we remove ${\cap }_{n=1}^{\infty }$:

$$\begin{array}{rl}\mathbb{P}(A_{\delta })& \le \mathbb{P}\left(\bigcup _{k=n}^{\infty }\{\omega :|{\bar{X}}_k(\omega )-\mu |>\delta \}\right)\\ & \le \sum _{k=n}^{\infty }\mathbb{P}\left(|{\bar{X}}_k-\mu |>\delta \right)\\ & \le 2\sum _{k=n}^{\infty }{c}_k,0<c_k<1.\end{array}$$

The last inequality is shown in Statistical Inference, Casella, 2nd ed., Chapter 5. If we acknowledge the last inequality, then $\mathbb{P}(A_{\delta })\le 2{\sum }_{k=n}^{\infty }{c}_k=2\frac{c_n}{1-c}\stackrel{n\to \infty }{\to }0$. Thus, $\mathbb{P}(A_{\delta })=0$ for any $\delta >0$, which means $\{{\bar{X}}_n\}$ converges to $\mu$ almost surely.

$\square$

Related Notes

• Delta Method