Law of Large Numbers

Convergence of Sequences

Convergence in Distribution

A sequence $X_1,X_2,\dots$ of real-valued random variables with CDF $F_1,F_2,\dots$ is said to converge in distribution, or converge weakly, or converge in law to a random variable $X$ with CDF $F$ if

$$\underset{n\to \infty }{\lim }{F}_n(x)=F(x)$$

for every number $x\in \mathbb{R}$ at which $F$ is continuous. We denote this as

$$X_n\stackrel{d}{\to }X\text{or}{X}_n\stackrel{\mathcal{D}}{\to }X$$

Convergence in Probability

A sequence $\left\{X_n\right\}$ of random variables converges in probability towards the random variable $X$ if for all $\epsilon >0$

$$\underset{n\to \infty }{\lim }P(\left|X_n-X\right|>\epsilon )=0$$

This could be denoted by

$$X_n\stackrel{p}{\to }X$$

Almost Everywhere

To say that the sequence $X_n$ converges almost surely or almost everywhere or with probability 1 or strongly towards $X$ means that

$$P\left(\underset{n\to \infty }{\lim }{X}_n=X\right)=1$$

This means that the values of $X_n$ approach the value of $X$, in the sense that events for which $X_n$ does not converge to $X$ have probability $0$, this can be denoted as

$$X_n\stackrel{a.s.}{\to }X\text{or}{X}_n\stackrel{a.e.}{\to }X$$

Convergence in Mean

Given a real number $r\ge 1$, we say that the sequence $X_n$ converges in the $r$-th mean towards the random variate $X$, if

$$\underset{n\to \infty }{\lim }\mathrm{E}\left[{\left|X_n-X\right|}^r\right]=0$$

Convergence in $r$-th mean tells us that the expectation of the $r$-th power of the difference between $X_n$ and $X$ converges to zero. This can be denoted as

$$X_n\stackrel{L^r}{\to }X$$

Relationship

$$\begin{array}{cccccc}\stackrel{L^s}{\to }& \underset{s\ge r\ge 1}{\Rightarrow }& \stackrel{L^r}{\to }& & & \\ & & \Downarrow & & & \\ \stackrel{a.s.}{⟶}& \Rightarrow & \stackrel{p}{\to }& & \Rightarrow & \stackrel{d}{⟶}\end{array}$$

2. For continuous function $g(x)$ and $\text{type}\in \left\{a.s.,p,d\right\}$, $X_n\stackrel{\text{type}}{\to }X⟹g(X_n)\stackrel{\text{type}}{\to }g(X)$
3. (Slustky's Theorem) If $c$ is a constant and $X_n\stackrel{d}{\to }X,Y_n\stackrel{p}{\to }c$, then
   1. $X_n+Y_n\stackrel{d}{\to }X+c$
   2. $X_n{Y}_n\stackrel{d}{\to }cX$
   3. $X_n/Y_n\stackrel{d}{\to }X/c,\text{if}c\ne 0$

Law of Large Numbers

Weak Law

Given a collection of i.i.d. samples from a random variable with finite mean, the sample mean converges in probability to the expected value, that is

$${\overline{X}}_n\stackrel{p}{\to }\mu ,n\to \infty$$

Strong Law

Given a collection of

1. i.i.d. samples
2. with finite mean
3. with finite variance Then the samples mean converges almost everywhere to the expected value, that is

$${\overline{X}}_n\stackrel{a.s}{\to }\mu ,n\to \infty$$

Chebyshev Inequality

If the expectation and the variance of a r.v. $X$ all exist, then for $\forall \epsilon >0$ we have

$$P\left(\left|X-\mathrm{E}[X]\right|\ge \epsilon \right)\le \frac{\mathrm{Var}(X)}{{\epsilon }^2}$$

With Chebyshev inequality, the condition of the weak law of large numbers can be rewritten as

$$\frac{1}{n^2}\mathrm{Var}\left(\sum _{i=1}^n{X}_i\right)\to 0,n\to 0$$

Therefore, if $X_1,\dots ,X_n$ are independent and bounded in variance, we have

$$\frac{1}{n^2}\mathrm{Var}\left(\sum _{i=1}^n{X}_i\right)\le \frac{1}{n^2}\sum _{i=1}^{n}M=\frac{M}{n}\to 0,n\to \infty$$

where $M$ is the bound of the variances. Now in this case we have proved

$$\frac{1}{n}\sum _{i=1}^n\left(X_i-\mathrm{E}[X_i]\right)\stackrel{P}{\to }0,n\to \infty$$

which is known as Chebyshev's Law of Large Numbers

Khinchin's Law of Large Numbers

If $X_1,\dots ,X_n$ i.i.d and their expectations exist, then

$$\frac{1}{n}\sum _{i=1}^n\left(X_i-\mathrm{E}[X_i]\right)\stackrel{P}{\to }0,n\to \infty$$