This text is still being edited: it may contain typos, inaccuracies, and locally unpolished spots. If you find something, please let the author know (contact details on the course page).
Questions about the long-run behavior of random sequences β βwill this happen infinitely many more times?β, βwill the failures ever stop?β, βwill the series converge?β β have a surprising property: their probabilities are almost never βaverageβ. The answer, as a rule, is either \(0\) or \(1\), and this topic is about two tools that compute which one. The Borel-Cantelli lemma is a working countable criterion (βadd up the probabilities and see whether the series convergesβ); Kolmogorovβs zero-one law is the structural reason why intermediate answers never occur. The practical meaning is direct: βan event of positive probability in independent repetitions will occur a.s., and moreover infinitely oftenβ β this is the mathematics of reliability (any failure with nonzero probability will occur regularly β the only question is how often), of cryptography (a random search will sooner or later hit a collision), and of the folkloric βmonkey with a typewriterβ.
The Borel-Cantelli lemma
Definition 1 For a sequence of events \(A_1, A_2, \ldots\) \[
\limsup _n A_n := \bigcap _{n=1}^\infty \bigcup _{k \geq n} A_k = \left\{ \text{infinitely many of the } A_n \text{ occurred}\right\} =: \left\{ A_n \text{ i.o.}\right\}
\] (i.o. β βinfinitely oftenβ); dually, \(\liminf_n A_n = \left\{ \text{all } A_n \text{ except finitely many}\right\}\).
The interactive illustration has not been created yet. See the source: /home/nedosh/Documents/online_math_notes/math-notes_FPMI_2/courses/nedosh_courses/courses/04-probability/02_PT/contents/specials/050/01_infinitely_often_fig.tex.
Theorem 1 (Borel-Cantelli)
If \(\sum_{n} \mathbb {P}\left(A_n\right) < \infty\), then \(\mathbb {P}\left(A_n \text{ i.o.}\right) = 0\).
If the events \(A_n\) are independent and \(\sum_{n} \mathbb {P}\left(A_n\right) = \infty\), then \(\mathbb {P}\left(A_n \text{ i.o.}\right) = 1\).
Both parts take one line each. (1): \(\mathbb {P}\left(\limsup A_n\right) \leq \mathbb {P}\left(\bigcup_{k \geq n} A_k\right) \leq \sum_{k \geq n} \mathbb {P}\left(A_k\right) \to 0\) as the tail of a convergent series. (2): by independence and the inequality \(1 - x \leq e^{-x}\)
\[
\mathbb {P}\left(\bigcap _{k=n}^{N} A_k^\complement \right) = \prod _{k=n}^N \left(1 - \mathbb {P}\left(A_k\right)\right) \leq \exp \left(-\sum _{k=n}^N \mathbb {P}\left(A_k\right)\right) \xrightarrow [N \to \infty ]{} 0,
\]
hence \(\mathbb {P}\left(\bigcup_{k \geq n} A_k\right) = 1\) for every \(n\), and the intersection over \(n\) also has probability \(1\).
The first part requires no independence whatsoever β it is pure measure theory, and hence foolproof: the overwhelming majority of a.s. convergence proofs in this course and in the stochastic processes course are built as βbound \(\mathbb {P}\left(\left|\xi_n - \xi \right| > \varepsilon \right)\) by a summable sequence β apply Borel-Cantelliβ:
Corollary 1 If \(\sum_n \mathbb {P}\left(\left|\xi_n - \xi \right| > \varepsilon \right) < \infty\) for every \(\varepsilon > 0\), then \(\xi_n \to \xi\) a.s.
In the second part independence is essential: take a single coin toss and \(A_n \equiv A = \left\{ \text{heads}\right\}\) β the series diverges, but \(\mathbb {P}\left(A_n \text{ i.o.}\right) = \mathbb {P}\left(A\right) = \frac12\).
A monkey presses equiprobable keys forever and independently (an alphabet of \(K\) symbols). Prove that with probability \(1\) it will type the complete text of βWar and Peaceβ (a string of length \(L\)), and moreover infinitely many times.
Split the stream of keystrokes into disjoint blocks of length \(L\): keystrokes \(1, \ldots , L\), then \(L+1, \ldots , 2L\), and so on. Let \(A_n\) be the event βthe \(n\)-th block exactly matches the text of the novelβ. The blocks do not overlap, so the events \(A_n\) are independent, and \(\mathbb {P}\left(A_n\right) = K^{-L} > 0\) β monstrously small, but the same for every \(n\), so \(\sum_n \mathbb {P}\left(A_n\right) = \infty\). By the second part of Borel-Cantelli, \(\mathbb {P}\left(A_n \text{ i.o.}\right) = 1\).
The trick of βcutting into independent blocksβ is the main device for applications of BC2: on their own, the events βthe text starts at position \(t\)β are dependent (they overlap), but block by block independence is honest. The engineering moral, without irony: in a sufficiently long series of trials any event of positive probability is guaranteed to occur β rare failures do not βpossibly happenβ, they happen for certain, and a system must be designed with this in mind.
Let \(\xi , \xi_1, \xi_2, \ldots\) be independent identically distributed variables. Prove:
if \(\mathbb {E}\left[\left|\xi \right|\right] < \infty\), then \(\frac{\xi_n}{n} \to 0\) a.s.;
if \(\mathbb {E}\left[\left|\xi \right|\right] = \infty\), then \(\limsup_n \frac{\left|\xi_n\right|}{n} = \infty\) a.s.
Let \(\left\{ \xi_{n}\right\}\) be an arbitrary (with no assumptions whatsoever!) sequence of random variables. Prove that there exists a non-random sequence \(a_{n} > 0\) for which \(\frac{\xi_{n}}{a_{n}} \to 0\) almost surely.
A fair coin is tossed. Prove that for any \(k \in \mathbb {N}\) a run of \(k\) consecutive heads will appear infinitely many times a.s. Moreover, show that runs of length \(\lfloor \log_2 n \rfloor\) starting no later than toss \(n\) appear i.o. (i.e. record run lengths grow logarithmically).
The zero-one law
Definition 2 Let \(\xi_1, \xi_2, \ldots\) be a sequence of random variables. The tail \(\sigma\)-algebra is \[
\mathcal{T} = \bigcap _{n=1}^{\infty } \sigma \left(\xi _n, \xi _{n+1}, \ldots \right).
\] Tail events are those that do not depend on any finite collection of the first terms: convergence of the series \(\sum \xi_n\), convergence of \(\frac{S_n}{n}\), finiteness of \(\limsup \xi_n\), β\(A_n\) infinitely oftenβ, and so on.
Theorem 2 (Kolmogorovβs zero-one law) If \(\xi_1, \xi_2, \ldots\) are independent, then every tail event has probability \(0\) or \(1\).
The idea of the proof is elegant: a tail event \(A\) does not depend on \(\sigma (\xi_1, \ldots , \xi_n)\) for every \(n\) (it lies in the βtailβ \(\sigma\)-algebra); by the criterion via \(\pi\)-systems (topic 1!) \(A\) does not depend on \(\sigma (\xi_1, \xi_2, \ldots )\) either β but \(A\) itself lies in this \(\sigma\)-algebra. An event independent of itself: \(\mathbb {P}\left(A\right) = \mathbb {P}\left(A \cap A\right) = \mathbb {P}\left(A\right)^2\), whence \(\mathbb {P}\left(A\right) \in \left\{ 0, 1\right\}\). \(\blacksquare\)
The law explains the βpolarizationβ of all our questions: a random series of independent terms has no scenario βconverges with probability \(\frac13\)β. But it does not tell us which of the two alternatives holds β specific criteria settle that. For series, the answer is given by (optional, statement only):
Theorem 3 (Kolmogorovβs three-series theorem) Let \(\xi_n\) be independent, \(c > 0\), \(\xi_n^c := \xi_n \; \mathbb {1}_{\left|\xi_n\right| \leq c}\). The series \(\sum_n \xi_n\) converges a.s. if and only if all three numerical series converge: \[
\sum _n \mathbb {P}\left(\left|\xi _n\right| > c\right), \qquad \sum _n \mathbb {E}\left[\xi _n^c\right], \qquad \sum _n \operatorname {Var}\left[\xi _n^c\right].
\]
Let \(\xi_1, \xi_2, \ldots\) be independent. Which of the following events are tail events: (a) \(\left\{ \sum_n \xi_n \text{ converges}\right\}\); (b) \(\left\{ \limsup_n \frac{S_n}{n} > 1\right\}\), where \(S_n = \xi_1 + \ldots + \xi_n\); (c) \(\left\{ \sum_n \xi_n > 1\right\}\); (d) \(\left\{ \xi_n > 0 \text{ i.o.}\right\}\)? For the tail events, draw a conclusion about their probability.
(Random signs.) Let \(\varepsilon_1, \varepsilon_2, \ldots\) be independent, \(\mathbb {P}\left(\varepsilon_n = \pm 1\right) = \frac12\). Prove that the event \(A = \left\{ \sum_n \frac{\varepsilon_n}{n} \text{ converges}\right\}\) has probability \(0\) or \(1\), and determine which one exactly (you may use the three-series theorem or wait for topic 6).