advanced30 min studyLesson 195 in Mathematics

Borel–Cantelli lemmas and tail events

Turn probability bounds into almost-sure eventual statements and distinguish summable errors from independent repeated opportunities.

Before you begin

On this page

The question for today

What you’ll understand

Express infinitely-often events using countable unions and intersections.
Apply each Borel–Cantelli direction with the correct dependence assumptions.
Identify tail events and state the independent-sequence zero–one law.

Suppose a numerical procedure has an error event at every iteration. Saying the error probability tends to zero is different from saying only finitely many errors occur along almost every infinite run. Borel–Cantelli connects the second statement to a series of error probabilities. Its two directions have different assumptions, and ignoring that asymmetry produces incorrect conclusions about dependent events. Tail sigma-algebras then explain why certain long-run properties of independent sequences must have probability either zero or one.

Infinitely often is a measurable limit event

An outcome belongs to infinitely many events when, after every index m, at least one later event occurs. This description becomes an intersection over m of unions over n≥m. The sets in this intersection decrease with m, so continuity from above applies to their probabilities. The construction uses only countable set operations and therefore stays inside the event sigma-algebra. No informal reference to an event occurring at an unspecified infinite time is necessary.

The probability of the union after m is at most the sum of its event probabilities. If the complete series converges, these tail sums tend to zero. Therefore the infinitely-often event has probability zero. This first Borel–Cantelli lemma needs no independence at all. It provides a useful design principle: choose error budgets whose sum is finite if the goal is to rule out infinitely many failures almost surely, even when failures at different iterations are strongly dependent.

\{A_n\ \mathrm{i.o.}\}=\bigcap_{m=1}^{\infty}\bigcup_{n\ge m}A_n,\qquad \sum_n\mathbb P(A_n)<\infty\ \Longrightarrow\ \mathbb P(A_n\ \mathrm{i.o.})=0

The implication follows from the union bound and continuity of probability for decreasing sequences. Independence is not required.↔ Scroll wide equations horizontally.

Divergence needs control of dependence

For a mutually independent sequence of events, divergence of the sum of their probabilities forces infinitely many of them to occur almost surely. One proof bounds the probability of no event between m and N by the exponential of the negative partial probability sum. As N grows, this bound vanishes. Each deterministic starting index therefore has a later occurrence with probability one, and the countable intersection over starting indices gives infinitely many occurrences.

Without independence the divergent series alone says little. Repeating a single event of probability one-half at every index makes the probability series diverge, but infinitely many occurrences happen exactly when that one event happens, with probability one-half. By contrast, a sequence of independent events with probabilities 1/n for n≥2 does occur infinitely often almost surely. Dependence can synchronize all opportunities, whereas independence prevents this particular collapse of infinitely many trials into a single piece of information.

\mathbb P\!\left(\bigcap_{n=m}^{N}A_n^c\right)=\prod_{n=m}^{N}(1-\mathbb P(A_n))\le\exp\!\left(-\sum_{n=m}^{N}\mathbb P(A_n)\right)

The product identity assumes mutual independence. If the probability sum diverges, the bound tends to zero for every fixed m.↔ Scroll wide equations horizontally.

Tail information and the zero–one law

For a sequence of random variables, the tail sigma-algebra consists of events measurable from the sequence after every finite initial segment. Changing any finite number of coordinates cannot affect the usual tail examples, such as whether a sequence converges or whether successes occur infinitely often. For an independent sequence, Kolmogorov’s zero–one law states that every tail event has probability zero or one. The event may be difficult to classify, but it cannot have an intermediate probability.

The proof uses independence to make a tail event independent of each finite initial block, then a sigma-algebra extension argument makes it independent of the entire sequence sigma-algebra. Since the tail event belongs to that whole sigma-algebra, it is independent of itself. Its probability must therefore equal its own square. This law determines only the two possible values; a separate estimate or argument is needed to choose between them. It also does not apply to arbitrary events depending on the first few observations.

\mathcal T=\bigcap_{m\ge1}\sigma(X_m,X_{m+1},\ldots),\qquad A\in\mathcal T\ \Longrightarrow\ \mathbb P(A)=\mathbb P(A)^2\in\{0,1\}

The zero–one conclusion assumes that the coordinate sequence is mutually independent. The tail sigma-algebra is defined without that assumption.↔ Scroll wide equations horizontally.

Work it through

Two schedules of rare errors

An algorithm has events A_n with P(A_n)≤1/n² for n≥1. A separate independent experiment has events B_n with P(B_n)=1/n for n≥2. Determine the probability of infinitely many events in each schedule.

The series of 1/n² converges. Comparing the A probabilities with this summable upper bound gives a finite total probability sum, regardless of dependence among the A events.
The first Borel–Cantelli lemma therefore gives probability zero to infinitely many A events: almost every run has some finite final error index, though that index may vary across runs.
The harmonic series of B probabilities diverges and the B events are mutually independent. The second Borel–Cantelli lemma gives probability one to infinitely many B events, even though each individual probability tends to zero.

The result

The A schedule has only finitely many occurrences almost surely. The independent B schedule has infinitely many occurrences almost surely; shrinking individual probabilities do not imply eventual absence.

The living notebook

Explore the model

Interactive lab

Interactive lab · probability

Finite opportunities before an infinite statement

Set p=0.2 and increase n from five to ten. Predict that the zero-success bar falls from 0.8⁵ to 0.8¹⁰. It represents no success in n independent equal-probability opportunities. The exact binomial panel illustrates the finite product used in the second-lemma proof, not the unequal probabilities 1/n.

Exact probabilityHighlighted outcomeMean np

Mean · np: 5
Variance · np(1−p): 2.5
Total probability: 1

Success probability p0.5Trials n10

t = 0 s

These are exact binomial probabilities for independent trials with one fixed success probability. Playback tours the distribution; it does not resample outcomes. Parameter changes pause playback and recompute the model at the current elapsed time. Reset restores both parameters and returns time to zero. Playback starts paused. Adjust either parameter, then choose Play or Step.

Look forA finite plot cannot establish an infinitely-often event. Its declining zero bar supports the finite-product intuition; the limiting proof still requires an unbounded sequence and its hypotheses.

Pause & reason

Check your understanding

Interactive checks need JavaScript. You can still read the explanation.

Read the checkpoint explanation

Every event occurs together or none occurs, so the infinitely-often event equals A. Independence is missing from the second Borel–Cantelli hypothesis, while the probability remains perfectly well-defined.

Your turn

Try it yourself

Let X_n be independent Bernoulli variables with P(X_n=1)=1/(n+1)². Prove that their sum contains only finitely many nonzero terms almost surely. Does this assertion bound the final nonzero index by one deterministic integer?

Take a moment to make a prediction or work it out on paper. Open a hint when you need one.

Give me a hint

Apply the first lemma to the events X_n=1, then distinguish an almost-sure finite random index from a uniform deterministic bound.

Compare with the solution

The series of success probabilities converges, so the first lemma gives probability zero to infinitely many successes. Thus almost every outcome has a finite number of nonzero terms. There is no deterministic final index that works almost surely: for every fixed N, the event X_(N+1)=1 has strictly positive probability, so a success later than N remains possible. Almost-sure finiteness does not mean one universal finite cutoff.

Keep the idea

Take it with you

Summable event probabilities rule out infinitely many occurrences without independence.
The divergent-series converse needs suitable independence assumptions.
Independent-sequence tail events obey a zero–one law, which alone does not choose the value.

Read further

Original sources and deeper explanations to follow at your own pace.

Optional progress, saved in this browser when available. Revisit any lesson at any time.

Lesson not marked complete.