From Tail Bounds to Almost-Sure Convergence

From Rare Deviations to Almost-Sure Convergence

Convergence in probability controls the chance of a deviation at each fixed index. Almost-sure convergence makes a stronger statement: with probability one, only finitely many sufficiently large deviations occur. A useful bridge between these statements is the first Borel–Cantelli lemma. It says that if the probabilities of a sequence of events have a finite sum, then those events occur only finitely often with probability one.

The key is to apply this result separately to deviations larger than each positive tolerance. If the resulting probability sums are finite, then eventually the sequence stays within every fixed tolerance, which is exactly convergence.

Definition: For events \(A_1,A_2,\ldots\), the event that infinitely many of them occur is \(\limsup_{n\to\infty} A_n=\bigcap_{N=1}^{\infty}\bigcup_{n\geq N}A_n\). Thus \(\limsup A_n\) occurs precisely when, no matter how far along the sequence one starts, at least one later event occurs.

The First Borel–Cantelli Lemma

The first Borel–Cantelli lemma does not require independence. Its conclusion follows directly from the union bound: the probability of at least one event occurring after index \(N\) is at most the sum of their probabilities.

Theorem (First Borel–Cantelli lemma): If \((A_n)_{n\geq 1}\) is a sequence of events and \(\sum_{n=1}^{\infty}P(A_n)<\infty\), then \(P(A_n\text{ infinitely often})=0\).

Proof. For every \(N\), the event \(\limsup A_n\) is contained in \(\bigcup_{n\geq N}A_n\). By the union bound,

P(\limsup_{n\to\infty}A_n) \leq P\left(\bigcup_{n\geq N}A_n\right) \leq \sum_{n\geq N}P(A_n).

Because the full series of nonnegative terms converges, its tail \(\sum_{n\geq N}P(A_n)\) tends to zero as \(N\to\infty\). The fixed probability on the left is therefore zero. \(\square\)

Theorem (Summable-tail criterion for almost-sure convergence): Let \(X_n\) and \(X\) be random variables on the same probability space. If, for every \(\varepsilon>0\), \(\sum_{n=1}^{\infty}P(|X_n-X|>\varepsilon)<\infty\), then \(X_n\xrightarrow{a.s.}X\). It is enough to check the condition for \(\varepsilon=1,1/2,1/3,\ldots\).

Proof. Fix a positive integer \(m\) and set \(A_n^{(m)}=\{|X_n-X|>1/m\}\). The assumed tail condition gives \(\sum_n P(A_n^{(m)})<\infty\). The first Borel–Cantelli lemma implies that, with probability one, only finitely many \(A_n^{(m)}\) occur. Intersect these probability-one events over all positive integers \(m\); the intersection still has probability one because its complement is a countable union of probability-zero events. On that intersection, for every \(m\), eventually \(|X_n-X|\leq 1/m\). Given any \(\varepsilon>0\), choose \(m\) with \(1/m<\varepsilon\); eventually \(|X_n-X|<\varepsilon\). Hence \(X_n\to X\) there. \(\square\)

Extracting an Almost-Surely Convergent Subsequence

This criterion gives an important consequence of convergence in probability. A sequence converging in probability need not converge almost surely, but one can always select a subsequence that does. The selection makes the probabilities of chosen deviations small enough to be summable.

Theorem: If \(Y_n\xrightarrow{p}Y\), then there is a strictly increasing sequence of indices \(n_k\) such that \(Y_{n_k}\xrightarrow{a.s.}Y\).

Proof. By convergence in probability, for each \(k\) there is an index beyond which \(P(|Y_n-Y|>1/k)<2^{-k}\). Choose \(n_k\) beyond that index and larger than \(n_{k-1}\). Then

\sum_{k=1}^{\infty}P(|Y_{n_k}-Y|>1/k) \leq \sum_{k=1}^{\infty}2^{-k}<\infty.

For any fixed \(\varepsilon>0\), choose \(K\) such that \(1/k<\varepsilon\) for \(k\geq K\). Then \(\{|Y_{n_k}-Y|>\varepsilon\}\subseteq\{|Y_{n_k}-Y|>1/k\}\) for \(k\geq K\), so the probabilities of deviations exceeding \(\varepsilon\) are summable along the subsequence. The summable-tail criterion gives \(Y_{n_k}\xrightarrow{a.s.}Y\). \(\square\)

