Tutorials › Measure Theory › The First Borel-Cantelli Lemma

Home  /  Tutorials  /  Expectation, Conditional Expectation and Independence

Expectation, Conditional Expectation and Independence · Tutorial 749 of 798

The First Borel-Cantelli Lemma

Learn to use summable probability bounds to control infinitely many events and to prove almost-sure convergence without assuming independence.

Advanced 10 min read

What You'll Learn

  • Define the limsup of a sequence of events as the event that they occur infinitely often.
  • Prove that summable event probabilities imply a null limsup.
  • Apply the lemma without any independence assumption.
  • Use Markov's inequality and the lemma to prove almost-sure convergence.
  • Distinguish the lemma's conclusion from what can be inferred when the probability sum diverges.

Infinitely Many Events

Suppose \((A_n)\) is a sequence of events. Knowing that each \(A_n\) has small probability does not by itself rule out their occurrence; the relevant question is whether the events occur infinitely often. The First Borel-Cantelli Lemma gives a direct answer when the probabilities have a finite sum. Its useful feature is that it requires no independence or other relationship among the events.

Throughout, \((\Omega,\mathcal{F},\mathbb{P})\) is a probability space, so \(\mathbb{P}(\Omega)=1\), and each \(A_n\) is in \(\mathcal{F}\). For \(N\ge1\), the event that at least one \(A_n\) occurs for \(n\ge N\) is \(\bigcup_{n=N}^{\infty}A_n\). The event that this happens for every \(N\)—equivalently, that infinitely many of the \(A_n\) occur—is

$$ \limsup_{n\to\infty}A_n =\bigcap_{N=1}^{\infty}\bigcup_{n=N}^{\infty}A_n. $$

This event is measurable because \(\mathcal{F}\) is a sigma-algebra. We will use countable subadditivity of the measure \(\mathbb{P}\): for events \(E_n\), \(\mathbb{P}(\bigcup_n E_n)\le\sum_n\mathbb{P}(E_n)\). This follows by replacing \(E_n\) with the disjoint events \(E_n\setminus\bigcup_{j<n}E_j\), which have the same union and probabilities no greater than \(\mathbb{P}(E_n)\).

The First Borel-Cantelli Lemma

Theorem (First Borel-Cantelli Lemma): Let \((\Omega,\mathcal{F},\mathbb{P})\) be a probability space and \((A_n)\) a sequence of events in \(\mathcal{F}\). If \(\sum_{n=1}^{\infty}\mathbb{P}(A_n)<\infty\), then \(\mathbb{P}(\limsup_{n\to\infty}A_n)=0\). No independence assumption is required.

Proof. Write \(L=\limsup_{n\to\infty}A_n\). For every \(N\), the definition gives \(L\subseteq\bigcup_{n=N}^{\infty}A_n\). Monotonicity of probability and countable subadditivity therefore give

$$ 0\le\mathbb{P}(L) \le\mathbb{P}\left(\bigcup_{n=N}^{\infty}A_n\right) \le\sum_{n=N}^{\infty}\mathbb{P}(A_n). $$

The series of probabilities is finite, so its tails tend to zero: for every \(\varepsilon>0\), some \(N\) satisfies \(\sum_{n=N}^{\infty}\mathbb{P}(A_n)<\varepsilon\). The displayed inequalities then imply \(0\le\mathbb{P}(L)<\varepsilon\) for every \(\varepsilon>0\). Hence \(\mathbb{P}(L)=0\). \(\square\)

The proof uses only the probability of a union as an upper bound by the sum of its members’ probabilities. It does not need the events to be disjoint, independent, or weakly dependent. In particular, the conclusion is that almost surely only finitely many \(A_n\) occur; it does not say that no \(A_n\) occurs.

Worked Example: Nested Events with Summable Probabilities

On \(\Omega=[0,1]\) with its Borel sigma-algebra and Lebesgue probability measure, let \(A_n=[0,2^{-n}]\) for \(n\ge1\). Find the probability that infinitely many \(A_n\) occur.

