The First Borel-Cantelli Lemma

From Probability Bounds to Almost-Sure Statements

Convergence in probability controls the chance of a large error at one index. Almost-sure convergence makes a stronger, pathwise claim: outside a probability-zero set, the errors eventually become small and stay small. A useful way to prove such claims is to bound the probabilities of exceptional events and show that their probabilities have a finite sum.

Let \((\Omega,\mathcal{F},\mathbb{P})\) be a probability space, and let \(A_1,A_2,\ldots\) be events in \(\mathcal{F}\). The event that infinitely many of them occur is

\{A_n\ \text{infinitely often}\} =\limsup_{n\to\infty} A_n =\bigcap_{m=1}^{\infty}\bigcup_{n=m}^{\infty}A_n.

A sample point belongs to this event exactly when, no matter how far along the sequence one starts, at least one later event occurs. The first Borel–Cantelli lemma says that if the probabilities of the events have a finite sum, then the probability of infinitely many occurrences is zero. Notably, it requires no independence assumption.

Theorem (First Borel–Cantelli lemma): If \((A_n)_{n\ge1}\) is a sequence of events on a probability space and \(\sum_{n=1}^{\infty}\mathbb{P}(A_n)<\infty\), then \(\mathbb{P}(A_n\text{ infinitely often})=0\).

Proof. For each \(m\ge1\), let \(U_m=\bigcup_{n=m}^{\infty}A_n\). Countable subadditivity gives \(\mathbb{P}(U_m)\le\sum_{n=m}^{\infty}\mathbb{P}(A_n)\). The right-hand side tends to zero as \(m\) tends to infinity because the series of event probabilities converges. The events \(U_m\) decrease as \(m\) increases, and \(\bigcap_{m=1}^{\infty}U_m\) is the event that infinitely many \(A_n\) occur. By continuity of probability for a decreasing sequence of events, \(\mathbb{P}(\bigcap_m U_m)=\lim_{m\to\infty}\mathbb{P}(U_m)=0\). This continuity property follows from countable additivity: for decreasing events \(U_m\), the differences \(U_m\setminus U_{m+1}\) are disjoint, and their probabilities form the tails of a convergent series bounded by \(\mathbb{P}(U_1)\le1\). Therefore the probability of the intersection is the limit of the probabilities of the decreasing events. \(\square\)

The conclusion is sometimes stated as: with probability one, only finitely many of the events occur. “Only finitely many” does not mean “none”: a sample point may belong to several early events and still belong to only finitely many events altogether. The key estimate in the proof is a bound on the probability of any occurrence after index \(m\), not a bound on the number of occurrences.

Worked Example: Summable Events Without Independence

Take \(\Omega=[0,1]\) with its Borel sets and uniform probability, and let \(A_n=[0,2^{-n}]\) for \(n\ge1\). These events are nested, so they are not independent. Their probabilities are \(\mathbb{P}(A_n)=2^{-n}\), and the sum is

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

For any \(m\ge1\), the tail sum is \(\sum_{n=m}^{\infty}2^{-n}=2^{1-m}\), which tends to zero. The first Borel–Cantelli lemma therefore gives probability zero to infinitely many occurrences. Directly, the intersection of all the intervals is \(\{0\}\): the point \(0\) lies in every \(A_n\), while each \(\omega>0\) eventually exceeds \(2^{-n}\). Since \(\mathbb{P}(\{0\})=0\), this also verifies the conclusion for this example.

Summable Deviations Give Almost-Sure Convergence

To apply the lemma to random variables, choose events that describe deviations from a proposed limit. A countable set of error thresholds is enough: if a sequence is eventually within \(1/k\) of its limit for every positive integer \(k\), then it converges to that limit.

Theorem (Summable-deviation criterion): Let \(X,X_1,X_2,\ldots\) be real-valued random variables on the same probability space. Suppose that, for every integer \(k\ge1\), \(\sum_{n=1}^{\infty}\mathbb{P}(|X_n-X|>1/k)<\infty\). Then \(X_n\to X\) almost surely.

