The Borel-Cantelli Lemmas, and Their Relationship to Limit Superior and Limit Inferior of Sets (or, Can a Monkey Really Type Hamlet?)

Abstract

The purpose of this chapter is to show that if a monkey types infinitely, Shakespeare’s Hamlet and any other works one may wish to add to the list will each be typed, not once, not twice, but infinitely often with a probability of 1. This dramatic fact is a simple consequence of the Borel-Cantelli lemma and will come as no surprise to anyone who has taken a graduate-level course in Probability. The proof of this result, however, is quite accessible to anyone who has but a rudimentary understanding of the concept of independence, together with the notion of limit superior and limit inferior of a sequence of sets.

1. Introduction

Consider a monkey named Sue who is given a word processor with $N$ symbols. We shall assume that these symbols include the 26 letters of the English alphabet (upper and lower case), all the Greek letters, the numbers 0 through 9, a blank space, all the standard punctuation marks (,.; − etc.), and mathematical symbols ($\infty$, $\int$, $\Rightarrow$, $\nabla$, etc.); imagine, in fact, that $N$ is so large that the keyboard is capable of typing just anything we might fancy, in any language. (A LaT_EX editor could do much of that too, but not in all languages!)

If Sue is handed such a machine and pounds away, randomly, it is clear that most of what she types will be complete gibberish. A stray segment of sense such as “dog eat HAy” or even “Ronnie ReAGan our 40th PresiD$\mathit{\epsilon \eta \tau }$ of USA” would surprise no one, but how often, we ask, would she successfully manage to type the Constitution of the United States, or Shakespeare’s $\mathit{\text{Hamlet}}$, or the fundamental mathematical works of the 2026 Fields Medalist(s)?

The purpose of this chapter is to show that if Sue types infinitely, the above works (and any others that one may choose to add to the list) will each be typed, not once, not twice, but infinitely often with a probability of 1. This dramatic fact is a simple consequence of the Borel-Cantelli lemma and will come as no surprise to anyone who has taken a serious graduate-level course in Probability. The proof of this result, however, is quite accessible to anyone who has but a rudimentary understanding of the concept of independence.

The reader is invited, while reading this chapter, to let his/her imagination run wild, and concoct a plethora of similar examples. A somewhat mundane objection may be raised immediately: how can Sue (or anyone else for that matter) type indefinitely? We shall not dwell on this nonmathematical problem, but will remark instead (and prove a little later) that Sue’s never-ending assignment is mathematically equivalent to the task of randomly selecting a number from the interval $\left[0,1\right]$.

We would like to mention that our problem is related to the famous “Problem of a printed line,” a popular account of which can be found in George Gamow’s classic book [1]. The solution presented there, however, is entirely deterministic and of a finite character: the automatic printing press considered by Gamow does not print indefinitely, and the probabilities of various outcomes are not calculated.

2. Limit superior and limit inferior of a sequence of sets

Consider any sequence ${\left\{A_n\right\}}_{n=1}^{\infty }$ of subsets of a set $\mathrm{\Omega }$. Points of $\mathrm{\Omega }$ will be denoted by $\omega$. We know that

$$\underset{n=1}{\overset{\infty }{\cup }}{A}_n=\left\{\omega \in \mathrm{\Omega }:\omega \in A_n\text{for}\text{some}n\right\}$$

and

$$\underset{n=1}{\overset{\infty }{\cap }}{A}_n=\left\{\omega \in \mathrm{\Omega }:\omega \in A_n\text{for}\text{each}n\right\}$$

It follows that

$$\underset{n=1}{\overset{\infty }{\cap }}\underset{k=n}{\overset{\infty }{\cup }}{A}_k=\left\{\omega \in \mathrm{\Omega }:\forall n\exists k\ge n\text{with}\omega \in A_k\right\}$$

