A Devious Bet: The Borel-Cantelli Lemma

by

(Authors note: I tried to make this post accessible possible, however I recommend the reader to familiarize themselves with basic notations and facts in set theory and on infinite series before reading if they aren’t already)

Suppose you are offered a bet as follows, by a totally not evil and totally not a squid monster disguised as a man casino owner:

How can they possibly be a squid monster? Squids don’t have mustaches

The bet will have (countably) infinitely many steps. In each you win or lose money, the only thing the totally not a squid monster tells you is that in each step, on average, you gain money. Furthermore, that average increases as the bet goes on.

How could the bet have infinitely many steps and still take a finite amount of time? I don’t know, it’s not like the person giving you the bet has Lovecraftian squid monster powers or something.

Do you take the bet? Well let’s say you do, let’s see your bank balance:

Oh, look it’s negatively infinite. Honestly I’m surprised there hasn’t been any integer flow in the process…

So what trickery did the not squid monster use? Let’s define Xn as the profit in dollars at step n (n is a positive integer), and look at its distribution:

(X_n)_{n=1}^{\infty} \textup{ are independent random variables such that for all}\: n\in\mathbb{N} \textup{:}
\mathbb{P}(X_n=3^n)=2^{-n},\: \mathbb{P}(X_n=-1)=1-2^{-n}

So it seems you win with a low probability, which gets exponentially lower the more time passes. But on the other hand, when you win, you win A LOT, and the more you play the more you win, and what you win gets exponentially higher.

Let’s see if the not squid monster told the truth by checking the expectation (average, in other words) of Xn:

\mathbb{E}(X_n)=\mathbb{P}(X_n=3^n)\cdot(3^n)+\mathbb{P}(X_n=-1)\cdot(-1)=
2^{-n}(3^n)-(1-2^{-n})=(3/2)^n-1+2^{-n}>0

So the not a squid monster didn’t lie, the bet matched his description. Not only that, as n grows the average profit gets exponentially higher! How did you lose?

So what happened?

The key fact is that although the average profit at each step is very high and grows exponentially, you win only a finite amount of times. In particular, the amount of money you earn at those steps is finite. In all other steps, you lose 1 dollar (as the profit Xn is negative 1). Since there are infinitely many steps where you lose, you lose all the money you earned at the steps where you won, and then proceed to infinity and continue to lose money. Thus at the end, you lose an infinite amount of money.

But why do you win only finitely many times. Well, that is due to the Borel-Cantelli Lemma, which states the following (almost surely means with probability one):

\textbf{Theorem (Borel-Cantelli Lemma): }\: \textup{Let} \:(A_n)_{n=1}^\infty\: \textup{be random events such that the sum of their probabilities }\mathbb{P}(A_n)\textup{ converges}
\textup{then almost surely only finitely many of }\: A_n\: \textup{ occur.}
\textup{So in other words, if }\sum _{n=1}^\infty\mathbb{P}(A_n)<\infty, \textup{ then:}
\mathbb{P}(A_n \textup{ happens infinitely often})=\mathbb{P}(\bigcap_{n=1}^\infty\bigcup _{k=n}^\infty A_k)=0

Now we can see why. The probability of winning at step n is 2-n. The sum of those probabilities is finite and equal to one. So by the Borel-Cantelli lemma almost surely you win only finitely many times.

A Proof of the Borel-Cantelli Lemma:

Let’s see then why the Borel-Cantelli lemma holds. The proof makes use of two fundamental facts in mathematics as a whole. The first is known as the union bound and is as follows:

\textup{If }(B_n)_{n=1}^\infty \textup{ are random events for each n then } \mathbb{P}(\bigcup_{n=1}^\infty B_n)\leq\sum_{n=1}^\infty\mathbb{P}(B_n)

In other words, the probability of at least one of Bn happening is less then or equal to the sum of their probabilities. This is a pretty intuitive fact, to prove it, it helps to think first of the case where Bn are disjoint (so no two of them can happen simultaneously). The idea is that if two events intersect, their union is smaller than if they were disjoint as some of the elements in the union appear in both sets. So the probability of the union is also lower than the probability of the union if they were disjoint, which is the sum of probabilities.

The second fact is an important fact about converging series:

\textup{If }\sum_{n=1}^\infty b_k<\infty, \textup{then the sequence of 'tail sums' }\sum_{n=k}^\infty b_k \textup{ approaches zero as k goes to infinity}

This is again a pretty intuitive fact, as we expect that the more we sum, the more that remains to get to the total, the ‘tail sums’, approaches zero.

Now let’s see how this helps prove the Borel-Cantelli lemma. Note the following: if An happens infinitely often, then for each natural number k, there must be some number n after k for which An happens. Else, all occurences of An happen before k, so there are finitely many of them in contradiction with our assumption.

Therefore, for each k, we can bound the probability of An happening infinitely often as follows:

\mathbb{P}(A_n\textup{happens infinitely often}) \leq \mathbb{P}(\bigcup_{n=k}^\infty A_n)

We can use the union bound to bound the probability of An happening after k:

\mathbb{P}(\bigcup_{n=k}^\infty A_n)\leq\sum_{n=k}^\infty\mathbb{P}(A_n)

But we have on the right hand side the tail of the converging sum of P(An). So as k grows larger, the right hand side approaches zero. So our bound on An happening infinitely often approaches zero and thus we conclude the probability of An happening infinitely often is zero. In other words, almost surely An happens finitely many times. This completes the proof. Q.E.D

A Second Borel Cantelli Lemma:

The Borel-Cantelli lemma dealt with the case where the sum of probabilities converged. A natural question to ask now is what about the case where the sum diverges? It turns out there is an analog of the lemma for that case as well:

\textbf{Theorem (Borel-Cantelli Lemma 2): }\: \textup{Let } (A_n)_{n=1}^\infty \textup{ be independent random event such that the sum of their probabilities diverges.}
\textup{Then, almost surely, }A_n\textup{ occurs for infinitely many n}
\textup{So, in other words, if } \sum_{n=1}^\infty \mathbb{P}(A_n)=\infty ,\textup{then:}
\mathbb{P}(A_n \textup{ happens infinitely often})=\mathbb{P}(\bigcap_{n=1}^\infty\bigcup _{k=n}^\infty A_k)=1

(Note that this version of the lemma requires the events to be independent. To see why the lemma isn’t true otherwise, try to think of a case where after one An fails, all following An fail, and yet the sum of probabilities still converges)

A nice application of this version of the lemma is as follows. Suppose you draw a poker hand infinitely many times (resetting the deck each time), each draw independent from the others. Then the probability of drawing a royal flush at each attempt is very low, but a positive constant nevertheless (equal to 1/649,740). So the sum of probabilities of drawing a royal flush for each attempt diverges. Thus almost surely, you will draw infinitely many royal flushes.

Maybe you can try to get back on the not a squid monster for taking your money using that. By the way, why does it smell like tentacles here all of a sudden?

4 thoughts on “A Devious Bet: The Borel-Cantelli Lemma”

  1. Pingback: A blog post I made about the Borel Cantelli lemma. Feedback would be appreciated! - Nevin Manimala's Blog
  2. Pingback: Stable pairings and how to find them (Gale-Shapely algorithm and also puppies) – Almost Surely a Math Blog
  3. Pingback: A Devious Bet 2: Law of Large Numbers – Almost Surely a Math Blog

Leave a Reply to RNCancel reply