The Second Borel-Cantelli Lemma

From Divergent Probabilities to Repeated Occurrence

A sequence of events can have probabilities whose sum is infinite even though that fact alone does not guarantee that the events keep occurring. Independence supplies the missing condition: it lets us calculate the probability that none of a finite group of events occurs. When the sum of probabilities diverges, these probabilities of repeated nonoccurrence shrink to zero. The result is an almost-sure statement, not merely a claim that repeated occurrence is likely.

Work on a probability space \((\Omega,\mathcal{F},\mathbb{P})\), and let \((A_n)_{n\ge1}\) be events in \(\mathcal{F}\). The events occur infinitely often if, for every integer \(m\ge1\), at least one \(A_n\) occurs for some \(n\ge m\). The event of infinitely many occurrences is written

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

Its complement is the event that only finitely many \(A_n\) occur: there is some index after which none occur. “Almost surely” means that the event in question has probability \(1\).

Theorem (Second Borel-Cantelli Lemma): If the events \(A_1,A_2,\ldots\) are independent and \(\sum_{n=1}^{\infty}\mathbb{P}(A_n)=\infty\), then \(\mathbb{P}(\limsup_{n\to\infty}A_n)=1\). Independence here means that for every finite set of distinct indices \(n_1,\ldots,n_r\), the probability of the intersection of the corresponding events, or of their complements, factors into the product of the individual probabilities.

Proof. Fix an integer \(m\ge1\). For each \(N\ge m\), let \(B_{m,N}=\bigcap_{n=m}^{N}A_n^c\), the event that none of \(A_m,\ldots,A_N\) occurs. By independence,

\mathbb{P}(B_{m,N}) =\prod_{n=m}^{N}\mathbb{P}(A_n^c) =\prod_{n=m}^{N}\bigl(1-\mathbb{P}(A_n)\bigr).

For every \(x\ge0\), \(1-x\le e^{-x}\): the function \(e^{-x}-(1-x)\) is zero at \(x=0\) and has derivative \(1-e^{-x}\ge0\) for \(x\ge0\). Since each probability lies in \([0,1]\), applying this inequality to each factor gives

0\le\mathbb{P}(B_{m,N}) \le \exp\!\left(-\sum_{n=m}^{N}\mathbb{P}(A_n)\right).

The series of probabilities diverges, so every tail sum \(\sum_{n=m}^{\infty}\mathbb{P}(A_n)\) diverges too: removing finitely many finite terms cannot make the sum finite. Thus the right-hand side tends to zero as \(N\to\infty\). The events \(B_{m,N}\) decrease as \(N\) increases, and their intersection is \(\bigcap_{n=m}^{\infty}A_n^c\), the event that no \(A_n\) occurs from index \(m\) onward. By continuity of probability for a decreasing sequence of events, its probability is the limit of \(\mathbb{P}(B_{m,N})\), hence is zero. Finally, the event that only finitely many \(A_n\) occur is \(\bigcup_{m=1}^{\infty}\bigcap_{n=m}^{\infty}A_n^c\). This is a countable union of probability-zero events, so it has probability zero. Its complement, \(\limsup_{n\to\infty}A_n\), therefore has probability \(1\). \(\square\)

The proof depends on independence at the finite-product step. The divergence condition makes that product small; independence is what permits the product calculation. In particular, the conclusion is stronger than saying that the expected number of occurrences is infinite: it says that, outside an event of probability zero, there is no last occurrence.

Worked Example: Harmonic Success Probabilities

Let \((X_n)_{n\ge2}\) be independent indicator random variables on a probability space, with \(\mathbb{P}(X_n=1)=1/n\) and \(\mathbb{P}(X_n=0)=1-1/n\). Set \(A_n=\{X_n=1\}\). Each probability is valid because \(n\ge2\) implies \(0<1/n\le1/2\). We show directly that successes occur infinitely often almost surely.

First verify divergence by grouping indices into blocks \(2^k\le n\le2^{k+1}-1\), for integers \(k\ge1\). There are \(2^{k+1}-1-2^k+1=2^k\) indices in the block. For every such \(n\), \(1/n\ge1/(2^{k+1}-1)\). Therefore the sum over that block satisfies

\sum_{n=2^k}^{2^{k+1}-1}\frac1n \ge \frac{2^k}{2^{k+1}-1} > \frac12,

where the strict inequality follows from \(2^{k+1}-1<2\cdot2^k\). There are infinitely many disjoint blocks, each contributing more than \(1/2\), so \(\sum_{n=2}^{\infty}1/n=\infty\). Since the events are independent, the second Borel-Cantelli lemma gives \(\mathbb{P}(X_n=1\text{ infinitely often})=1\).

As a finite-block check, independence also gives the probability of no success from \(2^k\) through \(2^{k+1}-1\) as

\prod_{n=2^k}^{2^{k+1}-1}\left(1-\frac1n\right) = \prod_{n=2^k}^{2^{k+1}-1}\frac{n-1}{n} = \frac{2^k-1}{2^{k+1}-1}.

The product telescopes because each numerator \(n-1\) cancels the preceding denominator. The block success probability is consequently \(1-(2^k-1)/(2^{k+1}-1)=2^k/(2^{k+1}-1)\), agreeing with the block-sum lower bound above. The lemma establishes infinitely many successes across the whole sequence, not a claim that every individual block must contain a success.

Worked Example: Reciprocal-Square-Root Success Probabilities