To better understand this somewhat complicated set, we first let $n=1$ and note that $\omega \in A_k$ for some $k\ge 1$, say $k=k_1$. Letting $n=k_1$, we see that $\omega$ must belong to some $A_{k_2}$, where $k_2\ge k_1$. Continuing in this fashion, we see that $\omega \in {\cap }_{n=1}^{\infty }{\cup }_{k=n}^{\infty }{A}_k$ if and only if $\omega \in A_k$ for infinitely many $k$‘s.

The set ${\cap }_{n=1}^{\infty }{\cup }_{k=n}^{\infty }{A}_k$ is called the limit superior of the sequence ${\left\{A_n\right\}}_{n=1}^{\infty }$, and is denoted by $\text{lim}\text{sup}{A}_n$, or, $\overline{lim}{A}_n$, or, rather appropriately, by $\left\{A_n\mathrm{i}.\mathrm{o}.\right\}$, where i.o. stands for “infinitely often.”

In a similar fashion, we observe that the set

$$\underset{n=1}{\overset{\infty }{\cup }}\underset{k=n}{\overset{\infty }{\cap }}{A}_k=\left\{\omega \in \mathrm{\Omega }:\exists n\text{such}\text{that}\omega \in A_k\forall k\ge n\right\}$$

is a collection of those points $\omega$ that belong to all but a finite number of the $A_n$‘s. ${\cup }_{n=1}^{\infty }{\cap }_{k=n}^{\infty }{A}_k$ is called the limit inferior of the sequence ${\left\{A_n\right\}}_{n=1}^{\infty }$ and is usually denoted by $\text{lim}\text{inf}{A}_n$ or $\underset{¯}{lim}{A}_n$. We prefer the notation $\left\{A_n\mathrm{a}.\mathrm{b}.\mathrm{f}.\mathrm{o}\right\}$ (a.b.f.o means “all but finitely often”). Elementary symbol manipulation may be used to prove that $\underset{¯}{lim}{A}_n\subset \overline{lim}{A}_n$. It is easier to note, however, that if $\omega$ belongs to all but finitely many $A_n$‘s it must necessarily belong to an infinite number of them. The above fact is just one of the many similarities between lim sups and lim infs of sets, on the one hand, and of real numbers, on the other (recall that $lim{inf}_{n\to \infty }{a}_n\le lim{sup}_{n\to \infty }{a}_n$). Likewise $\text{lim}{inf}_{n\to \infty }{a}_n$ and $lim{sup}_{n\to \infty }{a}_n$ must both exist, that is,

$$-\infty \le liminf{a}_n\le limsup{a}_n\le \infty ,$$

as must $\underset{¯}{lim}{A}_n$ and $\overline{lim}{A}_n$, with

$$\varphi \subset \underset{¯}{lim}{A}_n\subset \overline{lim}{A}_n\subset \mathrm{\Omega }.$$

If $\left\{A_n\mathrm{a}.\mathrm{b}.\mathrm{f}.\mathrm{o}\right\}=\left\{A_n\mathrm{i}.\mathrm{o}.\right\}$, the sequence $\left\{A_n\right\}$ is said to have a limit, which we define to be the common value of $\left\{A_n\mathrm{a}.\mathrm{b}.\mathrm{f}.\mathrm{o}\right\}$ and $\left\{A_n\mathrm{i}.\mathrm{o}.\right\}$ and denote by ${lim}_{n\to \infty }{A}_n$ (note, again, the analogy with real sequences).

A useful dual relation between these two sets is

$${\left(\overline{lim}{A}_n\right)}^c=\underset{¯}{lim}{A}_n^c,$$

and

$${\left(\underset{¯}{lim}{A}_n\right)}^c=\overline{lim}{A}_n^c$$

where $A^c$ denotes the complement of the set A. Here is an informal proof of the first of these two facts: $\omega \in \underset{¯}{lim}{A}_n^c$ iff $\omega$ belongs to all but finitely many $A_n^c$‘s iff $\omega \in$ just a finite number of the $A_n$‘s iff $\omega \notin \overline{lim}{A}_n$ iff $\omega \in {\left(\overline{lim}{A}_n\right)}^c$.

