Why count events along a whole sequence?
A probability such as describes one time. It does not by itself tell us whether an event will happen repeatedly on a single infinite sequence of trials. For convergence almost surely, however, the relevant question is precisely whether deviations from the proposed limit eventually stop. The Borel–Cantelli lemmas turn this pathwise question into a calculation with a series of probabilities, with an important distinction between arbitrary and independent events.
Events that occur infinitely often
For events on one probability space, define
An outcome belongs to this event if every tail contains an occurrence; equivalently, the set of indices at which the event occurs is infinite. Its complement says that some random index exists after which none of the events occurs. This is stronger than saying that each fixed event has small probability.
For random variables and on the same space, almost surely exactly when, for every positive , the events occur only finitely often almost surely. To verify this it is enough to use the countable tolerances , : the intersection of their probability-one events still has probability one. In contrast, convergence in probability only requires for each fixed .
The two lemmas
Theorem 17.1.1
(Borel–Cantelli)
Let be events on a probability space.
- If , then . No independence is required.
- If the events are mutually independent and , then .
Proof
(Union bound for summable series, product bound for independent events)
For the first statement, put . The union bound gives
The final tail tends to zero, so the probability is zero. The events need not be independent, or even distinct.
For the second statement, fix and write . For every , mutual independence and for yield
The event of no occurrence from time onward is contained in each finite intersection, hence has probability zero. The event of only finitely many occurrences is the countable union over of these no-further-occurrence events. It too has probability zero. Thus infinitely many occurrences have probability one.
Proof X-ray
What each half of the proof consumes
The first part uses one inequality, the union bound, applied to the tail union . Since the union bound holds for arbitrary events, the only hypothesis consumed is summability, and only through the tail ; the first terms of the series never matter.
The second part reverses the target. Instead of showing that late events occur, it shows that avoiding all of them from time on has probability zero. The key move is that mutual independence passes to the complements and turns the probability of a finite intersection into a product, which bounds by the exponential of a partial sum. Divergence then drives that bound to zero. The argument closes by countable additivity: there are only countably many starting times , so the union of the null events of no occurrence after is null. Without independence there is no product, and the nested events in the counterexample below show that divergence by itself forces nothing.
Worked examples
Worked example 17.1.2
(Rare independent successes still recur)
Suppose the events are mutually independent with for . Their individual probabilities tend to zero, but the harmonic series diverges. The second lemma gives . Thus a typical path sees infinitely many successes, even though a success at a predetermined late time is unlikely. Replacing by makes the series finite, and the first lemma gives only finitely many successes almost surely, regardless of dependence.
Counterexample mode
A divergent series without independence
Let be uniform on and set . Then and the series diverges, but the events are nested and, for every , eventually . Hence . The probabilities alone do not determine the answer in the divergent case.
Worked example 17.1.3
(Almost-sure convergence with persistent second moments)
Let where ; the events may be dependent. Since , almost every path has only finitely many nonzero terms, so almost surely. Nevertheless for every . Rare spikes disappear along almost every path but are large enough to keep the second moments from converging to zero. Almost-sure convergence alone does not justify passing a limit through an expectation.
Worked example 17.1.4
(How large independent exponentials become)
Let be independent exponential variables with rate one, and fix . For put , so that .
If , the series converges, and the first lemma gives for all but finitely many , almost surely. Hence almost surely. Taking for and intersecting these countably many probability-one events gives almost surely.
The edge case is exactly the harmonic series. The events are independent and , so the second lemma gives infinitely often, almost surely; therefore . Together, almost surely. Each fixed is typically of order one; the logarithmic rate describes how large the occasional exceptional values become along a single path.
Applying the lemmas to deviations
If for each the sum is finite, the first lemma and the countable-tolerance argument imply almost surely. For example, if , Chebyshev's inequality gives a summable bound . No independence is needed.
A bound of order tends to zero but is not summable. It proves convergence in probability, not almost-sure convergence by this argument. This is a limitation of the bound, not a proof that almost-sure convergence fails. The earlier maximal-inequality proof of the strong law overcomes precisely such a difficulty by controlling blocks of partial sums rather than summing the one-time estimates.
Common mistakes
Common mistake
(Pairwise independence is not the stated hypothesis)
The second lemma requires independence as stated; pairwise independence alone does not justify the product displayed in its proof. Some stronger results can weaken the hypothesis, but need a separate argument.
Common mistake
(The first lemma needs no independence)
Conversely, do not attach an independence condition to the first lemma. The union bound in its proof holds for arbitrary events, including nested or repeated ones.
Common mistake
(Vanishing probabilities do not rule out recurrence)
Distinguish the event of infinitely many occurrences from the assertion that stays positive: independent events of probability have vanishing probabilities and nevertheless recur infinitely often almost surely.
Exercises
Quick check
(For arbitrary events , suppose . Bound the probability of at least one occurrence at or after time , and determine the probability of infinitely many occurrences.)
Solution · Answer
The union bound gives . The tail tends to zero, so the first lemma gives probability zero for infinitely many occurrences.
Quick check
(Independent events have probability . Let . Determine whether in probability and almost surely.)
Solution · Answer
For , ; the same is immediate for . Thus in probability. The series diverges and the events are independent, so infinitely often almost surely. Consequently does not converge to zero almost surely.
Quick check
(Let be uniform on and . Determine both kinds of convergence to zero and explain why the divergent sum of deviation probabilities does not contradict the lemmas.)
Solution · Answer
For every , eventually , so almost surely and hence also in probability. For , the deviation probabilities sum to , but the nested events are dependent. The second lemma therefore does not apply; the first lemma is a sufficient condition, not a converse.
Quick check
(Suppose . Show almost surely. Does the same conclusion follow from this proof if the bound is ?)
Solution · Answer
Chebyshev gives , which is summable for each positive integer . The first lemma, followed by a countable intersection, proves almost-sure convergence. With the same upper bounds form a divergent harmonic series, so this proof gives no almost-sure conclusion. The conclusion may still hold in a particular example.