# The Borel-Cantelli Lemma

Today we're chatting about the

**Borel-Cantelli Lemma**: Let $(X,\Sigma,\mu)$ be a measure space with $\mu(X)< \infty$ and suppose $\{E_n\}_{n=1}^\infty \subset\Sigma$ is a collection of measurable sets such that $\displaystyle{\sum_{n=1}^\infty \mu(E_n)< \infty}$. Then

$$\mu\left(\bigcap_{n=1}^\infty \bigcup_{k=n}^\infty E_k \right)=0.$$

When I first came across this lemma, I struggled to understand what it meant "in English." *What does $\mu\left(\bigcap_{n=1}^\infty \bigcup_{k=n}^\infty E_k \right)=0$ really signify??* There's a pretty simple explanation if $(X,\Sigma,\mu)$ is a probability space, but how are we to understand the result in the context of general measure spaces?

A first step towards answering this question is to recognize that $\mu\left(\bigcap_{n=1}^\infty \bigcup_{k=n}^\infty E_k \right)=0$ is the same as saying if $A=\{x\in X : \text{there exists infinitely many $n$ such that $x\in E_n$}\}$ then $\mu(A)=0$. And *this *is equivalent to the statement that *almost every $x\in X$ lives in at most finitely many $E_n$.*

So in other words, for almost every $x\in X$, there is some finite indexing set $A_x=\{n_1,\ldots,n_m\}\subset\mathbb{N}$ such that $$x\in\bigcap_{i\in A_x} E_i,$$ which is to say that for almost each $x\in X$, we have a picture like this:

To make things a little more concrete, let's look at an example to see the Borel-Cantelli Lemma in action.

## Example

Suppose $(X,\Sigma,\mu)$ is a measure space with $\mu(X)< \infty$ and suppose $\{f_n:X\to\mathbb{C}\}$ is a sequence of measurable functions. Show there exists a sequence $\{c_n\}$ of positive numbers such that $\displaystyle\lim_{n\to\infty} c_nf_n(x)=0$ for almost every $x\in X$.

##### Train of Thought: Our goal for the proof is to make $|c_nf_n(x)|\leq\frac{1}{n}$ for $n$ large enough and for a.e. $x\in X$, for then we can bound it above by $\epsilon$ for any $\epsilon>0$. So we ask ourselves, "Is there a set (of positive measure) of $x\in X$ where $|f_n(x)|\leq k_n$ for some positive constant $k_n$?" If so, then we can write $$|c_nf_n(x)|\leq c_nk_n \overset{\text{want}}{=}1/n.$$

The last equality is what we want, and this behooves us to choose $c_n=1/nk_n$. But does such a $k_n$ even exist? The answer is yes (!), and this is where Borel-Cantelli comes in.

## Proof

We start by claiming that for $n$ large enough, there is $k_n\in\mathbb{R}$ such that $$\mu(\{x\in X:|f_n(x)|>k_n\})< \frac{1}{2^n}.$$ Indeed notice that for a fixed $n$, the sets $E_k=\{x\in X:|f_n(x)|>k\}$ for $k=1,2,3,\ldots$ satisfy $E_1\supset E_2\supset E_3\supset\cdots$. Further we have $$\bigcap_{k=1}^\infty E_k=\varnothing $$ since the $f_n$ map into $\mathbb{C}$ (i.e. there is no $x\in X$ nor $n\in\mathbb{N}$ for which $f_n(x)=\infty$). Thus, since $\mu(E_i)<\mu(X)<\infty$, we may use continuity from above to conclude $$0=\mu(\varnothing)=\mu\left(\bigcap_{k=1}^\infty E_k\right)=\lim_{k\to\infty}\mu(E_k).$$ Hence there is a $k=k_n$ large enough so that $$E_n=\{x\in X:|f_n(x)|>k_n\} \qquad \text{satisfies} \qquad \mu(E_n)< \frac{1}{2^n}.$$

Now consider the collection $\{E_n\}_{n=1}^\infty$ and notice that $\displaystyle{\sum_{n=1}^\infty \mu(E_n)=1<\infty}$. Thus by the Borel-Cantelli Lemma, almost every $x\in X$ lives in at most finitely many $E_n$. In other words, fix $x\in X$ (off of a set of measure zero). Then there is an finite indexing set $A_x=\{n_1,\ldots,n_m\}\subset\mathbb{N}$ (with, say, $n_i< n_{i+1}$) such that $$x\in\bigcap_{i=\in A_x}E_i=E_{n_m}$$ where the equality holds since the $E_i$ are nested. Since $x\in E_{n_m}$ but $x\not\in E_n$ for any $n>n_m$, it follows that $|f_n(x)|\leq k_n$ for all $n>n_m$. This prompts us to choose

$$c_n=\frac{1}{nk_n}.$$ Indeed fix $\epsilon >0$. Then for all $n>\text{max}\{n_m,\frac{1}{\epsilon}\}$, we have $$|c_nf_n(x)|< \frac{1}{nk_n}\cdot k_n=\frac{1}{n}< \epsilon$$ which implies $c_nf_n\to 0$ almost everywhere in $X$.