Borel-Cantelli Lemma

Many interesting theorem in probability utilizes measure theory, as it often provides some form of one-line argument that allows the proof to go through. Among one of them is the law of large numbers, which informally states that the average of iid samples approaches the mean of the distribution as the sample size grows large.

We would like to be more precise about what the words "approaches" mean. Clearly we cannot replace the word "approaches" with "converges to", as one could be unlucky and consistently draw below or above the mean so that the sample average may never even be close to the true mean. Despite of this, one thing that we do know is that consistently drawing below or above the mean, while not impossible, becomes increasingly unlikely as the sample grows large. This naturally leads to the idea of convergence in probability.

Convergence in probability

A sequence of random variables ${\textstyle X_{n}}$ converges in probability to ${\textstyle X}$ if for any ${\textstyle \epsilon >0}$,

$$\lim _{n\to \infty }\mathbb {P} (|X_{n}-X|>\epsilon )=0.$$

Notice that this is simply convergence in measure in probability space. Equipped with this definition, we can now state the weak law of large numbers: the sample average converges in probability to the mean. Bernoulli first proved this theorem for Bernoulli random variables in 1713, when tools like Chebyshev's inequality wasn't discovered. Later on, mathmaticians proved more general cases that does not the require the assumption of finite variance or iid random variables.

Proof. Without loss of generality assume that the random variables are centered, and let ${\overline {X}}_{n}$ denote the sample average. By Chebyshev's inequality, $P(|{\overline {X}}_{n}|>\epsilon )\leq {\frac {\sigma ^{2}}{n\epsilon }}\to 0$ as $n$ approaches infinity. Note that for Chebyshev's inequality to hold we need finite variance.

It is natural to wonder the possibility of obtaining a stronger notion of convergence, perhaps under stronger condition than finite variance. To do so we need to formally define the stronger type of convergence that we need, which in study of probability we often refer to as "almost sure convergence".

Almost sure convergence

A sequence of random variables ${\textstyle X_{n}}$ converges almost surely to ${\textstyle X}$ if

$$\mathbb {P} (\lim _{n\to \infty }X_{n}=X)=1.$$

Note that this is the almost everywhere convergence in probability space, which is a stronger version of convergence. This is due to the fact that in a finite measure space, convergence almost everywhere implies convergence in measure.

The strong law of large number carries this stronger notion of converges and states: the sample average converges almost surely to the mean. Before the proof, we first introduce a lemma.

Borel Catelli Lemma

Let ${\textstyle (\Omega ,B,\mathbb {P} )}$ be a probability space, and ${\textstyle \{E_{n}\}}$ any sequence of events in ${\textstyle B}$. If ${\textstyle \sum _{i=i}^{\infty }\mathbb {P} (E_{i})<\infty }$, then ${\textstyle \mathbb {P} (\cap _{n=1}^{\infty }\cup _{k\geq n}E_{k})=0}$.

On the other hand, if ${\textstyle \sum _{i=1}^{\infty }\mathbb {P} (E_{i})=\infty }$, then ${\textstyle \mathbb {P} (\cap _{n=1}^{\infty }\cup _{k\geq n}E_{k})=1}$.

Proof.

Fix ${\textstyle \epsilon >0}$, there exists ${\textstyle n}$ sufficiently large such that ${\textstyle \sum _{i=n}^{\infty }\mathbb {P} (E_{i})<\epsilon }$. By union bound we obtain ${\textstyle \mathbb {P} (\cup _{k\geq n}E_{k})<\epsilon }$. So ${\textstyle \lim _{n\to \infty }\mathbb {P} (\cup _{k\geq n}E_{k})=0}$. By continuity of measure , we have ${\textstyle \mathbb {P} (\cap _{n=1}^{\infty }\cup _{k\geq n}E_{k})=\lim _{n\to \infty }\mathbb {P} (\cup _{k\geq n}E_{k})=0}$.

The other statement follows easily from the similar technique.

Strong law of large numbers

Instead of directly stating the theorem, we explore a little bit on our own as to what assumptions we might need in order to achieve this "almost sure convergence" to the mean. Here, we are interested in the set where ${\overline {X}}_{n}$ converges to $\mu$, and we can rewrite this set as $\{x:\cap _{k}\cup _{n}\cap _{m\geq n}|{\overline {X}}_{m}|<{\frac {1}{k}}\}$. To relate it to Borel-Cantelli lemma, we instead study its complement $\{x:\cup _{k}\cap _{n}\cup _{m\geq n}|{\overline {X}}_{m}|\geq {\frac {1}{k}}\}$. By continuity of measure, we have $P(\{x:\cup _{k}\cap _{n}\cup _{m\geq n}|{\overline {X}}_{m}|\geq {\frac {1}{k}}\})=\lim _{k\to \infty }P\{x:\cap _{n}\cup _{m\geq n}|{\overline {X}}_{m}|\geq {\frac {1}{k}}\}$.

It suffices to show that for any fixed ${\textstyle k}$, ${\textstyle P(\cap _{n}\cup _{k\geq n}|{\overline {X}}_{n}|>{\frac {1}{k}})=0}$. This closely resembles the conclusion of the Borel-Cantelli lemma, so we might be tempted to show that ${\textstyle \sum _{n=1}^{\infty }P(|{\overline {X}}_{n}|>{\frac {1}{k}})<\infty }$. Unfortunately, a simple application of Chebyshev's inequality reveals that this fall short, as

$$\sum _{n=1}^{\infty }P(|{\overline {X}}_{n}|>{\frac {1}{k}})\leq \sum _{n=1}^{\infty }{\frac {k^{2}\sigma ^{2}}{n}}=\infty .$$

Therefore, stronger assumptions must be made if we are to use the same proof technique. It is a fact that the finiteness of higher moments implies that of the the lower ones. Assuming finite fourth moment, we get

$${\begin{aligned}\mathbb {P} (|{\overline {X}}_{n}|>{\frac {1}{k}})&\leq k^{4}\mathbb {E} (|{\overline {X}}_{n}|^{4})\\&=k^{4}{\frac {n\mathbb {E} (X_{i}^{4})+3n(n-1)\mathbb {E} (X_{i}^{2})}{n^{4}}}\\&=k^{4}O({\frac {1}{n^{2}}})\\&\to 0.\end{aligned}}$$

Then by Borel-Cantelli lemma, ${\textstyle {\overline {X}}_{n}}$ converges a.s to ${\textstyle \mu }$.