The Borel-Cantelli lemmas turn estimates for individual events into pathwise statements about infinitely many events. They are the standard passage from probability bounds to eventual almost-sure behavior. Zero-one laws then explain why many asymptotic events cannot retain an intermediate probability.
Limsup and liminf events
Definition. For events \(A_1,A_2,\ldots\), \[ \limsup_{n\to\infty}A_n =\bigcap_{m=1}^{\infty}\bigcup_{n\ge m}A_n =\{A_n\ \text{occurs infinitely often}\}, \] while \[ \liminf_{n\to\infty}A_n =\bigcup_{m=1}^{\infty}\bigcap_{n\ge m}A_n =\{A_n\ \text{occurs eventually always}\}. \] Their complements satisfy \[ (\limsup A_n)^c=\liminf A_n^c,\qquad (\liminf A_n)^c=\limsup A_n^c. \]
If \(N=\sum_{n\ge1}1_{A_n}\) is the total number of occurrences, then \(\{N=\infty\}=\limsup A_n\). This identity makes the first lemma almost a statement about integrability of a nonnegative integer-valued random variable.
The two Borel-Cantelli lemmas
Theorem (first Borel-Cantelli lemma). For arbitrary events \(A_n\), if \[ \sum_{n=1}^{\infty}P(A_n)<\infty, \] then \(P(A_n\ \mathrm{i.o.})=0\). No independence assumption is required.
Proof. For every \(m\), \[ P(\limsup A_n) \le P\!\left(\bigcup_{n\ge m}A_n\right) \le\sum_{n\ge m}P(A_n). \] The tail of a convergent nonnegative series tends to zero. Letting \(m\to\infty\) proves the assertion. Equivalently, Tonelli gives \(\mathbb EN=\sum_nP(A_n)<\infty\), and a nonnegative random variable with finite expectation is finite almost surely.
Theorem (second Borel-Cantelli lemma). If \(A_1,A_2,\ldots\) are independent and \[ \sum_{n=1}^{\infty}P(A_n)=\infty, \] then \(P(A_n\ \mathrm{i.o.})=1\).
Proof. Fix \(m\). Independence and \(1-x\le e^{-x}\) imply \[ P\!\left(\bigcap_{n=m}^{N}A_n^c\right) =\prod_{n=m}^{N}(1-P(A_n)) \le \exp\!\left\{-\sum_{n=m}^{N}P(A_n)\right\}\longrightarrow0. \] By continuity from above, \[ P\!\left(\bigcap_{n\ge m}A_n^c\right)=0. \] Taking the countable union over \(m\) shows that the event on which only finitely many \(A_n\) occur has probability zero.
Example (why dependence matters). Let \(A_n=A\) for every \(n\), where \(P(A)=1/2\). Then \(\sum_nP(A_n)=\infty\), but \[ P(A_n\ \mathrm{i.o.})=P(A)=\frac12. \] Divergence of the probability sum alone gives no converse to the first lemma.
Threshold tests for independent observations
Proposition. Let \(X_n\) be independent and let \(u_n\) be deterministic. Then \[ P(X_n>u_n\ \mathrm{i.o.})= \begin{cases} 0,&\sum_nP(X_n>u_n)<\infty,\\ 1,&\sum_nP(X_n>u_n)=\infty. \end{cases} \]
Proof. Apply the two lemmas to \(A_n=\{X_n>u_n\}\). The events inherit independence from the random variables.
Example (exponential upper envelope). If \(X_n\) are i.i.d. exponential with mean one, then \(P(X_n>c\log n)=n^{-c}\). Hence \[ P(X_n>c\log n\ \mathrm{i.o.})= \begin{cases} 0,&c>1,\\ 1,&0<c\le1. \end{cases} \] In particular, \(\limsup_n X_n/\log n=1\) almost surely: use rational \(c>1\) for the upper bound and rational \(c<1\) for the lower bound.
Kolmogorov's zero-one law
Definition. For random variables \(X_1,X_2,\ldots\), the tail sigma-field is \[ \mathcal T=\bigcap_{m=1}^{\infty}\sigma(X_m,X_{m+1},\ldots). \] A tail event is unchanged by modifying any finite initial segment of the sequence.
Theorem (Kolmogorov zero-one law). If \(X_1,X_2,\ldots\) are independent, then every \(T\in\mathcal T\) satisfies \(P(T)\in\{0,1\}\).
Proof. Put \(\mathcal F_m=\sigma(X_1,\ldots,X_m)\) and \(\mathcal F_\infty=\sigma(\bigcup_m\mathcal F_m)\). Since \(T\in\sigma(X_{m+1},X_{m+2},\ldots)\), independence of the variables implies that \(T\) is independent of \(\mathcal F_m\) for every \(m\). Define \[ \mathcal D=\{B\in\mathcal F_\infty:P(T\cap B)=P(T)P(B)\}. \] The class \(\mathcal D\) is a lambda-system and contains the pi-system \(\bigcup_m\mathcal F_m\). Dynkin's pi-lambda theorem therefore gives \(\mathcal D=\mathcal F_\infty\). But \(T\in\mathcal T\subset\mathcal F_\infty\), so \(T\) is independent of itself: \[ P(T)=P(T\cap T)=P(T)^2. \] Thus \(P(T)=0\) or \(1\).
Convergence of \(\sum_nX_n\), convergence of \(S_n/a_n\), and events of the form \(\{X_n>u_n\ \mathrm{i.o.}\}\) are tail events. The zero-one law does not tell which of zero or one occurs; moment estimates and Borel-Cantelli usually make that decision.
Hewitt-Savage symmetry
Theorem (Hewitt-Savage zero-one law). Let \(X_n\) be i.i.d. If an event \(A\in\sigma(X_1,X_2,\ldots)\) is invariant under every finite permutation of the coordinates, then \(P(A)\in\{0,1\}\).
Proof outline. Approximate \(A\) in probability by an event \(B\in\sigma(X_1,\ldots,X_m)\). Move the first \(m\) coordinates to a disjoint block by a finite permutation. Invariance of \(A\) makes the moved copy approximate the same event \(A\), while the original and moved copies of \(B\) are independent because the observations are i.i.d. Passing the approximation error to zero shows \(P(A)=P(A)^2\).
Remark. Hewitt-Savage is stronger than Kolmogorov for i.i.d. sequences: permutation-invariant events need not visibly belong to the tail sigma-field. It is useful for statements about unordered samples, empirical distributions, and limsup functionals.