Proof. Fix an integer \(k\ge1\) and define \(A_n^{(k)}=\{|X_n-X|>1/k\}\). The assumed sum is finite, so the first Borel–Cantelli lemma implies that, with probability one, only finitely many \(A_n^{(k)}\) occur. Call this probability-one event \(E_k\). The intersection \(E=\bigcap_{k=1}^{\infty}E_k\) also has probability one, since its complement is the countable union of the probability-zero events \(E_k^c\). For any \(\omega\in E\) and any \(\varepsilon>0\), choose an integer \(k\) such that \(1/k<\varepsilon\). Because \(\omega\in E_k\), there is an index \(N\) after which \(|X_n(\omega)-X(\omega)|\le1/k\). Thus, for every \(n\ge N\), \(|X_n(\omega)-X(\omega)|\le1/k<\varepsilon\). This is the definition of convergence of the sample path to \(X(\omega)\), so \(X_n\to X\) almost surely. \(\square\)

The strict inequality in the deviation event matters in using the conclusion: if \(|X_n-X|>1/k\) occurs only finitely often, then eventually the non-strict bound \(|X_n-X|\le1/k\) holds. No assumption of independence among the random variables, or among the deviation events, appears in this argument.

Worked Example: Moment Bounds Yield an Almost-Sure Limit

Suppose \(X_n\) and \(X\) are real-valued random variables on a probability space and, for every \(n\ge1\), \(\mathbb{E}|X_n-X|^2\le8^{-n}\). We show that \(X_n\to X\) almost surely.

For a nonnegative random variable \(Z\) and \(a>0\), the pointwise inequality \(a\mathbf{1}_{\{Z>a\}}\le Z\) implies \(\mathbb{P}(Z>a)\le\mathbb{E}Z/a\). Apply this with \(Z=|X_n-X|^2\) and \(a=4^{-n}\). Since \(|X_n-X|>2^{-n}\) is equivalent to \(|X_n-X|^2>4^{-n}\), we obtain

\mathbb{P}(|X_n-X|>2^{-n}) \le \frac{\mathbb{E}|X_n-X|^2}{4^{-n}} \le \frac{8^{-n}}{4^{-n}} =2^{-n}.

The probabilities of these threshold events sum to at most \(\sum_{n=1}^{\infty}2^{-n}=1\). By the first Borel–Cantelli lemma, with probability one there is an index \(N\) such that \(|X_n-X|\le2^{-n}\) for every \(n\ge N\). Since \(2^{-n}\to0\), this implies \(X_n\to X\) almost surely. The calculation uses the actual moment bound at each \(n\); a finite second moment without a suitably summable bound would not establish this conclusion by this argument.

Almost-Sure Convergence from Small Increments

Sometimes no candidate limit is known in advance. A different application of the lemma starts by controlling the increments \(X_{n+1}-X_n\). If the increments are eventually bounded by a summable deterministic sequence, then each sample path is Cauchy, and completeness of the real numbers supplies its limit.

Theorem (Summable increment criterion): Let \(X_1,X_2,\ldots\) be real-valued random variables on one probability space. Suppose there are positive numbers \(a_n\) with \(\sum_{n=1}^{\infty}a_n<\infty\) and \(\sum_{n=1}^{\infty}\mathbb{P}(|X_{n+1}-X_n|>a_n)<\infty\). Then \(X_n\) converges to a finite real limit almost surely.

Proof. Apply the first Borel–Cantelli lemma to \(A_n=\{|X_{n+1}-X_n|>a_n\}\). With probability one, there is an index \(N\) such that \(|X_{n+1}-X_n|\le a_n\) for all \(n\ge N\). Fix a sample point with this property. For integers \(r>s\ge N\), the triangle inequality gives \(|X_r-X_s|\le\sum_{n=s}^{r-1}|X_{n+1}-X_n|\le\sum_{n=s}^{r-1}a_n\). Because \(\sum_n a_n\) converges, its tails tend to zero, so the last bound tends to zero as \(s\) tends to infinity, uniformly over \(r>s\). The sample path is therefore Cauchy. The real numbers are complete, so this path has a finite limit. The property holds on a probability-one event, proving almost-sure convergence. \(\square\)

