Borel-Cantelli Lemmas

Borel-Cantelli Lemmas.

(First Borel-Cantelli Lemma) Let $(A_n)$ be a sequence of events such that the series $\sum_n \mathbb{P}(A_n)$ converges to a finite value $L$. Then, almost surely finitely many $A_n$’s will occur.
(Second Borel-Cantelli Lemma) Let $(A_n)$ be a sequence of independent events, such that the infinite series $\sum_n \mathbb{P}(A_n)$ diverges to $\infty$. Then, almost surely, infinitely many $A_n$’s will occur.

Fix a probability space $(\Omega,\mathcal{F},\mathbb{P})$. Let $A_1, A_2, A_3, \ldots$ be an infinite sequence of events belonging to $\mathcal{F}$. We shall often be interested in finding out how many of the $A_n$’s occur.

The event $A_n$ occurs infinitely often ($A_n\hspace{2mm}i.o$) is the set of all $\omega$ that belong to infinitely many $A_n$’s.

Imagine that an infinite number of $A_n$’s occur. That is, $(\forall n)(\exists m \geq n)(\text{s.t. }A_m \text{ occurs})$. In other words:

\[\begin{align*} \{A_n \text{ infinitely often}\} = \bigcap_{n=1}^{\infty} \underbrace{\bigcup_{m\geq n} A_m}_{B_n} \tag{1} \end{align*}\]

Here, $B_n$ is the event that atleast one of $A_n,A_{n+1},\ldots$ occur. For that reason, $B_n$ is referred to as the $n$-th tail event. $\{A_n \hspace{2mm} i.o.\}$ is the intersection of all $B_n$’s, so it is the event that all the $B_n$’s occur. Therefore, no matter how far I go, no matter how big $n_0$ is, atleast one of $A_{n_0}, A_{n_0}+1,\ldots$ occurs.

Taking the complement of both sides in (1), we get the expression for the event that $A_n$ occurs finitely many times.

\[\begin{align*} \{A_n \text{ occurs finitely often}\} = \bigcup_{n_0=1}^{\infty} \bigcap_{n \geq n_0} A_n^C \end{align*}\]

It means that, there exists an $n_0$, such that each of the further $A_i$’s fail to occur.

In order to prove the Borel-Cantelli lemmas, we require the following lemma.

Limit of product series

Lemma. If $\sum_{i=1}^\infty p_i = \infty$, then $\lim \prod_{i=1}^{n}(1-p_i) = 0$.

Proof.

We know that:

Using Taylor’s series expansion of $\ln(1+x)$ about $a=0$, we have:

\[\begin{align*} \ln(1+x) &= x - \frac{f''(c)}{2!}x^2\\ &= x - \frac{1}{(1+c)^2} \cdot \frac{x^2}{2}\\ &\leq x\\ &\quad \{\text{since } \left(\frac{x}{1+c}\right)^2 \geq 0\} \end{align*}\]

So,

\[\begin{align*} \ln(1 - p_i) &\leq -p_i\\ \sum_{i=1}^{n} \ln(1 - p_i) &\leq \sum_{i=1}^{n} (-p_i)\\ \ln\left(\prod_{i=1}^{n}(1-p_i)\right) &\leq \sum_{i=1}^{n} (-p_i)\\ \prod_{i=1}^{n}(1-p_i) &\leq e^{-\sum_{i=1}^{n} p_i} \end{align*}\]

So,

\[\begin{align*} 0 \leq \prod_{i=1}^{n}(1-p_i) \leq e^{-\lim \sum_{i=1}^{n} p_i} \end{align*}\]

Now, $e^{-\lim \sum_{i=1}^{n} p_i} = 0$, so by the squeeze theorem, $\lim \prod_{i=1}^{n}(1-p_i) = 0$.

Proof of the First Borel-Cantelli Lemma

Our claim is that $\mathbb{P}\left(\bigcap_{n=1}^{\infty} B_n\right) = 0$. Observe that, $B_1 \supseteq B_2 \supseteq B_3 \supseteq \ldots$. So, $(B_n)$ is a decreasing sequence of events.

\[\begin{align*} \mathbb{P}\left(\bigcap_{n=1}^{\infty} B_n\right) &= \lim_{n \to \infty }\mathbb{P}(B_n) \\ & \quad \{ \text{Continuity of probability measure} \}\\ &= \lim_{n\to\infty} \mathbb{P}\left(\bigcup_{n=1}^{\infty}A_n\right)\\ &\leq \lim_{n\to\infty} \sum_{n=1}^{\infty} \mathbb{P}\left(A_n\right)\\ & \quad \{ \text{Union bound} \} \end{align*}\]