Each interval includes both endpoints, and its probability is its length: \(\mathbb{P}(A_n)=2^{-n}-0=2^{-n}\). Thus

$$ \sum_{n=1}^{\infty}\mathbb{P}(A_n) =\sum_{n=1}^{\infty}2^{-n} =\frac{1/2}{1-1/2}=1. $$

The hypotheses of the First Borel-Cantelli Lemma hold, so the probability of infinitely many occurrences is zero. We can also identify the limsup directly. The intervals decrease with \(n\), so \(\bigcup_{n=N}^{\infty}A_n=[0,2^{-N}]\). Their intersection over \(N\) is \(\{0\}\): the point \(0\) is in every interval, while any \(x>0\) is excluded once \(2^{-N}<x\). Since \(\mathbb{P}(\{0\})=0\), this direct calculation agrees with the lemma.

Check: At \(n=1\), the interval length is \(2^{-1}=1/2\); at \(n=2\), it is \(2^{-2}=1/4\). Their probabilities follow the same geometric series, whose sum is \(1\), while the limsup is the single null point \(\{0\}\).

From Summable Tails to Almost-Sure Convergence

A common use of the lemma is to turn a sequence of probability bounds into an almost-sure statement about random variables. Let \(X_n\) and \(X\) be real-valued measurable random variables on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). For a fixed positive tolerance \(1/k\), the event \(\{|X_n-X|>1/k\}\) records a deviation larger than that tolerance. The following criterion uses countably many such tolerances.

Corollary: If, for every integer \(k\ge1\), \(\sum_{n=1}^{\infty}\mathbb{P}(|X_n-X|>1/k)<\infty\), then \(X_n\to X\) \(\mathbb{P}\)-almost everywhere.

Proof. For each \(k\ge1\), set \(B_{n,k}=\{|X_n-X|>1/k\}\), which is an event because the random variables are measurable. By the First Borel-Cantelli Lemma, \(\mathbb{P}(\limsup_n B_{n,k})=0\). The countable union \(Z=\bigcup_{k=1}^{\infty}\limsup_n B_{n,k}\) has probability zero by countable subadditivity. If \(\omega\notin Z\), then for every \(k\), \(\omega\notin\limsup_n B_{n,k}\). Thus there is an index \(N_k(\omega)\) such that \(|X_n(\omega)-X(\omega)|\le1/k\) for every \(n\ge N_k(\omega)\). Given any \(\eta>0\), choose \(k\) with \(1/k<\eta\). For every \(n\ge N_k(\omega)\), \(|X_n(\omega)-X(\omega)|\le1/k<\eta\), which is the definition of convergence to \(X(\omega)\). Therefore \(X_n\to X\) outside the null set \(Z\). \(\square\)

Worked Example: Markov Bounds Give Almost-Sure Convergence

On \(\Omega=[0,1]\) with Lebesgue probability measure, define the nonnegative measurable random variables \(X_n=2^n\chi_{[0,4^{-n}]}\), for \(n\ge1\). Show that \(X_n\to0\) almost everywhere using the First Borel-Cantelli Lemma and Markov's inequality.

The integral of an indicator is the measure of its set, so the expectation is

$$ \mathbb{E}[X_n] =2^n\mathbb{P}([0,4^{-n}]) =2^n4^{-n} =2^{-n}. $$

For any nonnegative integrable random variable \(Y\) and \(t>0\), Markov's inequality states \(\mathbb{P}(Y>t)\le\mathbb{E}[Y]/t\). Each \(X_n\) is nonnegative and integrable by the calculation above. Fix \(k\ge1\), use \(Y=X_n\) and \(t=1/k>0\), and obtain

$$ \mathbb{P}(X_n>1/k)\le k2^{-n}, \qquad \sum_{n=1}^{\infty}\mathbb{P}(X_n>1/k) \le k\sum_{n=1}^{\infty}2^{-n} =k\cdot1=k<\infty. $$