A few examples should help familiarize the reader with the above notions: the second and the third are taken from [2]:

Example 1. If $A_1\subset A_2\subset \dots ,$ then $\overline{lim}{A}_n=\underset{¯}{lim}{A}_n={\cup }_{n=1}^{\infty }{A}_n$. Likewise, if $A_1\supset A_2\supset A_3\supset \dots$, then $\overline{lim}{A}_n=\underset{¯}{lim}{A}_n={\cap }_{n=1}^{\infty }{A}_n$.

Example 2. If $A_{2n-1}=\left(-\frac{1}{n},1\right]$ and $A_{2n}=\left(-1,\frac{1}{n}\right]$, then $\underset{¯}{lim}{A}_n=\left\{0\right\}$ and $\overline{lim}{A}_n=\left(-1,1\right]$.

Example 3. if $A_n$ is the unit circle with center at $\left(\frac{{\left(-1\right)}^n}{n},0\right)$, then

$$\underset{¯}{lim}{A}_n=\left\{\left(x,y\right):x^2+y^2<1\right\}$$

and

$$\overline{lim}{A}_n=\left\{\left(x,y\right):x^2+y^2\le 1\right\}\backslash \left\{\left(0,1\right),\left(0,-1\right)\right\}.$$

In what follows, the set $\mathrm{\Omega }$ will be taken to be the sample space (or set of possible realizations) of a random experiment (one whose outcome cannot be predicted in advance). We shall assume that each subset of $\mathrm{\Omega }$ that we encounter is $\mathit{\text{measurable}}$. In other words, each set $A$ will be assumed to belong to the sigma algebra$\mathcal{A}$ of events, which is a class of subsets of $\mathrm{\Omega }$ satisfying the conditions

• $\varphi \in \mathcal{A}$

• If $A$$\in \mathcal{A}$, then $A^c\in \mathcal{A}$ and

• If $A_1,A_2,\dots \in \mathcal{A}$, then ${\cup }_{n=1}^{\infty }{A}_n\in \mathcal{A}$.

This restriction ensures that sets such as $\overline{lim}{A}_n$ and $\underset{¯}{lim}{A}_n$ are themselves measurable, so that we may meaningfully talk of their probabilities $P\left\{A_n\mathrm{i}.\mathrm{o}.\right\}$ and $P\left\{A_n\mathrm{a}.\mathrm{b}.\mathrm{f}.\mathrm{o}\right\}.$ We next move on to a key concept in probability:

Definition: The sequence of events ${\left\{A_n\right\}}_{n=1}^{\infty }$ will be said to be independent, if for each finite subcollection $A_{n_1},A_{n_2},\dots ,A_{n_k}$,

$$P\left(A_{n_1}\cap A_{n_2}\cap \dots \cap A_{n_k}\right)=P\left(A_{n_1}\right)\cdot P\left(A_{n_2}\right)\cdot \dots \cdot P\left(A_{n_k}\right).$$

Stated informally, this means that the occurrence (or nonoccurrence) of any finite subcollection $\left\{A_{n_1},A_{n_2},\dots ,A_{n_k}\right\}$ does not affect the probability of occurrence of another disjoint collection $\left\{A_{m_1},A_{m_2},\dots ,A_{m_{\mathrm{\ell }}}\right\}$.

The events ${\left\{A_n\right\}}_{n=1}^{\infty }$ that represent the successive outcomes of an infinite coin-tossing experiment are usually assumed, on intuitive and empirical grounds, to be independent. We shall make the same assumption regarding Sue’s successive choices ${\left\{B_n\right\}}_{n=1}^{\infty }$ of a keyboard’s key.

The Borel-Cantelli lemma is a two-pronged theorem, which asserts that the probability of occurrence of an infinite number of the independent events ${\left\{A_n\right\}}_{n=1}^{\infty }$ is zero or one:

Theorem 2.1.(The Borel-Cantelli lemma, [3, 4]).

1. If ${\left\{A_n\right\}}_{n=1}^{\infty }$is any sequence of events, then${\sum }_{n=1}^{\infty }P\left(A_n\right)<\infty$implies that$P\left(A_n\mathrm{i}.\mathrm{o}.\right)=0$.

2. If${\left\{A_n\right\}}_{n=1}^{\infty }$is an independence sequence, then$P\left(A_n\mathrm{i}.o.\right)$equals 0 or 1 according as the series${\sum }_{n=1}^{\infty }P\left(A_n\right)$converges or diverges.

The following lemma can be proved using elementary properties of probability measures:

Lemma 2.2.If${\left\{A_n\right\}}_{n=1}^{\infty }$is an increasing (decreasing) sequence of events then${lim}_{n\to \infty }P\left(A_n\right)=P\left({\cup }_{n=1}^{\infty }{A}_n\right)\left[P{\cap }_{n=1}^{\infty }{A}_n\right].$

Proof of Theorem 2.1

1. For any $n$, we note that

   $$P\left(A_n\mathrm{i}.\mathrm{o}.\right)\le P\left({\cup }_{k\ge n}{A}_k\right)\le \sum _{k=n}^{\infty }P\left(A_k\right)$$

   On letting $n\to \infty$, we see that

   $$P\left(A_n\mathrm{i}.\mathrm{o}.\right)\le \underset{n\to \infty }{lim}\sum _{k=n}^{\infty }P\left(A_k\right)=0,$$

   proving part (a).

2. We shall prove that $P\left(A_n^c\mathrm{a}.\mathrm{b}.\mathrm{f}.\mathrm{o}\right)=0$. Let $m,n\left(m\ge n\right)$ be arbitrary. Note that

   $$P\left({\cap }_{k=n}^m{A}_k^c\right)=\prod _{k=n}^{m}P\left(A_k^c\right)=\prod _{k=n}^m\left(1-P\left(A_k\right)\right)\le exp\left\{-\sum _{k=n}^{m}P\left(A_k\right)\right\},$$

   where the last inequality follows from the fact that $1-x\le e^{-x}\left(x\ge 0\right)$. Lemma 2.1 now gives us that

   $$\underset{m\to \infty }{lim}P\left(\underset{k=n}{\overset{m}{\cap }}{A}_k^c\right)=P\left(\underset{k=n}{\overset{\infty }{\cap }}{A}_k^c\right)=0\forall n,$$

   which proves that

   $$P\left(A_n^c\mathrm{a}.\mathrm{b}.\mathrm{f}.\mathrm{o}\right)\le \sum _{n=1}^{\infty }P\left(\underset{k=n}{\overset{\infty }{\cap }}{A}_K^c\right)=0,$$

   proving the result.

As seen by the dates on Refs. [3, 4], the Borel-Cantelli lemmas are classical, and now part of virtually all graduate level books on Probability such as [2]. Since then, for over 100 years, the literature on the lemmas has focused on weakening the independence requirement in the second lemma, or looking at more complicated probability models that yield the same conclusions. See for example [5, 6, 7]. What distinguishes this work from these and others is that we provide a very down-to-earth application that forces the reader to come to terms with the notions of independence and infinity, as opposed to the finite samples one has in statistical situations. It is a paper that we feel can cause amusement, astonishment, false disbelief, and, ultimately, understanding. With this backdrop, we are now in a position to start establishing the claim made at the beginning of this chapter:

Corollary 2.3.If Sue types indefinitely, by successively and independently choosing one of the$N$available keys, then any specific work containing a total of$M$characters (including all the blanks, of course) will be typed by her indfinitely often, with a probability of 1.