Worked Example: A Sequence Built from Rare Increments

On \(\Omega=[0,1]\) with uniform probability, set \(A_n=[0,4^{-n}]\), and define \(X_1=0\) and \(X_n=\sum_{j=1}^{n-1}\mathbf{1}_{A_j}\) for \(n\ge2\). We verify almost-sure convergence using the increment criterion with \(a_n=2^{-n}\).

For each \(n\ge1\), \(X_{n+1}-X_n=\mathbf{1}_{A_n}\). Since \(2^{-n}\le1/2<1\), the strict event \(\{|X_{n+1}-X_n|>2^{-n}\}\) is exactly \(A_n\), and its probability is \(4^{-n}\). The sum is

\sum_{n=1}^{\infty}4^{-n} =\frac{4^{-1}}{1-4^{-1}} =\frac{1}{3}, \qquad \sum_{n=1}^{\infty}2^{-n} =\frac{2^{-1}}{1-2^{-1}} =1.

Both required sums are finite, so the increment criterion proves that \(X_n\) converges almost surely. There is also a direct check: the first Borel–Cantelli lemma says that only finitely many \(A_n\) occur almost surely. On each such sample path, only finitely many increments equal \(1\); all later increments are zero, so \(X_n\) is eventually constant. This confirms the convergence conclusion independently at the path level.

What a Divergent Sum Does—and Does Not—Say

The first Borel–Cantelli lemma is a sufficient condition, not a necessary one. If the probability sum diverges, this lemma gives no conclusion about infinitely many occurrences. It is incorrect to reverse the implication and claim that a divergent sum forces infinitely many events to occur. The behavior can vary with the dependence structure, and no independence hypothesis was needed for the first lemma.

Worked Example: Divergent Probabilities but No Infinite Occurrences

Take \(\Omega=(0,1)\) with uniform probability and \(A_n=(0,1/n)\) for \(n\ge1\). Each event has probability \(1/n\), and \(\sum_{n=1}^{\infty}1/n\) diverges. For every fixed \(\omega\in(0,1)\), membership in \(A_n\) requires \(n<1/\omega\), which holds for only finitely many positive integers \(n\). Thus no \(\omega\in\Omega\) belongs to infinitely many \(A_n\), and \(\mathbb{P}(A_n\text{ infinitely often})=0\), despite the divergent sum.

Common mistake. The incorrect calculation is “\(\sum_n\mathbb{P}(A_n)=\infty\), therefore \(\mathbb{P}(A_n\text{ infinitely often})=1\).” The first Borel–Cantelli lemma does not assert this converse. Its valid implication is from a finite sum to probability zero for infinitely many occurrences. In the example above, direct inspection shows that every sample point belongs to only finitely many events, so the proposed converse would give the wrong answer.

For almost-sure convergence, the practical strategy is to choose exceptional events that capture failure at a specified accuracy. Prove that their probabilities have a finite sum, apply the first Borel–Cantelli lemma, and then translate “only finitely many exceptions” into a pathwise statement. When the proposed limit is known, use deviation events; when it is not, summable increment bounds can make sample paths Cauchy.

Check Your Understanding

For each question, identify the relevant event sequence or probability bound before drawing a conclusion.

State the event that \(A_n\) occurs infinitely often using unions and intersections.
Why does the first Borel–Cantelli lemma not require independence?
If \(\mathbb{P}(|X_n-X|>1/k)\le 3^{-n}\) for every \(n\ge1\) and fixed \(k\ge1\), what is the sum of these bounds, and how does it support an almost-sure convergence argument when the condition holds for every \(k\)?
In the increment criterion, where is completeness of the real numbers used?
Give the logical error in concluding that a divergent sum of event probabilities forces infinitely many occurrences almost surely.

What You'll Learn