Borel-Cantelli Lemma

The study of modern probability is built on the foundation of measure theory. One of its most basic and key results, the strong law of large numbers, demonstrates the usefulness and power of this foundation. Informally, this law states that the sample mean gets close to the true mean as sample size grows large.

We would like to be more precise about the meaning of the phrase "get close to". Certainly we cannot replace it by "converges to", as one could be unlucky and consistently draw below or above the mean so that the sample mean is no where near the true mean. However, just by intuition we know that consistently drawing below or above the mean, while not impossible, becomes increasingly unlikely as the sample size grows. 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 shows that this fall short, as we get

$$\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. Since finiteness of higher moments implies that of the the lower ones, it is natural for us to assume finite fourth moment, which gives us

$${\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 }$.