Let \((Y_n)_{n\ge1}\) be independent indicators with \(\mathbb{P}(Y_n=1)=1/\sqrt{n+1}\), and put \(C_n=\{Y_n=1\}\). The probabilities are in \((0,1)\), since \(n+1\ge2\). To check divergence, use the disjoint blocks \(2^k\le n\le2^{k+1}-1\), for \(k\ge0\). Each block has \(2^k\) indices, and throughout it \(n+1\le2^{k+1}\). Hence

\sum_{n=2^k}^{2^{k+1}-1}\frac1{\sqrt{n+1}} \ge \frac{2^k}{\sqrt{2^{k+1}}} = 2^{(k-1)/2}.

In particular, each block sum is at least \(1/\sqrt{2}\), because \(k\ge0\) implies \(2^{(k-1)/2}\ge2^{-1/2}=1/\sqrt{2}\). Infinitely many disjoint blocks each contribute at least this positive amount, so \(\sum_{n=1}^{\infty}\mathbb{P}(C_n)=\infty\). The events \(C_n\) are independent; therefore \(\mathbb{P}(Y_n=1\text{ infinitely often})=1\).

This application uses only the indicator events and their probabilities. It does not assert convergence of averages such as \(n^{-1}\sum_{j=1}^nY_j\); that is a different question from whether successes occur infinitely many times.

Independent Indicator Sequences

An indicator random variable takes values \(0\) and \(1\). For a sequence \((X_n)_{n\ge1}\) of independent indicators, write \(p_n=\mathbb{P}(X_n=1)\) and \(A_n=\{X_n=1\}\). Then the second Borel-Cantelli lemma gives a practical criterion: if \(\sum_n p_n=\infty\), then \(X_n=1\) infinitely often almost surely. If instead \(\sum_n p_n<\infty\), the first Borel-Cantelli lemma gives that \(X_n=1\) only finitely often almost surely; that first lemma does not require independence and is a standard result of the earlier material on the first Borel-Cantelli lemma. Together, for independent indicators, these statements characterize whether there are infinitely many successes almost surely by whether the probability sum diverges.

Worked Example: A Constant Success Probability

Let \((Z_n)_{n\ge1}\) be independent indicators with \(\mathbb{P}(Z_n=1)=1/2\), and define \(D_n=\{Z_n=1\}\). Each \(D_n\) has probability \(1/2\), so the partial sum through \(N\) is \(\sum_{n=1}^{N}\mathbb{P}(D_n)=N/2\), which tends to infinity. The second Borel-Cantelli lemma therefore gives infinitely many successes almost surely.

The finite calculation illustrates the mechanism. For fixed \(m\ge1\) and \(N\ge m\), independence yields

\mathbb{P}(Z_m=0,\ldots,Z_N=0) = \prod_{n=m}^{N}\mathbb{P}(Z_n=0) = \prod_{n=m}^{N}\frac12 = \left(\frac12\right)^{N-m+1}.

For example, from \(m=3\) through \(N=6\), there are \(6-3+1=4\) trials, and the probability of no success is \((1/2)^4=1/16\). For any fixed \(m\), the general expression tends to zero as \(N\) increases. Thus the probability of no successes at all from \(m\) onward is zero; taking the union over all possible starting indices \(m\) shows that the probability of only finitely many successes is zero.

Why Independence Matters

A divergent sum alone cannot guarantee infinitely many occurrences. For a concrete example, let \(B\) be a single event with \(\mathbb{P}(B)=1/2\), and set \(A_n=B\) for every \(n\ge1\). Then \(\mathbb{P}(A_n)=1/2\), so \(\sum_n\mathbb{P}(A_n)=\infty\). But the events are not independent: for distinct \(i,j\), \(\mathbb{P}(A_i\cap A_j)=\mathbb{P}(B)=1/2\), whereas independence would require \(\mathbb{P}(A_i)\mathbb{P}(A_j)=1/4\). Here \(\limsup_n A_n=B\), so the probability of infinitely many occurrences is \(1/2\), not \(1\).

Common mistake. It is incorrect to treat the sum of event probabilities as the probability that at least one event occurs, or to infer infinitely many occurrences from divergence without checking dependence. In the repeated-event example, the incorrect calculation would say that \(\sum_n\mathbb{P}(A_n)=\infty\), therefore \(\mathbb{P}(\limsup A_n)=1\). The actual calculation is \(\limsup A_n=B\), with probability \(1/2\). The correction is to check the theorem’s independence hypothesis before using the divergent-sum conclusion. When independence holds, the proof uses products of nonoccurrence probabilities; without it, those products need not equal the probabilities of intersections.

The distinction is useful in applications involving repeated trials, where independent indicators often arise naturally, and in settings where events share a common source of randomness. In either case, first identify the events and calculate their probabilities; then check independence and the sum condition separately. A divergent sum verifies only one of the theorem’s two hypotheses.

Check Your Understanding

For each question, distinguish the probability-sum condition from the independence condition.

State the second Borel-Cantelli lemma, including its hypotheses and conclusion.
For independent indicators with success probabilities \(p_n=1/(n+2)\), explain how grouping indices into dyadic blocks can establish that \(\sum_n p_n\) diverges.
If independent indicators have success probabilities \(p_n=2^{-n}\), what does the first Borel-Cantelli lemma say about the number of successes?
For the events \(A_n=B\) where \(\mathbb{P}(B)=1/3\) for every \(n\), compute \(\mathbb{P}(\limsup_n A_n)\) and explain why the second Borel-Cantelli lemma does not apply.
In the theorem’s proof, where exactly is independence used, and why does divergence force the probability of no occurrences after a fixed index to be zero?

The Second Borel-Cantelli Lemma

What You'll Learn