The infinite series $\sum_{n=1}^{\infty} \mathbb{P}\left(A_n\right)$ is convergent. The tail sum $\lim_{k \to \infty} \sum a_k$ of a convergent series $\sum a_k$ is zero. Hence,

\[\begin{align*} 0 \leq \mathbb{P}\left(\bigcap_{n=1}^{\infty} B_n\right) \leq 0 \end{align*}\]

Consequently,

\[\begin{align*} \mathbb{P}\left(\bigcap_{n=1}^{\infty} B_n\right) = 0 \end{align*}\]

Hence, $A_n$ occurs only finitely many times.

Proof of the second Borel-Cantelli Lemma

Our claim is that $\mathbb{P}\left(A_n \hspace{2mm} i.o.\right) = 1$. We must therefore prove that:

\[\begin{align*} \mathbb{P} \left(\bigcap_{m=1}^{\infty} \bigcup_{n=m}^{\infty}A_n \right) = \mathbb{P} \left(\bigcap_{m=1}^{\infty} B_m \right) = 1 \end{align*}\]

Or:

\[\begin{align*} \mathbb{P} \left(\bigcup_{n=1}^{\infty} B_n^C \right) = 0 \end{align*}\]

Since $(B_n^C)$ is an increasing sequence of events, we have:

\[\begin{align*} \mathbb{P} \left(\bigcup_{n=1}^{\infty} B_n^C\right) &= \lim \mathbb{P}(B_n^C)\\ &= \lim \mathbb{P}\left\{ \left(\bigcup_{m \geq n} A_m\right)^C \right\} \\ &= \lim \mathbb{P} \left\{\bigcap_{m \geq n} A_m^C \right\}\\ &= \lim \prod_{m=n}^{\infty} \mathbb{P} (A_m^C)\\ &= \lim \prod_{m=n}^{\infty} (1-P(A_m)) \end{align*}\]

Since $\sum_i P(A_i)$ diverges to $\infty$, $\prod_i (1-P(A_i))$ converges to zero. Consequently,

\[\begin{align*} \mathbb{P} \left(\bigcup_{n=1}^{\infty} B_n^C \right) = 0 \end{align*}\]

