# Can someone explain the Borel-Cantelli Lemma?

I’m looking for an informal and intuitive explanation of the Borel-Cantelli Lemma. The symbolic version can be found here.

What is confusing me is what ‘probability of the limit superior equals $0$’ means.

Thanks!

-

Let $\{E_n\}$ be a sequence of events. Each event $E_i$ is a collection of outcomes. The limit superior of the collection $\{E_n\}$ is the collection of all those outcomes that appear in infinitely many events. The Borel Cantelli Lemma says that if the sum of the probabilities of the $\{E_n\}$ are finite, then the collection of outcomes that occur infinitely often must have probability zero.

To give an example, suppose I say that I have a favorite real number between $0$ and $1$, and I challenge my friends to guess a subset of $[0,1]$ where this number lies. Of course, I have infinitely many friends (not implausible), so they each makes a guess $E_n$. Each guess $E_n$ is a collection of numbers, which here represent the outcomes. Now, a probabilist comes along assigns to each friend the probability they were correct. Thus, if a friend chose $[0,1/2]$, they would have a $1/2$ probability of being correct, etc. Now, this probabilist adds together all these probabilities, and gets a finite number. What can he conclude? That the collection of all those numbers that infinitely many friends guessed (the lim sup) had a $0$ percent chance of being correct, so no infinite collection of friends could agree on more than a few numbers in their collection.

-
For the 0 percent chance of being correct, I don't really get it, couldn't it happen that one does happen to hit upon it? – user136503 Nov 25 '15 at 16:57
thank you for focusing on the intuition! – Diego Dec 1 '15 at 22:04

Here is a proof I wrote up for sci.math, but never posted:

Borel-Cantelli: Suppose that $\sum_{i=1}^\infty P(A_i)$ is finite, then the probability that infinitely many of the $A_i$ occur is $0$.

Proof: Let $B_k$ be the event $\cup_{i=k}^\infty A_i$ for $k=1,2,\ldots,$. If $x$ is in the event $A_i$'s i.o., then $x\in B_k$ for all $k$. So $x\in \cap_{k=1}^\infty B_k$.

Conversely, if $x\in B_k$ for all $k$, then we can show that $x$ is in $A_i$'s i.o. Indeed, $x\in B_1 = \cup_{i=1}^\infty A_i$ means that $x\in A_{j(1)}$ for some $j(1)$. However $x\in B_{j(1)+1}$ implies that $x\in A_{j(2)}$ for some $j(2)$ that is strictly larger than $j(1)$. Thus we can produce an infinite sequence of integer $j(1)< j(2)< j(3)<\ldots$ such that $x\in A_{j(i)}$ for all $i$.

Let $E$ be the event $\{x:\, x\in A_i \mbox{ i.o.}\}$. We have $$E = \bigcap_{k=1}^\infty \bigcup_{i=k}^\infty A_i\tag{1}$$ From $E\subseteq B_k$ for all $k$, it follows that $P(E)\leq P(B_k)$ for all $k$. By union bound, we know that $P(B_k)\leq \sum_{i=k}^\infty P(A_i)$. So $P(B_k)\rightarrow 0$, by the hypothesis that $\sum_{i=1}^\infty P(A_i)$ is finite. Therefore, $P(E)=0$.

For events, $\bigcap\approx\inf$ and $\bigcup\approx\sup$. Since $$\limsup_{n\to\infty}a_n=\operatorname*{\inf\vphantom{p}}_{n\ge1}\sup_{k\ge n}a_k\tag{2}$$ it makes sense to call $$\limsup_{n\to\infty}A_n=\bigcap_{n\ge1}\bigcup_{k\ge n} A_k\tag{3}$$

-
thanks for this wonderful proof!!! – under-root Mar 26 '14 at 22:04
excellent explanation! thank you! – Diego Dec 1 '15 at 22:04

In infinite probability spaces the probability of an event being $0$ does not mean it can't happen. This can be confusing, but such is life. Consider for instance flipping a fair coin infinitely many times. What is the probability that in all these flips you'll get heads? Answer: 0 (the probability of all flips heads must be less then the probability of first $n$ flips being heads, but that is equal precisely to $(1/2)^n$, so the probability of all heads is smaller then $(1/2)^n$ for all $n$, which means it's equal to $0$). It can of course but with probability $0$.

In finite probability spaces an event having probability $0$ can safely be interpreted as "can't happen". But in infinite probability spaces you need to refine your intuition.

If I understand your question correctly, this is really what you are asking about and not so much about Borel-Cantelli. Just to make one more comment then, Borel-Cantelli says that if the total sum of the probabilities of events is finite (i.e., small) then the probability for such events occurring infinitely often is $0$. It can happen, but it's bloody unlikely. For some events to occur infinitely often it must be the case that the total sum of individual probabilities is large (i.e., infinity). The Wiki page you cited gives several examples. I hope this helps.

-