The corollary therefore gives \(X_n\to0\) almost everywhere. The event probabilities can also be checked exactly: since \(2^n>1/k\) for all \(n\ge1\) and \(k\ge1\), \(\{X_n>1/k\}=[0,4^{-n}]\), whose probability is \(4^{-n}\). Their sum is \(\frac{1/4}{1-1/4}=1/3\), so it is finite for each \(k\). As a direct check of the conclusion, every \(\omega>0\) is eventually larger than \(4^{-n}\), so \(X_n(\omega)=0\) eventually; at \(\omega=0\), \(X_n(0)=2^n\), but the singleton \(\{0\}\) has probability zero.

Check: For \(n=1\), \(\mathbb{E}[X_1]=2\cdot(1/4)=1/2=2^{-1}\). For \(n=2\), \(\mathbb{E}[X_2]=4\cdot(1/16)=1/4=2^{-2}\). The exact tail-event probabilities are \(1/4\) and \(1/16\), respectively, consistent with the geometric sum \(1/3\).

What Summability Does—and Does Not—Say

The lemma is a one-way implication. A finite sum of event probabilities guarantees a null event of infinitely many occurrences. If the sum diverges, the lemma gives no conclusion by itself. The events may occur infinitely often with probability zero, with probability strictly between zero and one, or with probability one; additional structure is needed to decide. In particular, divergence alone is not a converse to the lemma.

Worked Example: Divergence Gives No Conclusion by Itself

On \(\Omega=[0,1]\) with Lebesgue probability measure, let \(A_n=[0,1/3]\) for every \(n\ge1\). The interval includes its endpoints, and each event has probability \(1/3\). Hence for every \(N\), \(\sum_{n=1}^{N}\mathbb{P}(A_n)=N/3\), which tends to infinity. Nevertheless, every point in \([0,1/3]\) belongs to every \(A_n\), and every point outside that interval belongs to none. Thus \(\limsup_n A_n=[0,1/3]\) and \(\mathbb{P}(\limsup_n A_n)=1/3\), not zero.

These repeated events are dependent: \(\mathbb{P}(A_1\cap A_2)=1/3\), whereas \(\mathbb{P}(A_1)\mathbb{P}(A_2)=(1/3)(1/3)=1/9\). This example illustrates both why divergence does not settle the question and why the First Borel-Cantelli Lemma needs no independence for its summable-probability conclusion.

Common pitfall: confusing the limsup probability with the sum of the event probabilities. In the repeated-event example, the incorrect calculation \(\mathbb{P}(\limsup_n A_n)=\sum_n\mathbb{P}(A_n)=\infty\) cannot be right: a probability is at most \(1\). The sum counts repeated occurrences in a way that is not the probability of their limsup. The valid general estimate is instead \(\mathbb{P}(\limsup_n A_n)\le\sum_{n=N}^{\infty}\mathbb{P}(A_n)\) for each \(N\); when the series is finite, its tails shrink to zero and force the limsup probability to vanish.

Check Your Understanding

For each question, identify the event or probability bound to which the lemma applies, and state whether independence is needed.

  1. On \([0,1]\) with Lebesgue probability measure, let \(A_n=[0,3^{-n}]\). Compute \(\sum_n\mathbb{P}(A_n)\) and identify \(\limsup_n A_n\).
  2. Suppose \(\mathbb{P}(A_n)\le 5\cdot2^{-n}\) on a probability space. What does the First Borel-Cantelli Lemma imply about \(\limsup_n A_n\)?
  3. For real-valued measurable \(X_n,X\), explain why summability of \(\mathbb{P}(|X_n-X|>1/k)\) for every integer \(k\ge1\) implies almost-everywhere convergence.
  4. Give a sequence of events with divergent sum of probabilities for which the limsup has probability \(1\). Does divergence alone guarantee that answer?
  5. Which step in the proof of the First Borel-Cantelli Lemma would fail if the probabilities \(\mathbb{P}(A_n)\) had a divergent sum?

Previous

Next

Back to Tutorials