--- title: "Borel-Cantelli Lemmas" author: "Quasar" date: "2024-06-28" categories: [Probability Theory] image: "image.jpg" toc: true toc-depth: 3 --- ## Borel-Cantelli Lemmas *Borel-Cantelli Lemmas*. (a) *(First Borel-Cantelli Lemma)* Let $(A_n)$ be a sequence of events such that the series $\sum_n \mathbb{P}(A_n)$ converges to a finite value $L$. Then, almost surely finitely many $A_n$'s will occur. (b) *(Second Borel-Cantelli Lemma)* Let $(A_n)$ be a sequence of independent events, such that the infinite series $\sum_n \mathbb{P}(A_n)$ diverges to $\infty$. Then, almost surely, infinitely many $A_n$'s will occur. Fix a probability space $(\Omega,\mathcal{F},\mathbb{P})$. Let $A_1, A_2, A_3, \ldots$ be an infinite sequence of events belonging to $\mathcal{F}$. We shall often be interested in finding out how many of the $A_n$'s occur. The event $A_n$ occurs infinitely often ($A_n\hspace{2mm}i.o$) is the set of all $\omega$ that belong to infinitely many $A_n$'s. Imagine that an infinite number of $A_n$'s occur. That is, $(\forall n)(\exists m \geq n)(\text{s.t. }A_m \text{ occurs})$. In other words: \begin{align*} \{A_n \text{ infinitely often}\} = \bigcap_{n=1}^{\infty} \underbrace{\bigcup_{m\geq n} A_m}_{B_n} \tag{1} \end{align*} Here, $B_n$ is the event that atleast one of $A_n,A_{n+1},\ldots$ occur. For that reason, $B_n$ is referred to as the $n$-th tail event. $\{A_n \hspace{2mm} i.o.\}$ is the intersection of all $B_n$'s, so it is the event that all the $B_n$'s occur. Therefore, no matter how far I go, no matter how big $n_0$ is, atleast one of $A_{n_0}, A_{n_0}+1,\ldots$ occurs. Taking the complement of both sides in (1), we get the expression for the event that $A_n$ occurs finitely many times. \begin{align*} \{A_n \text{ occurs finitely often}\} = \bigcup_{n_0=1}^{\infty} \bigcap_{n \geq n_0} A_n^C \end{align*} It means that, there exists an $n_0$, such that each of the further $A_i$'s fail to occur. In order to prove the Borel-Cantelli lemmas, we require the following lemma. ## Limit of product series *Lemma*. If $\sum_{i=1}^\infty p_i = \infty$, then $\lim \prod_{i=1}^{n}(1-p_i) = 0$. *Proof.* We know that: Using Taylor's series expansion of $\ln(1+x)$ about $a=0$, we have: \begin{align*} \ln(1+x) &= x - \frac{f''(c)}{2!}x^2\\ &= x - \frac{1}{(1+c)^2} \cdot \frac{x^2}{2}\\ &\leq x\\ &\quad \{\text{since } \left(\frac{x}{1+c}\right)^2 \geq 0\} \end{align*} So, \begin{align*} \ln(1 - p_i) &\leq -p_i\\ \sum_{i=1}^{n} \ln(1 - p_i) &\leq \sum_{i=1}^{n} (-p_i)\\ \ln\left(\prod_{i=1}^{n}(1-p_i)\right) &\leq \sum_{i=1}^{n} (-p_i)\\ \prod_{i=1}^{n}(1-p_i) &\leq e^{-\sum_{i=1}^{n} p_i} \end{align*} So, \begin{align*} 0 \leq \prod_{i=1}^{n}(1-p_i) \leq e^{-\lim \sum_{i=1}^{n} p_i} \end{align*} Now, $e^{-\lim \sum_{i=1}^{n} p_i} = 0$, so by the squeeze theorem, $\lim \prod_{i=1}^{n}(1-p_i) = 0$. ## Proof of the First Borel-Cantelli Lemma Our claim is that $\mathbb{P}\left(\bigcap_{n=1}^{\infty} B_n\right) = 0$. Observe that, $B_1 \supseteq B_2 \supseteq B_3 \supseteq \ldots$. So, $(B_n)$ is a decreasing sequence of events. \begin{align*} \mathbb{P}\left(\bigcap_{n=1}^{\infty} B_n\right) &= \lim_{n \to \infty }\mathbb{P}(B_n) \\ & \quad \{ \text{Continuity of probability measure} \}\\ &= \lim_{n\to\infty} \mathbb{P}\left(\bigcup_{n=1}^{\infty}A_n\right)\\ &\leq \lim_{n\to\infty} \sum_{n=1}^{\infty} \mathbb{P}\left(A_n\right)\\ & \quad \{ \text{Union bound} \} \end{align*} The infinite series $\sum_{n=1}^{\infty} \mathbb{P}\left(A_n\right)$ is convergent. The tail sum $\lim_{k \to \infty} \sum a_k$ of a convergent series $\sum a_k$ is zero. Hence, \begin{align*} 0 \leq \mathbb{P}\left(\bigcap_{n=1}^{\infty} B_n\right) \leq 0 \end{align*} Consequently, \begin{align*} \mathbb{P}\left(\bigcap_{n=1}^{\infty} B_n\right) = 0 \end{align*} Hence, $A_n$ occurs only finitely many times. ## Proof of the second Borel-Cantelli Lemma Our claim is that $\mathbb{P}\left(A_n \hspace{2mm} i.o.\right) = 1$. We must therefore prove that: \begin{align*} \mathbb{P} \left(\bigcap_{m=1}^{\infty} \bigcup_{n=m}^{\infty}A_n \right) = \mathbb{P} \left(\bigcap_{m=1}^{\infty} B_m \right) = 1 \end{align*} Or: \begin{align*} \mathbb{P} \left(\bigcup_{n=1}^{\infty} B_n^C \right) = 0 \end{align*} Since $(B_n^C)$ is an increasing sequence of events, we have: \begin{align*} \mathbb{P} \left(\bigcup_{n=1}^{\infty} B_n^C\right) &= \lim \mathbb{P}(B_n^C)\\ &= \lim \mathbb{P}\left\{ \left(\bigcup_{m \geq n} A_m\right)^C \right\} \\ &= \lim \mathbb{P} \left\{\bigcap_{m \geq n} A_m^C \right\}\\ &= \lim \prod_{m=n}^{\infty} \mathbb{P} (A_m^C)\\ &= \lim \prod_{m=n}^{\infty} (1-P(A_m)) \end{align*} Since $\sum_i P(A_i)$ diverges to $\infty$, $\prod_i (1-P(A_i))$ converges to zero. Consequently, \begin{align*} \mathbb{P} \left(\bigcup_{n=1}^{\infty} B_n^C \right) = 0 \end{align*}