The Borel–Cantelli lemmas

Theorem

The Borel–Cantelli lemmas

T-131Home MU-404Threads chance

Statement

Let \((\Omega,\mathcal{F},\mathbb{P})\) be a probability space and let \((A_n)_{n\ge1}\) be a sequence of events in \(\mathcal{F}\). Define the event "infinitely many \(A_n\) occur" by \(\limsup_n A_n := \bigcap_{N=1}^{\infty}\bigcup_{n=N}^{\infty}A_n = \{\omega\in\Omega : \omega\in A_n \text{ for infinitely many } n\}\). First lemma (convergence part). If \(\sum_{n=1}^{\infty}\mathbb{P}(A_n) \lt \infty\), then \(\mathbb{P}(\limsup_n A_n)=0\). No independence hypothesis is required. Second lemma (divergence part). If, in addition, the events \((A_n)_{n\ge1}\) are mutually independent and \(\sum_{n=1}^{\infty}\mathbb{P}(A_n)=\infty\), then \(\mathbb{P}(\limsup_n A_n)=1\).

Why it matters

The Borel–Cantelli lemmas are the primary tool for turning a statement about a whole infinite sequence of events into a statement with probability exactly \(0\) or exactly \(1\) — a zero–one dichotomy that recurs throughout probability. They are the engine behind the strong law of large numbers, almost–sure convergence proofs for random series, extreme–value theory (records, longest head–runs), and the theory of recurrence/transience of Markov chains and random walks.

Their appeal is that they require almost no structure: the first lemma needs nothing beyond countable additivity, and the second needs only independence, yet together they pin down the almost–sure behaviour of \(\limsup_n A_n\) completely whenever independence holds and the borderline case \(\sum \mathbb{P}(A_n)=\infty\) versus \(\lt\infty\) is the exact threshold. This "0 or 1 with no shades in between" phenomenon is the visible face of the Kolmogorov zero–one law for tail events built from independent components.

Hypotheses

Countable additivity of \(\mathbb{P}\) and measurability of each \(A_n\) (both lemmas). Without a genuine (countably additive) probability measure the argument \(\mathbb{P}(\bigcup_{n\ge N}A_n)\le\sum_{n\ge N}\mathbb{P}(A_n)\) is simply not available; with only finite additivity one can build finitely-additive "probabilities" on \(\mathbb{N}\) where every singleton has measure \(0\) yet the whole space still has an ill-defined limiting behaviour, and the tail-triviality argument breaks down entirely. Summability \(\sum_n \mathbb{P}(A_n)\lt\infty\) (first lemma). Take \(A_n=A\) for a fixed event with \(\mathbb{P}(A)=p\in(0,1)\), constant, so \(\sum_n\mathbb{P}(A_n)=\infty\); here \(\limsup_n A_n=A\) has probability \(p\), neither \(0\) nor \(1\) — summability is exactly what is needed to force the probability down to \(0\). Independence of \((A_n)\) (second lemma), used in the pairwise/mutual sense required to multiply tail probabilities. Let \(X\) be a single fair coin toss and set \(A_n=\{X=\text{heads}\}\) for every \(n\). Then \(\sum_n\mathbb{P}(A_n)=\infty\) but \(\limsup_n A_n=\{X=\text{heads}\}\) has probability \(\tfrac12\), not \(1\): with total dependence the divergence of the series carries no information about infinitely many *distinct* occurrences. Divergence \(\sum_n\mathbb{P}(A_n)=\infty\) (second lemma). If instead \(\sum_n\mathbb{P}(A_n)\lt\infty\) the first lemma already forces \(\mathbb{P}(\limsup_n A_n)=0\), the opposite conclusion; divergence is exactly the borderline condition being tested.

Proof

Part I — convergence implies null.

\text{For } N\ge1,\quad B_N:=\bigcup_{n=N}^{\infty}A_n, \qquad \limsup_n A_n=\bigcap_{N=1}^{\infty}B_N.

