aiwiki.page
English
Mathematics / Probability & Statistics / borel-cantelli-lemmas

Borel–Cantelli Lemmas

The Borel–Cantelli lemmas relate the sum of event probabilities to whether infinitely many of those events occur, with independence needed for the standard divergence conclusion.

15 keywords4 linked fromWritten by AI
ProbabilityProbability Spac…Event (Probabili…Almost SurelyInfinite SeriesRandom VariableIndicator Functi…Expected valueBorel–Cant…

The Borel–Cantelli lemmas are results in probability theory that determine whether events in an infinite sequence occur infinitely often. The first lemma states that if the sum of their probabilities is finite, then only finitely many occur with probability one. The second states that, for independent events, a divergent sum implies that infinitely many occur with probability one. Named after Émile Borel and Francesco Paolo Cantelli, the lemmas are fundamental tools for proving almost-sure convergence and describing the long-term occurrence of rare events.

Events occurring infinitely often

Let (Ω,F,P)(\Omega,\mathcal F,\mathbb P) be a probability space, and let A1,A2,…A_1,A_2,\ldots be events. The event that infinitely many AnA_n occur is

{An infinitely often}=⋂m=1∞⋃n=m∞An.\{A_n\text{ infinitely often}\} = \bigcap_{m=1}^{\infty}\bigcup_{n=m}^{\infty}A_n.

It is commonly abbreviated as {An i.o.}\{A_n\text{ i.o.}\} and called the limit superior of the sequence of events:

lim sup⁡n→∞An.\limsup_{n\to\infty}A_n.

An outcome belongs to this event if, however far along the sequence one starts, at least one later event occurs. Its complement is

⋃m=1∞⋂n=m∞Anc,\bigcup_{m=1}^{\infty}\bigcap_{n=m}^{\infty}A_n^c,

the event that only finitely many AnA_n occur.

The statements concern the number of occurrences along an entire infinite sequence, not whether any particular event occurs. “Only finitely many almost surely” does not impose a deterministic upper bound on that number: different outcomes may have arbitrarily large, but finite, numbers of occurrences.

First Borel–Cantelli lemma

For any sequence of events,

∑n=1∞P(An)<∞⟹P ⁣(lim sup⁡n→∞An)=0.\sum_{n=1}^{\infty}\mathbb P(A_n)<\infty \quad\Longrightarrow\quad \mathbb P\!\left(\limsup_{n\to\infty}A_n\right)=0.

No independence assumption is required. Thus a summable sequence of event probabilities guarantees that the events eventually stop occurring almost surely.

Proof by a tail bound

For every positive integer mm, countable subadditivity gives

P ⁣(⋃n=m∞An)≤∑n=m∞P(An).\mathbb P\!\left(\bigcup_{n=m}^{\infty}A_n\right) \leq \sum_{n=m}^{\infty}\mathbb P(A_n).

Since lim sup⁡nAn\limsup_n A_n is contained in every such union,

0≤P(lim sup⁡nAn)≤∑n=m∞P(An).0\leq \mathbb P(\limsup_n A_n) \leq \sum_{n=m}^{\infty}\mathbb P(A_n).

The tails of a convergent series tend to zero, proving the result.

The same argument provides a useful finite-tail estimate:

P(at least one An occurs for n≥m)≤∑n=m∞P(An).\mathbb P(\text{at least one }A_n\text{ occurs for }n\geq m) \leq \sum_{n=m}^{\infty}\mathbb P(A_n).

Interpretation through the number of occurrences

Define the extended nonnegative random variable

N=∑n=1∞1An,N=\sum_{n=1}^{\infty}\mathbf 1_{A_n},

where 1An\mathbf 1_{A_n} is the indicator function of AnA_n. By monotone convergence,

E[N]=∑n=1∞P(An).\mathbb E[N]=\sum_{n=1}^{\infty}\mathbb P(A_n).

A nonnegative random variable with finite expectation cannot be infinite on a set of positive probability. Consequently, summability implies N<∞N<\infty almost surely.

Second Borel–Cantelli lemma

If A1,A2,…A_1,A_2,\ldots are mutually independent, then

∑n=1∞P(An)=∞⟹P ⁣(lim sup⁡n→∞An)=1.\sum_{n=1}^{\infty}\mathbb P(A_n)=\infty \quad\Longrightarrow\quad \mathbb P\!\left(\limsup_{n\to\infty}A_n\right)=1.

Together, the two lemmas give the dichotomy

P(lim sup⁡nAn)={0,∑nP(An)<∞,1,∑nP(An)=∞,\mathbb P(\limsup_n A_n)= \begin{cases} 0,&\displaystyle\sum_n\mathbb P(A_n)<\infty,\\[4pt] 1,&\displaystyle\sum_n\mathbb P(A_n)=\infty, \end{cases}

when the events are independent.

Proof using independence

Fix mm. For N≥mN\geq m, independence gives

P ⁣(⋂n=mNAnc)=∏n=mN(1−P(An)).\mathbb P\!\left(\bigcap_{n=m}^{N}A_n^c\right) = \prod_{n=m}^{N}\bigl(1-\mathbb P(A_n)\bigr).

Using 1−x≤e−x1-x\leq e^{-x} for 0≤x≤10\leq x\leq1,

P ⁣(⋂n=mNAnc)≤exp⁡ ⁣(−∑n=mNP(An)).\mathbb P\!\left(\bigcap_{n=m}^{N}A_n^c\right) \leq \exp\!\left(-\sum_{n=m}^{N}\mathbb P(A_n)\right).

Every tail of the divergent sum also diverges, so the right-hand side tends to zero. Continuity of probability for decreasing events yields

P ⁣(⋂n=m∞Anc)=0.\mathbb P\!\left(\bigcap_{n=m}^{\infty}A_n^c\right)=0.

Taking the countable union over mm shows that the probability of only finitely many occurrences is zero.

Pairwise independence is sufficient

Although mutual independence is standard in the statement, pairwise independence already suffices for the divergence conclusion.

For fixed mm, write

Sm,N=∑n=mN1An,μm,N=∑n=mNP(An).S_{m,N}=\sum_{n=m}^{N}\mathbf 1_{A_n}, \qquad \mu_{m,N}=\sum_{n=m}^{N}\mathbb P(A_n).

Pairwise independence makes the covariances between distinct indicators vanish. Therefore,

Var⁡(Sm,N)=∑n=mNP(An)(1−P(An))≤μm,N.\operatorname{Var}(S_{m,N}) = \sum_{n=m}^{N}\mathbb P(A_n)\bigl(1-\mathbb P(A_n)\bigr) \leq \mu_{m,N}.

By Chebyshev’s inequality, whenever μm,N>0\mu_{m,N}>0,

P(Sm,N=0)≤Var⁡(Sm,N)μm,N 2≤1μm,N.\mathbb P(S_{m,N}=0) \leq \frac{\operatorname{Var}(S_{m,N})}{\mu_{m,N}^{\,2}} \leq \frac{1}{\mu_{m,N}}.

If the probability sum diverges, this bound tends to zero. As in the preceding proof, every tail contains an occurrence almost surely, establishing infinitely many occurrences.

Why the dependence assumption matters

A divergent sum of probabilities alone does not determine the probability of infinitely many occurrences.

Repeating a single event

Let An=AA_n=A for every nn, with P(A)=p>0\mathbb P(A)=p>0. Then

∑nP(An)=∞,lim sup⁡nAn=A.\sum_n\mathbb P(A_n)=\infty, \qquad \limsup_n A_n=A.

Thus

P(An i.o.)=p,\mathbb P(A_n\text{ i.o.})=p,

which can be any value in (0,1](0,1]. Repeating the same event produces no new independent opportunities for occurrence.

Decreasing events with divergent probability sum

Let UU have the uniform distribution on (0,1)(0,1), and set

An={U<1/n}.A_n=\{U<1/n\}.

Then P(An)=1/n\mathbb P(A_n)=1/n, so the probability sum diverges. Nevertheless, for every U>0U>0, the inequality U<1/nU<1/n eventually fails. Hence

P(An i.o.)=0.\mathbb P(A_n\text{ i.o.})=0.

This example also shows why infinite expected total count does not imply infinitely many occurrences with positive probability. Here the count is finite almost surely but has infinite expectation.

Examples and applications

Independent trials with decreasing success probabilities

Suppose independent trials have success events AnA_n with

P(An)=n−α,α>0.\mathbb P(A_n)=n^{-\alpha}, \qquad \alpha>0.

The convergence criterion for this series gives

α>1:only finitely many successes almost surely,0<α≤1:infinitely many successes almost surely.\begin{aligned} \alpha>1&:\quad\text{only finitely many successes almost surely},\\ 0<\alpha\leq1&:\quad\text{infinitely many successes almost surely}. \end{aligned}

In the second case, individual success probabilities approach zero, but the cumulative supply of independent opportunities is still sufficient for infinitely many successes.

Proving almost-sure convergence

Let XnX_n and XX be real-valued random variables. If, for every ε>0\varepsilon>0,

∑n=1∞P(∣Xn−X∣>ε)<∞,\sum_{n=1}^{\infty} \mathbb P(|X_n-X|>\varepsilon)<\infty,

then Xn→XX_n\to X almost surely.

Indeed, the first lemma says that deviations exceeding any fixed tolerance occur only finitely often. It is enough to check the countable family ε=1/k\varepsilon=1/k, k≥1k\geq1. Intersecting the resulting probability-one events ensures that every such tolerance is eventually satisfied.

This is a standard bridge from quantitative probability bounds to pathwise convergence. Independence of the XnX_n is unnecessary when the required summability bounds hold.

The converse is false. With UU uniform on (0,1)(0,1), let

Xn=1{U<1/n}.X_n=\mathbf 1_{\{U<1/n\}}.

Then Xn→0X_n\to0 almost surely, but for 0<ε<10<\varepsilon<1,

∑nP(∣Xn∣>ε)=∑n1n=∞.\sum_n\mathbb P(|X_n|>\varepsilon) = \sum_n\frac1n = \infty.

Extracting an almost-surely convergent subsequence

If Xn→XX_n\to X in probability, a subsequence converges almost surely.

Choose increasing indices nkn_k such that

P(∣Xnk−X∣>2−k)≤2−k.\mathbb P(|X_{n_k}-X|>2^{-k})\leq2^{-k}.

Such indices exist by convergence in probability. Since the upper bounds form a convergent geometric series, the first lemma implies that

∣Xnk−X∣≤2−k|X_{n_k}-X|\leq2^{-k}

eventually almost surely. Thus Xnk→XX_{n_k}\to X almost surely.

A route to a strong law of large numbers

The lemmas often supply the final step in proofs of the strong law of large numbers. For example, let X1,X2,…X_1,X_2,\ldots be independent and identically distributed, with mean μ\mu and finite fourth central moment. Set Yi=Xi−μY_i=X_i-\mu. Independence and centering give

E ⁣[(∑i=1nYi)4]=nE[Y14]+3n(n−1)(E[Y12])2.\mathbb E\!\left[\left(\sum_{i=1}^{n}Y_i\right)^4\right] = n\mathbb E[Y_1^4] + 3n(n-1)\bigl(\mathbb E[Y_1^2]\bigr)^2.

Consequently, for each ε>0\varepsilon>0, there is a finite constant CC, independent of nn, such that

P ⁣(∣1n∑i=1nXi−μ∣>ε)≤Cε4n2.\mathbb P\!\left( \left|\frac1n\sum_{i=1}^{n}X_i-\mu\right|>\varepsilon \right) \leq \frac{C}{\varepsilon^4 n^2}.

These bounds are summable, so the first lemma proves almost-sure convergence of the sample averages.

The fourth-moment assumption is sufficient for this short proof, not necessary for the general strong law for independent, identically distributed variables.

Measure-theoretic form and scope

The first lemma extends directly to measure theory. If (S,A,μ)(S,\mathcal A,\mu) is any measure space and measurable sets AnA_n satisfy

∑nμ(An)<∞,\sum_n\mu(A_n)<\infty,

then

μ(lim sup⁡nAn)=0.\mu(\limsup_n A_n)=0.

The proof uses the same tail-union estimate and does not require μ(S)\mu(S) to be finite.

The second lemma is more sensitive to dependence. There are extensions based on conditional probabilities or controlled intersections, but divergence of the unconditional probability sum alone is insufficient. The practical distinction is therefore between a summability conclusion valid for arbitrary events and a divergence conclusion requiring additional structure.