I’m currently lecturing my first course at King’s, which builds measure theory from the ground up to the construction of the Lebesgue integral, along with some more probabilistic topics. In this second week, we have been discussing various matters related to the construction of sigma-algebras. It took me slightly by surprise that this ends up being the natural moment during an undergraduate’s progression through probability to introduce the Borel-Cantelli lemmas. It’s not hard to imagine a pedagogical schedule in which they appear earlier, but equally, one benefits from seeing them with a bit more mathematical experience, even if they are only very loosely related to the construction of the Lebesgue integral!
Anyway, I noticed that I have not written about these results on the blog before. There are a couple of neat applications that lie slightly beyond the remit (and time allowance) of the lecture course, so they are presented at the end.
Context – events holding eventually and infinitely often
Recall that (in the notation of probability spaces) a sigma-algebra provides a set of events for which it is meaningful and consistent to define a probability measure. This is extremely uncontroversial in the setting where the set of outcomes is finite, but thornier in the setting where is uncountable, for example [0,1] or . The key axiom for sigma-algebras involves countable unions. If is a sequence of events in , we must also have .
Since the axioms also demand that is closed under taking complements, it only takes a few steps to show that countable intersections are also valid, ie also. It is uncontroversial to note that
The main initial motivation for considering the events are that they lie between the intersection and the union in terms of containment.
- ‘Infinitely often’ is relatively uncontroversial, just meaning ‘for infinitely many values of n’.
- ‘Eventually’ is less clear on an initial reading. Perhaps ‘eventually always’ would be better? [And closer to the title of this blog!] The meaning is ‘always, except for finitely many n’, which implies that there is some threshold N such that it holds for all n>N.
- In set notation, infinitely often (or i.o.) means that must hold for every n, and so the event .
- Similarly, eventually means that there must be an n for which holds, so the event .
We end up with the richer containment sequence
These individual containment relations may not be obvious a priori in this form. Probably the most clear is the central containment, that if an holds for all except finitely many n, then it holds for infinitely many n. The right-most says that if it holds infinitely often, then it holds at least once. For the left-most containment, note that is literally the same as the n=1 case of , so taking a union over other values of n only increases the set.
It’s also worth thinking about the complements. Note that and . Versions of these apply to eventually/i.o. also. In particular
So in any calculation or application, there is flexibility to study is this is more convenient. As we will see, it makes sense to focus on whichever of has vanishing probabilities as .
Comment: It is standard to write , and . I am happy to admit I get these confused with non-vanishing probability, and prefer to stick to eventually/i.o. or the full union/intersection statements for safety!
The Borel-Cantelli lemmas establish some conditions under which the event almost surely holds, or almost surely doesn’t hold. We’ll state them now:
BC1: If , then .
BC2: If and the events are independent, then .
Proof of BC1: Since for every $n$, we have
Comment: we could also introduce the random variable which counts how many events occur, ie . Then , and the given condition is equivalent to , which certainly implies . Indeed, it’s reasonable to think of BC1 as a first-moment result, with BC2 as (sort of) a second-moment result, and this is reflected in the comparative complexity of the two proofs.
Proof of BC2: As discussed, it is equivalent to show that . To do this, we study the intersections of the complements, whose probabilities are tractable using independence:
We have assumed that for each n, and so we obtain
But since is an increasing sequence of events, so taking a union over n is particularly natural. Precisely, by continuity of measure, we have
Comment: the independence condition is certainly necessary, as otherwise one can have situations where . For example, with , consider , for which , whose sum diverges, while clearly .
Classic examples: the famous ‘infinite monkey theorem’, relatively well-known outside the realm of theoretical probability, asserts that a monkey typing randomly at a keyboard for long enough will eventually type the complete works of William Shakespeare. Other standard examples involve independent with probabilities decaying at various speeds. The latter do have some overlap with the slightly less standard examples presented below.
Example – generating random permutations
Consider a sequence of random permutations where is a permutation of . We construct these iteratively as follows: is the identity (ie the only permutation of one element!); then for each , define from by inserting element at a uniformly-chosen position in .
We ask the question whether this gives a well-defined limiting permutation on . A necessary condition for this is that the first element is eventually constant. But in fact the events are independent, and each others with probability , and so
On reflection, each has the uniform distribution on , permutations of . So our result is consistent with the idea that one cannot construct a uniform random permutation on an infinite set.
Now, alternatively, suppose the new element is added at place where are IID random variables. (The truncation is just to prevent pathologies like trying to add the new entry in ‘place -6’.) Then
and since , BC1 shows that the first element changes only finitely often. A similar argument applies for the second element, and the third element, and so on. Consequently, almost surely we have a well-defined pointwise limit permutation . This is known as the Mallows Permutation on the integers, and is one of the more popular models for a random permutation on an infinite set, with lots of interesting properties. I supervised an undergraduate research project on this model over Summer 2022, and will write more when time allows.
Example – well-separated random integers
The final example is a toy version of a construction I’ve been working on recently regarding subsets of the vertices of a graph which ‘trap’ random walk on that graph.
Suppose we are trying to colour some positive integers randomly, so that the coloured integers are infinite, but also asymptotically sparse. We also do not want pairs of coloured integers to be close together. Let’s say that two integers are close if .
Now, suppose we colour each integer green independently with probability . Then, whenever we have two integers which are close, and coloured green, we re-colour them both red.
We would like to prove that infinitely many integers are coloured green. Let . Using BC2, we know that almost surely, infinitely many are coloured with some colour, and it seems implausible that many would be close. However, the events are not independent, so one cannot apply BC2 directly to these. However, we can study instead . We can bound these probabilities as
and apply BC1 to show . Then, since , we obtain , as required.