Worked Example: A Convergent-in-Probability Sequence With a Good Subsequence

Let \(Y_n\) be independent Bernoulli random variables with \(P(Y_n=1)=1/n\) and \(P(Y_n=0)=1-1/n\). Show that \(Y_n\xrightarrow{p}0\), select a subsequence that converges almost surely to zero, and check that the full sequence does not converge almost surely to zero.

Since \(Y_n\) takes only the values zero and one, for \(0<\varepsilon<1\), \(P(|Y_n|>\varepsilon)=P(Y_n=1)=1/n\to0\). For \(\varepsilon\geq1\), that probability is zero. Thus \(Y_n\xrightarrow{p}0\).

Take \(n_k=2^k\), for \(k\geq1\). For \(0<\varepsilon<1\),

\sum_{k=1}^{\infty}P(|Y_{2^k}|>\varepsilon) =\sum_{k=1}^{\infty}\frac{1}{2^k}=1<\infty.

For \(\varepsilon\geq1\), every term is zero. The summable-tail criterion therefore gives \(Y_{2^k}\xrightarrow{a.s.}0\).

For the full sequence, independence gives, for integers \(M\geq N\),

P(Y_n=0\text{ for every }N\leq n\leq M) =\prod_{n=N}^{M}\left(1-\frac1n\right) =\frac{N-1}{M}.

As \(M\to\infty\), this probability tends to zero. Hence the probability that all variables from index \(N\) onward are zero is zero. Taking the union over \(N\), the probability that \(Y_n=1\) only finitely often is zero. So \(Y_n=1\) infinitely often with probability one, and the full sequence does not converge almost surely to zero. This illustrates why a carefully chosen subsequence may converge almost surely even when the original sequence does not.

Tail Bounds for Averages

For averages, the summable-tail criterion can be used as soon as one has a usable bound on the deviation probability. Let \(X_1,X_2,\ldots\) have finite means \(\mu_i=E[X_i]\), and write \(\bar X_n=n^{-1}\sum_{i=1}^n X_i\). A direct sufficient condition is that, for each \(\varepsilon>0\), there are bounds \(b_n(\varepsilon)\) satisfying

P(|\bar X_n-E[\bar X_n]|>\varepsilon)\leq b_n(\varepsilon), \qquad \sum_{n=1}^{\infty}b_n(\varepsilon)<\infty.

Then \(\bar X_n-E[\bar X_n]\xrightarrow{a.s.}0\). If \(E[\bar X_n]\to\mu\), it follows that \(\bar X_n\xrightarrow{a.s.}\mu\): the deterministic difference \(E[\bar X_n]-\mu\) tends to zero, and the random difference from the expectation tends to zero almost surely.

One common source of bounds is Chebyshev’s inequality. If the variables are pairwise uncorrelated with finite variances, then \(\operatorname{Var}(\bar X_n)=n^{-2}\sum_{i=1}^n\operatorname{Var}(X_i)\). Therefore

P(|\bar X_n-E[\bar X_n]|>\varepsilon) \leq \frac{\sum_{i=1}^n\operatorname{Var}(X_i)}{n^2\varepsilon^2}.

If the right-hand side is summable in \(n\) for every \(\varepsilon>0\), the averages converge almost surely to their expectations in the sense just described. This is a sufficient condition, not a necessary one. In particular, for identically distributed variables with positive finite variance, the bound is proportional to \(1/n\), whose series diverges. That particular Chebyshev bound cannot establish almost-sure convergence of the full sequence.

Worked Example: Chebyshev’s Inequality Along a Geometric Subsequence

Let \(X_1,X_2,\ldots\) be pairwise uncorrelated, identically distributed random variables with \(E[X_i]=\mu\) and \(\operatorname{Var}(X_i)=\sigma^2<\infty\). Show that the averages at indices \(n_k=2^k\) converge almost surely to \(\mu\).

For \(\bar X_n=n^{-1}\sum_{i=1}^n X_i\), pairwise uncorrelatedness gives \(\operatorname{Var}(\bar X_n)=\sigma^2/n\). Chebyshev’s inequality therefore yields, for every \(\varepsilon>0\),