Proof. Let $A_1$ be the event that Sue’s first $M$ random choices lead to the work being typed correctly. It is clear that $P\left(A_1\right)=\left(\frac{1}{N^M}\right)$. Similarly, let $A_2$ denote a successful completion of the task between the ${\left(M+1\right)}^{\mathrm{st}}$ and ${\left(2M\right)}^{\mathrm{th}}$ keystrokes. In general, $A_n$ denotes the completion of a flawless job between ${\left(\left(n-1\right)M+1\right)}^{\mathrm{st}}$ and the ${\left(\mathit{nM}\right)}^{\mathrm{th}}$ random strokes. It is evident that $P\left(A_n\right)=\left(\frac{1}{N^M}\right)\left(n\ge 1\right)$ and that the sequence ${\left\{A_n\right\}}_{n=1}^{\infty }$ is independent. Since ${\sum }_{n=1}^{\infty }P\left(A_n\right)={\sum }_{n=1}^{\infty }\left(\frac{1}{N^M}\right)=\infty ,$ it follows by part (b) of the Borel-Cantelli lemma that $P\left(A_n\mathrm{i}.\mathrm{o}.\right)=1$. Since the probability that the work is typed correctly infinitely often is at least as large as $P\left(A_n\mathrm{i}.\mathrm{o}.\right)$, the proof is complete. (Notice how the events ${\left\{A_n\right\}}_{n=1}^{\infty }$ are defined using disjoint blocks; this guarantees their independence.)

Lemma 2.4.If$P(C_n$) = 1 (n = 1,2,…), then$P\left({\cap }_{n=1}^{\infty }{C}_n\right)=1$.

Proof: Boole’s inequality states that

$$P\left({\cap }_{k=1}^n{C}_k\right)\ge \sum _{k=1}^{n}P\left(C_k\right)-\left(n-1\right).$$

Thus $P\left({\cap }_{k=1}^n{C}_k\right)=1$ for each $n$. The required conclusion is obtained on letting $n\to \infty ,$ and using Lemma 2.2.

Corollary 2.5.If Sue types indefinitely, then every piece of writing (of any finite length whatsoever; published, unpublished, or yet to be written by yet unborn individuals; meaningful or gibberish) will be typed by her, infinitely often each, with a probability of 1.

Proof. Denote the works by $B_1,B_2,.\dots$, and set $A_n=\left\{B_n\mathrm{i}.\mathrm{o}.\right\},\left(n=1,2,\dots \right).$ By Lemma 2.2, $P\left(A_n\right)=1$ for each $n$ and thus, by Lemma 2.4, $P\left({\cap }_{n=1}^{\infty }{A}_n\right)=1$, as claimed. (Note: this implies that the probability that some work is typed finitely often (or never) is zero.)

Example 4. (Statistical tests of hypotheses) If a fair coin is tossed infinitely often, a sequence of ${10}^6$ consecutive heads will appear infinitely often with probability 1.

Now, if a coin (of unknown origin) were tossed a million times, and a head appeared each time, the “null” statistical hypothesis

$$H_0:\text{The}\text{coin}\text{is}\text{fair}\left(p=1/2\right)$$

would be summarily rejected at most conventional (5, 1, 0.00001%) levels of significance. The point to note, however, is that such “extreme” and “erratic” behavior will be exhibited on an infinite number of occasions by any fair coin (and by all coins with $P\left(H\right)>0),$ with a probability of 1.

Similarly, if a fair coin is tossed infinitely often, an $n$-long alternating sequence $\mathit{\text{HTHT}}\dots \mathit{HT}$ ($n$ is arbitrary) will appear infinitely often, almost certainly. This fact may be compared with the conclusion of a standard nonparametric statistical procedure, the run test: the fair coin hypothesis would be vigorously rejected, using this test, if a large number of coin tosses yielded an alternating sequence of heads and tails.

3. A probability model for infinite coin tossing

