Deriving WLLN with Chebyshev's Inequality

1. Formalizing the Law of Large Numbers

The WLLN is a statement about a specific kind of convergence called convergence in probability. Let's define our terms carefully.

The Setup:
Consider a sequence of i.i.d. random variables $X_1,X_2,\dots ,X_n$. Each variable has the same finite mean $E[X_i]=\mu$ and the same finite variance $\text{Var}(X_i)={\sigma }^2$.

We define the sample mean as the average of these $n$ variables:
${\bar{X}}_n=\frac{1}{n}{\sum }_{i=1}^n{X}_i$
It's crucial to remember that since each $X_i$ is a random variable, their sum is also a random variable, and therefore the sample mean ${\bar{X}}_n$ is itself a random variable. For any given experiment with $n$ trials, ${\bar{X}}_n$ will take on a specific value, but it has its own probability distribution.

The Statement (Convergence in Probability):
The Weak Law of Large Numbers states that the sample mean ${\bar{X}}_n$ converges in probability to the true mean $\mu$. Mathematically, this means that for any small, positive number $ϵ$, the probability that the sample mean deviates from the true mean by more than $ϵ$ goes to zero as the sample size $n$ approaches infinity.
${\lim }_{n\to \infty }P(|{\bar{X}}_n-\mu |\ge ϵ)=0\text{for any }ϵ>0$

To see a clear, formal statement of this, please watch the first part of the following lecture from MIT OpenCourseWare.

2. The Proof Strategy: Using Chebyshev's Inequality

Our goal is to prove that ${\lim }_{n\to \infty }P(|{\bar{X}}_n-\mu |\ge ϵ)=0$. This expression should look familiar. It's precisely the form addressed by Chebyshev's inequality, which provides an upper bound for such probabilities.

Let's recall Chebyshev's inequality for a generic random variable $Y$.

The formula is:
$P(|Y-E[Y]|\ge ϵ)\le \frac{\text{Var}(Y)}{{ϵ}^2}$

Our strategy is to apply this inequality to our random variable of interest, $Y={\bar{X}}_n$. To do this, we need to calculate its expected value, $E[{\bar{X}}_n]$, and its variance, $\text{Var}({\bar{X}}_n)$. If we can show that the right-hand side of the inequality goes to zero as $n\to \infty$, our proof will be complete.

3. Key Ingredients: Mean and Variance of the Sample Mean

Let's derive the two necessary components for our proof.

A. Expected Value of the Sample Mean

Using the linearity of expectation, which states that the expectation of a sum is the sum of expectations:
$E[{\bar{X}}_n]=E\left[\frac{1}{n}{\sum }_{i=1}^n{X}_i\right]=\frac{1}{n}{\sum }_{i=1}^{n}E[X_i]$
Since the variables are identically distributed, $E[X_i]=\mu$ for all $i$.
$E[{\bar{X}}_n]=\frac{1}{n}{\sum }_{i=1}^n\mu =\frac{1}{n}(n\mu )=\mu$
So, the expected value of the sample mean is the true mean. This makes the sample mean an unbiased estimator of the population mean, a concept we will explore in detail later.

B. Variance of the Sample Mean

For the variance, we use the property that $\text{Var}(cY)=c^2\text{Var}(Y)$ and that for independent random variables, the variance of the sum is the sum of the variances.
$\text{Var}({\bar{X}}_n)=\text{Var}\left(\frac{1}{n}{\sum }_{i=1}^n{X}_i\right)=\frac{1}{n^2}\text{Var}\left({\sum }_{i=1}^n{X}_i\right)$
Because the $X_i$ are independent:
$\text{Var}({\bar{X}}_n)=\frac{1}{n^2}{\sum }_{i=1}^n\text{Var}(X_i)$
Since they are also identically distributed, $\text{Var}(X_i)={\sigma }^2$ for all $i$.
$\text{Var}({\bar{X}}_n)=\frac{1}{n^2}{\sum }_{i=1}^n{\sigma }^2=\frac{1}{n^2}(n{\sigma }^2)=\frac{{\sigma }^2}{n}$
This is a critical result. It shows that the variance of the sample mean shrinks as the sample size $n$ increases. This is the mathematical reason why the distribution in the first plot gets tighter for larger $N$.

The following video segments walk through these two derivations clearly.

4. Completing the Derivation of the WLLN

Now we have all the pieces to assemble the proof.

1. Start with Chebyshev's inequality applied to $Y={\bar{X}}_n$:
   $P(|{\bar{X}}_n-E[{\bar{X}}_n]|\ge ϵ)\le \frac{\text{Var}({\bar{X}}_n)}{{ϵ}^2}$
2. Substitute the mean and variance we just derived ($E[{\bar{X}}_n]=\mu$ and $\text{Var}({\bar{X}}_n)=\frac{{\sigma }^2}{n}$):
   $P(|{\bar{X}}_n-\mu |\ge ϵ)\le \frac{{\sigma }^2/n}{{ϵ}^2}=\frac{{\sigma }^2}{n{ϵ}^2}$
3. Take the limit as $n\to \infty$. Since ${\sigma }^2$ and $ϵ$ are fixed positive constants, the right-hand side of the inequality approaches zero:
   ${\lim }_{n\to \infty }\frac{{\sigma }^2}{n{ϵ}^2}=0$
4. Combine with the Squeeze Theorem. We know that probability is always non-negative, so:
   $0\le P(|{\bar{X}}_n-\mu |\ge ϵ)\le \frac{{\sigma }^2}{n{ϵ}^2}$
   As $n\to \infty$, the upper bound goes to 0. Therefore, the probability itself must go to 0.
   ${\lim }_{n\to \infty }P(|{\bar{X}}_n-\mu |\ge ϵ)=0$
   This completes the proof of the Weak Law of Large Numbers.

For a rigorous, step-by-step write-up of this derivation, please study the following resource. The text format will allow you to trace each logical step at your own pace.

5. Self-Assessment

As you requested, here is an exercise to test your understanding. The Statlect page contains a solved problem that applies the WLLN to a slightly more complex scenario involving a covariance stationary sequence, which is common in time-series analysis and signal processing.

Conclusion

In this lesson, you have rigorously proven the Weak Law of Large Numbers, a cornerstone of probability and statistics.

Key Takeaways:

• The WLLN provides the theoretical justification for using the sample average to estimate the true population mean.
• The key to the proof is showing that the variance of the sample mean, $\text{Var}({\bar{X}}_n)={\sigma }^2/n$, diminishes to zero as the sample size $n$ grows.
• By applying Chebyshev's inequality to the sample mean, we can formally show that ${\bar{X}}_n$ converges in probability to $\mu$.

Preview of the Next Lesson:

The WLLN tells us that the sample mean gets close to the true mean. But it doesn't tell us how the values of the sample mean are distributed around that true mean. The Central Limit Theorem (CLT) does exactly that. In our next lesson, we will outline the proof of the CLT, which reveals the remarkable fact that the distribution of the sample mean approaches a Gaussian (normal) distribution as $n$ gets large, regardless of the underlying distribution of the individual samples. This is arguably the most important theorem in all of statistics, and it forms the basis for a vast range of data science techniques.