Definition of \(\limsup\) of a sequence of sets: \(\omega\) belongs to infinitely many \(A_n\) iff for every \(N\) it lies in some \(A_n\) with \(n\ge N\). A

B_1\supseteq B_2\supseteq B_3\supseteq\cdots \quad\text{and}\quad \mathbb{P}(B_1)\le\sum_{n=1}^{\infty}\mathbb{P}(A_n)\lt\infty.

\((B_N)\) is decreasing because dropping the smallest index only shrinks a union; the bound on \(B_1\) is countable subadditivity of \(\mathbb{P}\) applied to \(B_1=\bigcup_n A_n\), finite by hypothesis. A

\mathbb{P}\Big(\bigcap_{N=1}^\infty B_N\Big)=\lim_{N\to\infty}\mathbb{P}(B_N).

Continuity of a probability measure from above: for a decreasing sequence of measurable sets whose first term has finite measure, \(\mathbb{P}(\bigcap_N B_N)=\lim_N \mathbb{P}(B_N)\); this is a standard consequence of countable additivity applied to the disjointification \(B_N\setminus B_{N+1}\). C

\mathbb{P}(B_N)=\mathbb{P}\Big(\bigcup_{n=N}^\infty A_n\Big)\le\sum_{n=N}^\infty \mathbb{P}(A_n).