P(|\bar X_{2^k}-\mu|>\varepsilon) \leq \frac{\sigma^2}{\varepsilon^2 2^k}.

Summing over \(k\geq1\),

\sum_{k=1}^{\infty}P(|\bar X_{2^k}-\mu|>\varepsilon) \leq \frac{\sigma^2}{\varepsilon^2} \sum_{k=1}^{\infty}2^{-k} =\frac{\sigma^2}{\varepsilon^2}<\infty.

The summable-tail criterion now gives \(\bar X_{2^k}\xrightarrow{a.s.}\mu\). The argument establishes convergence only at the geometric indices \(2^k\); it does not bound the deviations at every intervening index.

Worked Example: Exponential Tail Bounds for Normal Sample Averages

Suppose \(X_1,X_2,\ldots\) are independent with \(X_i\sim N(\mu,\sigma^2)\), where \(\sigma^2>0\). Show directly from a tail bound that \(\bar X_n\xrightarrow{a.s.}\mu\).

For any real \(t\), the moment-generating function of \(X_i-\mu\) is \(E[e^{t(X_i-\mu)}]=e^{\sigma^2t^2/2}\). Independence gives \(E[e^{t\sum_{i=1}^n(X_i-\mu)}]=e^{n\sigma^2t^2/2}\). For \(t>0\), Markov’s inequality implies

P(\bar X_n-\mu>\varepsilon) =P\left(e^{t\sum_{i=1}^n(X_i-\mu)}>e^{tn\varepsilon}\right) \leq \exp\left(-tn\varepsilon+\frac{n\sigma^2t^2}{2}\right).

The exponent is minimized at \(t=\varepsilon/\sigma^2\), giving an upper-tail bound \(e^{-n\varepsilon^2/(2\sigma^2)}\). Applying the same argument to \(-\sum_{i=1}^n(X_i-\mu)\) gives the same bound for the lower tail. Consequently,

P(|\bar X_n-\mu|>\varepsilon) \leq 2e^{-n\varepsilon^2/(2\sigma^2)}.

For fixed \(\varepsilon>0\), this is a geometric series when summed over \(n\), with ratio \(e^{-\varepsilon^2/(2\sigma^2)}<1\). The sum is finite, so the summable-tail criterion proves \(\bar X_n\xrightarrow{a.s.}\mu\).

Common Pitfall: A Tail Probability That Shrinks Is Not Enough

The condition \(P(|X_n-X|>\varepsilon)\to0\) for every \(\varepsilon>0\) establishes convergence in probability. It does not ensure almost-sure convergence: the probabilities may shrink too slowly for their sum to be finite, and deviations may keep occurring. The independent Bernoulli example above has probabilities \(1/n\), which tend to zero but have a divergent sum.

The first Borel–Cantelli lemma is a one-way implication. Summability guarantees that only finitely many deviations occur, but a divergent sum alone does not show that deviations occur infinitely often. Additional assumptions, such as independence in the Bernoulli calculation, can sometimes support that stronger conclusion; divergence by itself cannot.

Key takeaway: To prove almost-sure convergence with the first Borel–Cantelli lemma, bound each fixed-tolerance deviation probability and show that the bounds are summable. If a full-sequence bound is not summable, a carefully chosen subsequence may still have summable bounds and hence converge almost surely.

Check Your Understanding

Use the summable-tail criterion and the role of the index sequence to guide your answers.

State the first Borel–Cantelli lemma and identify which part of its proof uses a probability bound.
If \(P(|X_n-X|>\varepsilon)\leq 3/n^2\) for every \(n\), what can you conclude about \(X_n\) and \(X\)?
Why does convergence in probability allow selection of an almost-surely convergent subsequence?
For independent, identically distributed observations with finite positive variance, what does Chebyshev’s inequality give for \(P(|\bar X_n-\mu|>\varepsilon)\), and why is that bound insufficient by itself for the summable-tail criterion over all \(n\)?
Does \(\sum_n P(A_n)=\infty\) by itself imply that \(A_n\) occurs infinitely often with probability one? Explain.