In the above discussion, we often concluded that a particular event (e.g., Hamlet is typed infinitely often) occurred with probability 1. One fundamental question that we did not address, however, was the following: just what probability model describes infinite coin tossing or simian typewriting? Put another way, what are the sample spaces associated with these two experiments? And what exactly is the probability of an event defined to be? We realize then, in retrospect, that we had put the cart before the horse; various events were shown to have probability 1, by assuming the existence of a logically consistent probability (measure) on a sample space that had not been fully described. This practice is fairly standard in the teaching of probability; for example, sequences ${\left\{X_n\right\}}_{n=1}^{\infty }$ of independent and identically distributed (i.i.d.) random variables are often introduced as mathematical objects before their existence is proved, using Kolmogorov’s famous Consistency Theorem. Such an approach is often beneficial; as Billingsley [8] wrote, “It is instructive… to see the show in rehearsal as well as in performance.”

We shall start by noting that three tosses of a fair coin lead to the eight-point sample space

$$\mathrm{\Omega }=\left\{\mathit{HHH},\mathit{HHT},\mathit{HTH},\mathit{HTT},\mathit{THH},\mathit{THT},\mathit{TTH},\mathit{TTT}\right\}$$

It seems reasonable to assign probability 1/8 to each of these eight points; thus the probability $P\left(A\right)$ of any subset $A$ may be defined by

$$P\left(A\right)=\frac{\text{number}\text{of}\text{points}\text{in}A}{8}$$

Our analysis is thus complete, and can easily be extended to any finite number of coin tosses. The situation gets rapidly more complicated if the coin is tossed endlessly. This experiment cannot be conceived, carried out, or justified “in practice,” and our neat conclusions would be rendered meaningless if we were unable to mathematically model our procedure. Happily, however, this is not the case. We simply let

$$\mathrm{\Omega }=\left\{\omega :\omega \text{is}\text{an}\text{infinite}\text{sequence}\text{of}{\mathrm{H}}^{\prime }\mathrm{s}\text{and}{\mathrm{T}}^{\prime }\mathrm{s}\right\}$$

$$=\left\{\omega :\omega \text{is}\text{an}\text{infinite}\text{sequence}\text{of}{1}^{\prime }\mathrm{s}\text{and}{0}^{\prime }\mathrm{s}\right\}$$

A typical element of $\mathrm{\Omega }$ might be $\omega =0010011\dots$. It is well known (and easily proved) that $\mathrm{\Omega }$ is an uncountable set. It seems reasonable, then, to assign probability zero to each sample point.

The next step is crucial. We identify each element of $\mathrm{\Omega }$ with the real number in the interval [0,1] that has the same binary expansion. For example, the sample outcome THTHTH … is identified with the real number 0.01010101 … which equals

$$\frac{0}{2^1}+\frac{1}{2^2}+\frac{0}{2^3}+\frac{1}{2^4}+\dots =\frac{1}{3}.$$

A problem arises immediately: Numbers of the form $k/2^n$, where $k$ and $n$ are positive integers, do not have a unique binary representation. In other words, two different sample outcomes such as HTTTTT… and THHHH… would correspond to the same real number 1/2 (since 1/2 = 0.0111… = 0.100…), and the correspondence between $\mathrm{\Omega }$ and [0,1] would not, consequently, be one-to-one. We note, however, that numbers of the form $k/2^n$ constitute a denumerable set, and that there are two sample outcomes that correspond to each such number. If one, but not both, of each of these outcomes were to be removed from $\mathrm{\Omega }$, we would be left with a one-to-one map from a censored sample space ${\mathrm{\Omega }}^{\prime }$ onto [0,1]. Moreover, our assumption regarding individual sample points forces $P\left(\mathrm{\Omega }\backslash {\mathrm{\Omega }}^{\prime }\right)$ to equal zero. Thus, if a set of zero probability is thrown out from the original sample space, we may let $\mathrm{\Omega }=\left[0,1\right]$ and derive great satisfaction from the knowledge that this would not change the answer to any of our probability calculations.

