Weak Law of Large Numbers

This post aims to explain Weak Law of Large numbers. To do so, we first introduce Chebyshev Inequality, then provide the theorem and proof of the weak law of large numbers.

Chebyshev Inequality

Theorem:
Let X be a random variable with mean E[X] = \mu and variance \mathrm{Var}[X] = \sigma^2.

Then, the Chebyshev inequality states that

P(|X - \mu| \geq t) \leq \frac{\sigma^2}{t^2}, for t > 0.

Proof:
Let A denotes the event |X - \mu| \geq t, and A^{c} the complementary event (|X - \mu| < \mu )

\sigma^2 = E[(X - \mu)^2|A]P(A) + E[(X - \mu)^2|A^{c}]P(A^{c})

\sigma^2 \geq E[(X - \mu)^2|A]P(A)

since

0 \leq P(A^{c}) \leq 1 and E[(X - \mu)^2|A^{c}] \geq 0.

So, whenever A occurs, |X - \mu| \geq t, which implies (X - \mu)^{2} \geq t^{2}. Here, we can say that: E[(X - \mu)^2 | A] \geq t^{2}


finally, by using third equation, can say that, \sigma^2 \geq t^2 P(A), which alternatively means:

P(|X - \mu| \geq t) \leq \frac{\sigma^2}{t^2}

Weak Law of Large Numbers

Theorem:
Let X_1, X_2, \dots X_n be an independent trials process, with finited expected value \mu = E[X_j] and finite variance \sigma^{2} = \mathrm{Var}[X].

Let S_n = X_1 + X_2 + X_3 + \dots + X_n.

P(|\frac{S_n}{n} - \mu| \geq t) \rightarrow 0, for t > 0 as n \rightarrow \infty.

Proof:
Since X_1, X_2, \dots X_n are independent and have the same distributions, we can say that:

\mathrm{Var[S_n]} = n \sigma^2

and,

\mathrm{Var[\frac{S_n}{n}]} = \frac{\sigma^2}{n}

By Chebyshev's inequality, for any t > 0,

P(|\frac{S_n}{n} - \mu| \geq t) \leq \frac{\sigma^{2}}{nt^{2}}

Thus, for fixed t

P(|\frac{S_n}{n} - \mu| \geq t) \rightarrow 0

as n \rightarrow \infty, we can say that:

P(|\frac{S_n}{n} - \mu| < t) \rightarrow 1

Appendix

Theorem:

\mathrm{Var[\frac{S_n}{n}]} = \frac{\sigma^2}{n}

Proof: we know that

\mathrm{Var}[\frac{S_n}{n}] = \mathrm{Var}[\frac{X_1}{n}] + \mathrm{Var}[\frac{X_2}{n}] + \dots + \mathrm{Var}[\frac{X_n}{n}]

\frac{1}{n^2}(\mathrm{Var}[X_1] + \mathrm{Var}[X_2] + \dots + \mathrm{Var}[X_n])

\frac{1}{n^2} \times n \times \sigma^2 = \frac{\sigma^2}{n}

References:

1. http://www.ams.sunysb.edu/~jsbm/courses/311/cheby.pdf
2. https://www.dartmouth.edu/~chance/teaching_aids/books_articles/probability_book/Chapter8.pdf
3. https://www.dartmouth.edu/~chance/teaching_aids/books_articles/probability_book/Chapter6.pdf
4. http://textofvideo.nptel.ac.in/117104129/lec9.pdf