Chapter 7 Limit theorems
7.4 Borel-Cantelli
Here we must consider an infinite list of events. As a baseline example consider all possible infinite sequences of coin flips. For each \(n\), let \(A_n\) be the event that the \(n^{th}\) coin flip is heads, \(A_n=\{\text{heads on } n^{th} \text{ flip}\}\). If the coin is a fair coin, we know that a typical sequence of infinitely-many coin flips will have infinitely-many heads (and infinitely-many tails). We state this as: “the coin flip is heads infinitely-often.” This means that the event \(A_n\) occurs for infinitely-many values of \(n\). And we write this symbolically as \(\mathsf P(A_n \text{ i.o.})\) with “i.o.” an abbreviation for “infinitely often.”
First let’s convince ourselves that the probability of having infinitely-many tails consecutively in a row is zero. Let \(A_n^c=\{n^{th}\text{ flip is tails}\}\). Then we have that \[\{\text{all tails}\}=\{1^{st}\text{ flip is tails}\}\text{ and } \{2^{nd}\text{ flip is tails}\} \text{ and } \cdots=\cap_{n=1}^\infty A_n^c.\] Now define event that the first \(M\) flips are all tails by \[D_M=\{\text{first }M\text{ flips are all tails}\}=\cap_{n=1}^M A_n^c.\] Now we have a decreasing sequence of events: \[D_1\supset D_2\supset\cdots.\] By the continuity of probability (for increasing or decreasing sequences of events) we have that \[\mathsf P(\lim_{M\to\infty} D_M)=\lim_{M\to\infty} \mathsf P(D_M).\] Since the coin is fair, we have \(\mathsf P(D_M)=\frac1{2^M}\). This shows that the limit above is indeed zero. Now we finally are guaranteed that the probability of flipping all tails is zero 9for an infinite sequence of coin flips).
Now, we can intuitively understand that \(\mathsf P(A_n \text{ i.o.})=1\). If we didn’t have infinitely-many heads, then the sequence of coin flips ends in an infinite string of tails. The axioms of probability show that an infinite string of consecutive tails has probability zero. Let \(E_n\) be the event that flip \(n\) onwards is all tails. We have that \(\mathsf P(E_n)=0\) for any \(n\) by the above work. The events are related by \[\{A_n \text{ i.o.}\}=\cap_{n=1}^\infty\{\text{not all tails from flip }n\text{ onward}\}=\cap_{n=1}^\infty E_n^c.\]
Now, \[\mathsf P(A_n \text{ i.o.})=\mathsf P(\lim_{N\to\infty}\cap_{n=1}^N E_n^c)=\lim_{N\to\infty}\mathsf P(\cap_{n=1}^N E_n^c)\] since we again have a decreasing sequence of events \[(\cap_{n=1}^1 E_n^c) \supset (\cap_{n=1}^2 E_n^c) \supset\cdots.\] Now we also have that, for any \(N\), \[\mathsf P(\cap_{n=1}^N E_n^c)=1-\mathsf P(\cup_{n=1}^N E_n)\geq1-\sum_{n=1}^N\mathsf P( E_n)=1\] since \(\mathsf P(\cup_{n=1}^N E_n)\leq\sum_{n=1}^N\mathsf P( E_n)\) by Boole’s inequality and \(\mathsf P(E_n)=0\) always.
This finally shows that \(\mathsf P(A_n \text{ i.o.})=1\). We did this the hard way, but now we give a result that answers this question more easily and more generally.
What happens if the probability of heads changes over time? In particular, what is the probability of heads decreases for each subsequent flip? The following two results show that if the probability fo heads decreases fast enough, then we eventually stop getting heads at some point with probability 1, and if the probability of heads decreases slow enough, then we still get infinitely-many heads with probability 1.
Borel-Cantelli Lemma. Let \(\{A_n\}_{n\in\mathbb N}\) be a sequence of events. If \(\sum_{n=1}^\infty\mathsf P(A_n)<\infty\), then \(\mathsf P(A_n \text{ i.o.})=0\).
Converse to Borel-Cantelli. Let \(\{A_n\}_{n\in\mathbb N}\) be a sequence of independent events. If \(\sum_{n=1}^\infty\mathsf P(A_n)=\infty\), then \(\mathsf P(A_n \text{ i.o.})=1\).
Example. Consider a coin where the probability of heads decreases at each step. Let \(\mathsf P(\text{heads on }n^{th}\text{ flip})=\frac{3^n}{4^n}\) for each \(n=1,2,\ldots\). Since \(\sum_{n=1}^\infty \frac{3^n}{4^n}=\frac34\frac{1}{1-\frac34}=3\) by the geometric series formula, we get that \(\mathsf P(\text{infinitely-many heads})=0\).
If instead, we let \(P(\text{heads on }n^{th}\text{ flip})=\frac1n\) (and assume that each coin flip is independent of all others), then we get that \(\mathsf P(\text{infinitely-many heads})=1\) by the converse to Borel-Cantelli.
This is interesting that if the probability of heads decreases (even to zero in the limit), we can still get infinitely-many heads!