It is possible to show, in a somewhat non-rigorous fashion (i.e., without using much measure theory), or rigorously, by introducing Lebesgue measure, that infinite coin tossing is mathematically equivalent to choosing a number randomly from the interval [0,1]. It can be shown, in a completely analogous way, that infinite random typewriting is equivalent to the single random choice of a number in [0,1]. We need of course, to consider the $N$-ary representation of numbers in [0,1], instead of their binary expansion (where $N$ ithe number of typewriter keys). However, we shall not do so here.

Example 5. (Random Numbers) Let the random variable $X$ denote the random choice of a number from [0,1]. Then

$$P\left(X\text{is}\text{rational}\right)=\sum _{n=1}^{\infty }P\left(X=r_n,\right)$$

where $r_n$ is the $n$‘th rational. Since, $P\left(X=r_n\right)=0$ for each $n$, we have that

$$P\left(X\text{is}\text{rational}\right)=0.$$

This result may be compared with a mundane fact of “reality”: If a person, computer, pointer, or random number generator were asked to choose $X$, limitations of measurement accuracy (or decimal point restrictions) would systematically exclude irrational X’s, leading to the “conclusion” that

$$P\left(X\text{is}\text{rational}\right)=1!$$

We would like to next state a thrilling result, called Borel’s law of normal numbers [3]: A number in [0,1] is said to be normal, if its decimal representation has, asymptotically, an equal frequency of the digits 0 through 9:

$$\underset{n\to \infty }{lim}\left\{\frac{\text{the}\text{number}\text{of}\text{times}j\text{appears}\text{in}\text{the}\text{first}n\text{digits}\text{of}\mathrm{its}\text{decimal}\text{expansion}}{n}\right\}=\frac{1}{10}$$

for each $j=0,1,2,\mathrm{\dots .9}$. Borel’s law states that

$$P\left(X\text{is}\text{normal}\right)=1,$$

which is somewhat surprising, since it is awfully hard to think of a single number that is normal (the number 0.012345678910111213…, obtained by writing each integer successively, is known to be normal; the proof is not trivial).

The Borel-Cantelli lemma yields several consequences that may, at first glance, seem to contradict Borel’s normal number law:

Almost all the numbers in [0,1] (i.e., all except some with zero Lebesgue measure) have decimal expansions that contain infinitely many chains of length 1000, say, that contain no numbers except 2,3, and 4. The nice part is, of course, that almost all of these numbers are normal as well, and so on.

The moral of the Borel-Cantelli lemma should, by now, be quite clear: “The realization of a truly random infinite procedure will, with probability one, contain infinitely many segments that exhibit extreme ‘non-randomness’, of all sizes, patterns and intensities.” The Borel-Cantelli lemma is, after all, a limit theorem of probability, and a quote from the classic treatise of Gnedenko and Kolmogorov [9] might be in order as well: “In reality, however, the epistemological value of the theory of probability is revealed only by limit theorems. Moreover, without limit theorems, it is impossible to understand the real content of the primary concept of all our sciences—the concept of probability.”

4. Conclusions and future developments

The main results of this chapter, accessible to a second-year undergraduate, are Corollaries 2.3 and 2.5. They follow from the Borel-Cantelli lemmas and Boole’s inequality, respectively. Corollary 2.3 states that in an infinite sequence of keystrokes, any fixed-length “work” appears infinitely often with probability 1. Most undergraduates that the author has taught have great difficulty believing this fact, since most statistical tests, for example, are based on finite samples. Corollary 2.5 goes one step further, proving that every finite-length piece of work, even those yet unwritten, will each appear infinitely often with probability 1. The undergraduate reader will undoubtedly appreciate the “power of infinity” on reading this chapter, while graduate students will enjoy a nonpractical yet deep application of the Borel-Cantelli lemmas.

Example 4 makes a contrast between the finite situation and the infinite one. An important practical problem in this regard would be to use Poisson approximations as in [10] to find the approximate probability that a specific work occurs $x$ times in $n$ keystrokes and to use this process as the basis of a statistical test for randomness.