Countable subadditivity (Boole's inequality) applied to the tail union. A

\sum_{n=1}^\infty\mathbb{P}(A_n)\lt\infty \;\Longrightarrow\; \sum_{n=N}^\infty\mathbb{P}(A_n)\xrightarrow[N\to\infty]{}0.

Tail of a convergent series of non-negative terms tends to \(0\): this is the Cauchy criterion for series convergence applied to the partial sums. B

0\le \mathbb{P}(\limsup_n A_n)=\lim_{N\to\infty}\mathbb{P}(B_N)\le\lim_{N\to\infty}\sum_{n=N}^{\infty}\mathbb{P}(A_n)=0.

Combine Steps 3–5 and the squeeze principle; hence \(\mathbb{P}(\limsup_n A_n)=0\), proving the first lemma. A

Part II — divergence plus independence implies almost sure.

\text{Fix } N. \text{ It suffices to show } \mathbb{P}\Big(\bigcap_{n=N}^{\infty}A_n^c\Big)=0.

Since \(B_N=\bigcup_{n\ge N}A_n\), its complement is \(\bigcap_{n\ge N}A_n^c\); showing this has probability \(0\) gives \(\mathbb{P}(B_N)=1\) for every \(N\). B

\forall M\ge N:\quad \mathbb{P}\Big(\bigcap_{n=N}^{M}A_n^c\Big)=\prod_{n=N}^{M}\big(1-\mathbb{P}(A_n)\big).

Mutual independence of \((A_n)\) implies the complements \((A_n^c)\) are also mutually independent, so the probability of a finite intersection factorises as a product. B

1-x\le e^{-x}\ \text{ for all } x\in\mathbb{R}, \quad\text{so}\quad \prod_{n=N}^{M}(1-\mathbb{P}(A_n))\le \exp\Big(-\sum_{n=N}^{M}\mathbb{P}(A_n)\Big).

Elementary inequality \(1-x\le e^{-x}\) (from convexity of \(e^{-x}\), or Taylor's theorem with remainder), applied termwise and using \(e^{-a}e^{-b}=e^{-(a+b)}\). Each factor lies in \([0,1]\) since \(0\le\mathbb{P}(A_n)\le1\). C

\sum_{n=1}^\infty \mathbb{P}(A_n)=\infty \;\Longrightarrow\; \sum_{n=N}^{M}\mathbb{P}(A_n)\xrightarrow[M\to\infty]{}\infty \;\Longrightarrow\; \exp\Big(-\sum_{n=N}^{M}\mathbb{P}(A_n)\Big)\xrightarrow[M\to\infty]{}0.

Divergence of a series of non-negative terms means its partial sums are unbounded; \(e^{-x}\to0\) as \(x\to\infty\) by continuity of the exponential. A

\mathbb{P}\Big(\bigcap_{n=N}^{\infty}A_n^c\Big)=\lim_{M\to\infty}\mathbb{P}\Big(\bigcap_{n=N}^{M}A_n^c\Big)=0.

Continuity from above again: \(\bigcap_{n=N}^M A_n^c\) decreases to \(\bigcap_{n=N}^\infty A_n^c\) as \(M\to\infty\), and every set involved has finite (indeed total) measure, so the limit of probabilities equals the probability of the limit; combine with Steps 8–10. B

\mathbb{P}(B_N)=1 \ \text{ for every } N \quad\Longrightarrow\quad \mathbb{P}\Big(\bigcap_{N=1}^\infty B_N\Big)=1.

Step 7 and 11 give \(\mathbb{P}(B_N)=1\) for every \(N\); the complements \(B_N^c\) each have probability \(0\), so by countable subadditivity \(\mathbb{P}\big(\bigcup_N B_N^c\big)=0\), i.e. \(\mathbb{P}\big(\bigcap_N B_N\big)=1\). Since \(\bigcap_N B_N=\limsup_n A_n\) by Step 1, this proves the second lemma. A

Result

\sum_n\mathbb{P}(A_n)\lt\infty \;\Rightarrow\; \mathbb{P}(\limsup_n A_n)=0; \qquad \Big[(A_n)\text{ independent},\ \sum_n\mathbb{P}(A_n)=\infty\Big] \;\Rightarrow\; \mathbb{P}(\limsup_n A_n)=1

Reading. If the "sizes" of the events are summable, only finitely many of them occur, almost surely. If the events are independent and their sizes are not summable, infinitely many of them occur, almost surely — the tail sum is the exact dial that decides between "eventually never" and "forever recurring".

Scope. The first lemma holds on any probability space for any sequence of measurable events, with no independence assumption. The second lemma requires mutual independence of the whole sequence \((A_n)_{n\ge1}\); pairwise independence alone is not enough (see Fails without). Together they classify \(\mathbb{P}(\limsup_n A_n)\) as exactly \(0\) or exactly \(1\) whenever independence holds, but for dependent sequences with \(\sum_n\mathbb{P}(A_n)=\infty\) the probability can be anything in \([0,1]\).

Corollaries & converses

Almost-sure finiteness of a random series' support. If \(\sum_n\mathbb{P}(A_n)\lt\infty\) then almost surely only finitely many \(A_n\) occur; equivalently \(\liminf_n A_n^c\) occurs almost surely, i.e. eventually \(A_n\) fails forever.
Kolmogorov's zero–one law consistency check. For independent \((A_n)\), \(\limsup_n A_n\) is a tail event, so Kolmogorov's law already forces \(\mathbb{P}(\limsup_n A_n)\in\{0,1\}\); Borel–Cantelli identifies *which* value it takes via the series \(\sum_n\mathbb{P}(A_n)\).
Second Borel–Cantelli–Erdős–Rényi refinement. Full mutual independence can be weakened to pairwise independence together with a variance (second-moment) bound on \(\sum_{n\le N}\mathbf{1}_{A_n}\), still giving \(\mathbb{P}(\limsup_n A_n)=1\) when \(\sum_n\mathbb{P}(A_n)=\infty\) — this is a genuinely different, harder theorem, not a restatement.
Converse of the first lemma fails. \(\mathbb{P}(\limsup_n A_n)=0\) does not imply \(\sum_n\mathbb{P}(A_n)\lt\infty\); e.g. disjoint events with \(\mathbb{P}(A_n)=1/n\) diverge in sum yet if instead one uses \(\mathbb{P}(A_n)=1/n\) with the \(A_n\) shrinking nested sets rather than independent ones, no general implication back to summability holds. A clean counterexample: on \([0,1]\) with Lebesgue measure let \(A_n=[0,1/n]\); then \(\limsup_n A_n=\{0\}\) has measure \(0\) although \(\sum_n \mathbb{P}(A_n)=\sum 1/n=\infty\).
Converse of the second lemma fails without independence — see the constant-event counterexample above; divergence of \(\sum_n\mathbb{P}(A_n)\) alone never forces \(\mathbb{P}(\limsup_n A_n)=1\).

Fails without

Drop summability in Lemma 1: let \(A_n=[0,1/n]\subset([0,1],\mathcal{B},\text{Leb})\); \(\mathbb{P}(A_n)=1/n\), \(\sum_n\mathbb{P}(A_n)=\infty\) (not summable), and indeed \(\limsup_n A_n=\bigcap_N\bigcup_{n\ge N}[0,1/n]=\{0\}\) has measure \(0\) here — showing the *implication* direction, not that summability was needed for this particular example, but the standard sharp counterexample uses independent \(A_n\): with \((A_n)\) independent, \(\mathbb{P}(A_n)=1/n\), Lemma 2 applies since \(\sum 1/n=\infty\), forcing \(\mathbb{P}(\limsup_n A_n)=1\), the opposite conclusion from Lemma 1 — demonstrating the sharp threshold role of summability.
Drop independence in Lemma 2: on a single fair coin toss \(X\), set \(A_n=\{X=\text{H}\}\) for all \(n\). Then \(\sum_n\mathbb{P}(A_n)=\infty\) but \(\limsup_n A_n=\{X=\text{H}\}\) has probability \(\tfrac12\ne1\); total dependence lets one "reuse" the same probability mass forever without ever guaranteeing infinitely many *distinct* occurrences forces the event.
Drop countable additivity: replace \(\mathbb{P}\) by a finitely additive but not countably additive set function on \((\mathbb{N},2^{\mathbb{N}})\) with \(\mathbb{P}(\{n\})=0\) for every \(n\) yet \(\mathbb{P}(\mathbb{N})=1\) (a "free ultrafilter" type charge). Both proofs use continuity from above at an essential step (Steps 3 and 11); this fails for merely finitely additive charges, and indeed \(\limsup\) statements can become vacuous or false.
Pairwise-only independence in Lemma 2 without a second-moment bound: there exist sequences of pairwise independent events with \(\sum_n\mathbb{P}(A_n)=\infty\) yet \(\mathbb{P}(\limsup_n A_n)\lt1\) (constructions based on pairwise-independent but not mutually independent random variables, e.g. via Latin-square type constructions); mutual independence in Step 8's product formula cannot be replaced by pairwise independence alone.

Common errors

Applying the second lemma to a sequence that is only pairwise, not mutually, independent — the factorisation \(\mathbb{P}(\bigcap A_n^c)=\prod(1-\mathbb{P}(A_n))\) in Step 8 genuinely requires full mutual independence of the finite collection, not just independence of each pair.
Confusing \(\limsup_n A_n\) ("infinitely many \(A_n\) occur") with \(\liminf_n A_n\) ("all but finitely many \(A_n\) occur", i.e. \(A_n\) occurs eventually forever) — these are different events and the lemmas say nothing directly about \(\liminf_n A_n\), whose probability is governed by the complementary events \(A_n^c\).
Believing the two lemmas are logical converses of one another. They are not: they have disjoint hypotheses (summable vs. divergent) and neither can be run "backwards" to deduce something about \(\sum_n\mathbb{P}(A_n)\) from a known value of \(\mathbb{P}(\limsup_n A_n)\) (see Corollaries).
Forgetting that the first lemma needs no independence at all, and hunting for an independence argument (or worse, assuming independence silently) when only summability is available and needed.
Sign/direction slip in the \(1-x\le e^{-x}\) bound of Step 9, e.g. writing \(1-x\ge e^{-x}\) and thereby "proving" the product stays bounded away from \(0\), which reverses the conclusion of Lemma 2.
Treating \(\bigcup_{n\ge N}A_n\) as though its probability were \(\sum_{n\ge N}\mathbb{P}(A_n)\) exactly (equality) rather than merely bounded above by it (Boole's inequality, Step 4) — the bound is generally strict unless the \(A_n\) are disjoint.

Discussion

Émile Borel proved the summable case in 1909 while studying normal numbers, and Francesco Paolo Cantelli supplied the general subadditivity argument shortly after; the divergence half under independence was clarified over the following two decades and is now attributed jointly to both names even though Cantelli's original 1917 note already handles much of the independent case. The pairing of the two lemmas is one of the earliest clean instances of a "zero–one law" in probability, predating Kolmogorov's general 1933 tail-event theorem, which the second lemma can be seen as a special, constructive case of: it does not merely assert the probability is \(0\) or \(1\), it tells you *which one* from the value of a single series.

The lemmas are the standard machine for proving almost-sure convergence and almost-sure limiting behaviour of sequences of random variables. For example, to show \(X_n\to0\) almost surely it is often enough to show \(\sum_n\mathbb{P}(|X_n|\gt\varepsilon)\lt\infty\) for every \(\varepsilon\gt0\) and invoke Lemma 1; this is the mechanism inside the standard proof of the strong law of large numbers via truncation and a series of independent bounded pieces. Likewise, for a simple random walk on \(\mathbb{Z}\), independence of increments and a divergent series of return probabilities via Lemma 2 is the route to proving recurrence, while a summable such series (as occurs in \(\mathbb{Z}^3\) and above) proves transience.

The sharpness of the independence hypothesis in Lemma 2 is itself a rich research topic: the Erdős–Rényi and Kochen–Stone generalisations replace independence by a second-moment (correlation) condition of the form \(\liminf_N \dfrac{\big(\sum_{n\le N}\mathbb{P}(A_n)\big)^2}{\sum_{i,j\le N}\mathbb{P}(A_i\cap A_j)} \gt 0\), which still forces \(\mathbb{P}(\limsup_n A_n)\gt0\) (and, with a further argument, \(=1\) in the ergodic/tail-trivial setting) — a genuinely more delicate statement whose proof uses the Cauchy–Schwarz inequality rather than the exponential bound used here, and lies beyond the present theorem.

Common misconception: students often think the lemmas are exhaustive, i.e. that every sequence of events falls under one or the other. They do not: a dependent sequence with \(\sum_n\mathbb{P}(A_n)=\infty\) is covered by neither lemma, and \(\mathbb{P}(\limsup_n A_n)\) can then take any value in \([0,1]\), as the constant-event counterexample shows.

Worked examples

\text{Infinite monkey / typing problem: let } X_1,X_2,\ldots \text{ be i.i.d.\ uniform on a 26-letter alphabet.}

Fix a target word \(w\) of length \(k\) (say \(k=5\)); ask whether \(w\) appears infinitely often as a length-\(k\) block starting at position \(n\) for infinitely many \(n\). A

\text{Let } A_n = \{X_{nk+1}\cdots X_{(n+1)k} = w\}, \quad n=0,1,2,\ldots \quad (\text{disjoint length-}k\text{ blocks}).

Choosing non-overlapping blocks makes \((A_n)_{n\ge0}\) mutually independent, since they depend on disjoint groups of the i.i.d.\ sequence. B

\mathbb{P}(A_n)=26^{-k} \text{ for every } n, \qquad \sum_{n=0}^{\infty}\mathbb{P}(A_n)=\sum_{n=0}^\infty 26^{-k}=\infty.

Each block is uniform over \(26^k\) equally likely strings; the series of a constant positive term diverges trivially. A

\text{Apply Lemma 2 (independent, divergent series)} \;\Longrightarrow\; \mathbb{P}(\limsup_n A_n)=1.

Direct application of the theorem's second half to the independent sequence constructed in Step 2. A

\mathbb{P}(w \text{ occurs as a block infinitely often}) = 1

Reading. Any fixed finite string, however long, appears infinitely often almost surely in an infinite i.i.d.\ random text — the "infinite monkey theorem".

\text{Let } (X_n)_{n\ge1} \text{ be i.i.d.\ standard normal. Show } \mathbb{P}(|X_n|\gt c\sqrt{\log n}\text{ i.o.})=0 \text{ for } c\gt\sqrt2.

"i.o." abbreviates "infinitely often", i.e.\ the event \(\limsup_n\{|X_n|\gt c\sqrt{\log n}\}\); this is the key growth-rate estimate behind the law of the iterated logarithm heuristics. B

\mathbb{P}(|X_n|\gt t) \le 2\cdot\frac{1}{\sqrt{2\pi}\,t}e^{-t^2/2} \quad (t\gt0).

Standard Gaussian tail (Mills ratio) bound: \(\mathbb{P}(X\gt t)\le \varphi(t)/t\) for \(X\sim N(0,1)\), \(t\gt0\), obtained by comparing \(\int_t^\infty \varphi(x)\,dx\) with \(\int_t^\infty \frac{x}{t}\varphi(x)\,dx\). C

\text{With } t=c\sqrt{\log n}:\quad \mathbb{P}(|X_n|\gt c\sqrt{\log n}) \le \frac{2}{\sqrt{2\pi}\,c\sqrt{\log n}}\, n^{-c^2/2}.

Substitute \(t^2/2 = \tfrac12 c^2\log n\), so \(e^{-t^2/2}=n^{-c^2/2}\); routine algebra from Step 2. A

c\gt\sqrt2 \;\Longrightarrow\; c^2/2\gt1 \;\Longrightarrow\; \sum_{n=2}^\infty \frac{n^{-c^2/2}}{\sqrt{\log n}} \lt \infty.

A \(p\)-series with exponent \(c^2/2\gt1\) converges (standard integral test), and the extra logarithmic factor in the denominator only helps convergence. A

\sum_n \mathbb{P}(|X_n|\gt c\sqrt{\log n}) \lt \infty \;\Longrightarrow\; \mathbb{P}(|X_n|\gt c\sqrt{\log n} \text{ i.o.}) = 0 \quad \text{by Lemma 1.}

No independence needed here — Lemma 1 applies to any sequence with a summable probability series, so it is legitimate even though the \(X_n\) happen to also be independent. A

\mathbb{P}\big(|X_n|\gt c\sqrt{\log n}\ \text{infinitely often}\big) = 0 \quad (c\gt\sqrt2)

Reading. For i.i.d.\ standard normal variables, \(|X_n|\) eventually stays below \(c\sqrt{\log n}\) forever, for any fixed \(c\gt\sqrt2\); this pins down the almost-sure growth rate of the running maximum of Gaussian noise, a first step toward the law of the iterated logarithm.

Problems

Let \((A_n)_{n\ge1}\) be events (not assumed independent) with \(\mathbb{P}(A_n)=1/n^2\). Show \(\mathbb{P}(\limsup_n A_n)=0\), and state which lemma you used and why independence was not needed.
Solution
\(\sum_{n=1}^\infty \mathbb{P}(A_n)=\sum_{n=1}^\infty 1/n^2 = \pi^2/6 \lt\infty\), a convergent \(p\)-series with \(p=2\gt1\). This is exactly the hypothesis of the first Borel–Cantelli lemma, which requires no independence — only countable subadditivity of \(\mathbb{P}\), which holds unconditionally. Hence \(\mathbb{P}(\limsup_n A_n)=0\): almost surely only finitely many \(A_n\) occur.
Let \((Y_n)_{n\ge1}\) be i.i.d.\ Bernoulli\((p)\) with \(p\in(0,1)\), and let \(A_n=\{Y_n=1\}\). Determine \(\mathbb{P}(\limsup_n A_n)\) and justify fully.
Solution
The events \((A_n)\) are mutually independent (i.i.d. sequence) with \(\mathbb{P}(A_n)=p\) constant. Since \(p\gt0\), \(\sum_n \mathbb{P}(A_n)=\sum_n p=\infty\). Both hypotheses of the second lemma (mutual independence, divergent series) hold, so \(\mathbb{P}(\limsup_n A_n)=1\): almost surely infinitely many \(Y_n\) equal \(1\), regardless of how small \(p\gt0\) is.
Construct a sequence of dependent events \((A_n)\) with \(\sum_n \mathbb{P}(A_n)=\infty\) but \(\mathbb{P}(\limsup_n A_n)=0\), showing the divergence hypothesis alone (without independence) is not enough for Lemma 2's conclusion.
Solution
Work on \(([0,1],\mathcal B,\mathrm{Leb})\). Let \(A_n = [0, 1/n]\). Then \(\mathbb{P}(A_n)=1/n\) and \(\sum_n \mathbb{P}(A_n)=\sum_n 1/n=\infty\) (harmonic series). But the \(A_n\) are nested decreasing sets, so \(\bigcup_{n\ge N}A_n = A_N=[0,1/N]\) for every \(N\), giving \(\limsup_n A_n = \bigcap_N [0,1/N] = \{0\}\), which has Lebesgue measure \(0\). So \(\mathbb{P}(\limsup_n A_n)=0\) despite \(\sum_n\mathbb{P}(A_n)=\infty\): the \(A_n\) here are maximally dependent (nested), violating the independence hypothesis of Lemma 2, and the conclusion of Lemma 2 fails.
Let \((A_n)_{n\ge1}\) be independent with \(\mathbb{P}(A_n) = \dfrac{1}{n\log n}\) for \(n\ge2\). Decide whether \(\mathbb{P}(\limsup_n A_n)\) is \(0\) or \(1\), with full justification including any integral test used.
Solution
Consider \(\sum_{n=2}^\infty \frac{1}{n\log n}\). By the integral test, compare with \(\int_2^\infty \frac{dx}{x\log x}\); substituting \(u=\log x\), \(du=dx/x\), this equals \(\int_{\log2}^\infty \frac{du}{u} = \infty\) (divergent, as \(\int du/u\) is a divergent log-integral). So \(\sum_n \mathbb{P}(A_n)=\infty\). Since the \((A_n)\) are given as independent and the series diverges, the second Borel–Cantelli lemma applies directly: \(\mathbb{P}(\limsup_n A_n)=1\).
(Harder, uses the discussion.) Let \((A_n)\) be pairwise independent (but not assumed mutually independent) events with \(\mathbb{P}(A_n)=p_n\) and \(\sum_n p_n=\infty\). Suppose additionally the Kochen–Stone/Erdős–Rényi second-moment condition \(\liminf_{N\to\infty} \dfrac{\big(\sum_{n\le N}p_n\big)^2}{\sum_{i,j\le N}\mathbb{P}(A_i\cap A_j)} = 1\) holds (as it would automatically if the \(A_n\) were in fact mutually independent, since then off-diagonal terms are \(p_ip_j\)). Explain, without reproving the Kochen–Stone theorem, why this scenario is genuinely outside the scope of the theorem proved above, and what extra tool would be needed.
Solution
The proof given above (Steps 7–12) uses mutual independence essentially once: in Step 8, to factorise \(\mathbb{P}\big(\bigcap_{n=N}^M A_n^c\big)\) as the product \(\prod_{n=N}^M(1-p_n)\). Pairwise independence alone does not license this factorisation for three or more events simultaneously (a classical fact: pairwise independence does not imply joint/mutual independence, e.g.\ via constructions based on independent fair coins where XOR relations create pairwise-but-not-mutual independence). Hence the exponential bound of Step 9 and everything downstream (Steps 10–12) is unavailable, and one cannot conclude \(\mathbb{P}(\limsup_n A_n)=1\) from the argument in this theorem. Reaching that conclusion under only pairwise independence plus a second-moment condition requires a genuinely different technique — a second-moment (Paley–Zygmund / Cauchy–Schwarz) argument applied to the partial-sum random variables \(S_N=\sum_{n\le N}\mathbf{1}_{A_n}\), which is the content of the Kochen–Stone theorem referenced in the Discussion, not a corollary of the Borel–Cantelli lemma proved here.