Quantitative Borel-Cantelli Lemma

Everyone knows and loves the Borel-Cantelli lemma: it is widely used, intuitive and has a cute proof. Let’s recall it.

Borel-Cantelli Lemma. Let be a measure space, and a sequence of measurable sets such that . Then the points of that lie in infinitely many form a set of measure zero.

Proof. We present the usual slick proof of the lemma, and postpone intuition until the development of a quantitative statement. Define to be the set of points lying in infinitely many , and notice that . It follows that is measurable, and contained in each cofinite union . Now, , and the latter goes to zero as , because converges. Thus , as claimed.

Alright, so the set of points lying in “very many” is “very small”. A natural quantitative question to ask at this point is: how small is the set of points lying in “moderately many” ? More precisely, if is the set of points lying in at least of the , and the set of points lying in exactly of the , can we get bounds on and , depending on ?

It seems plausible. If a point lies in at least of the sets , adding up all the seems to be “counting” at least times. Therefore, intuitively, should be at least , for each , which gives an upper bound on . Since is a subset of , the same bound applies.

This is consistent with the usual Borel-Cantelli lemma as , and indeed, in the finitary case, we have a

Counting lemma. Suppose is a finite set, endowed with the structure of a measure space , where is the counting measure (ie, is the number of elements in ). Let be subsets of , and define as above. Then

Proof. This is a very proof-friendly lemma. One may use induction on , or on the cardinality of , or even reason visually, by counting edges in an appropriate bipartite graph.

Since , we easily get, for each ,

.

The trouble with extending this analysis to general measure spaces is that, typically, has very little to do with the number of elements in , which at any rate might be infinite. In fact, are and even measurable in general? Fortunately, yes.

It suffices to establish measurability of all the , and the idea is just a finitary version of the argument expressing , above, as a union of intersections. Let be the (denumerable) set of -element subsets of . Obviously, if , then is measurable, whence is measurable. But that’s exactly .

But still, it isn’t clear how to adapt the proofs of the counting lemma to the general conjecture

.

Let’s take a look at the three straightforward proofs of the c.l. Two of them somehow rely on the “individuality” of each point: induction on the cardinality of proceeds by adding a point to some of the , and seeing how the sums change; and edge-counting reinterprets the sum of as a sum of certain functions (vertex degree) over the points. In a general measure space, there may be infinitely many points, and they may each have measure zero, so those lines of argument don’t look too appealing.

The third proof we had was induction on the number of , which isn’t exactly applicable, as there are denumerably many of them; but a standard move in analysis can help us here, namely, “try to ignore small things and see if simpler patterns emerge”. Since the sum converges, we know that not only do the individual become small as , but a cofinite set of them becomes small.

So let’s assume, for the moment, that there are only finitely many . Maybe later we can disregard the contributions of all but finitely many , and manage an “approximation by ” argument.

This looks tractable! For instance, if there are only and , we have

Obviously, and , while . Thus the conjecture holds when there are only two sets ; more than that, the relevant structures become obvious. What we should consider, instead of single points, is atoms of the -algebra generated by — which is just a fancy way of saying “regions of the Venn diagram of the “. More explicitly, the possible intersections , where each is either or its complement.

At this point we may even forget the complicated idea of induction (and the myriad ways in which a new can intersect the old ) and focus on proving an analogue of the counting lemma where the elements of are allowed to have “weights”, and subsets of are assigned the sum of the weights of their elements, instead of just their number. More precisely:

Weighted counting lemma. Let be a finite set, some of its subsets, and define as before. Let be a “weight function” on elements of , and for define . Then

First proof. One way to go is induction on the cardinality of : add a new guy in, call him , and say he’s in of the . Observe that the leftmost sum increases by ( for each that is in). Now, increases by , as does each of , while the other remain unchanged. Therefore, the middle and rightmost sums also increase by .

Second proof. Or we may take the graph-theoretic approach, defining a bipartite graph , the vertices of which are the elements of on one hand, and the sets on the other (P and Q, respectively). Add an edge between and of weight whenever . Calculate the total edge weight in two different ways to get equality between the leftmost and rightmost terms; equality between the middle and rightmost terms is straightforward.

Looking at the atoms of the -algebra generated by as “weighted elements” of the , w.c.l. trivially gives

Quantitative Borel-Cantelli (finite case). Let be measurable subsets of a measure space , and define as before. Then

.

Ideally, we should be able to take some sort of limit as and prove the general case. The more obvious way to do that is disregard all but finitely many , which introduces an arbitrarily small error in the term. However, and are sort of spread out over the , and truncating the latter series does not straightforwardly correspond to a truncation of the former.

We take our next clue from writing out, in full, the proof of quantitative B-C via w.c.l., the second proof in particular. The productive thing to do there was split up each along the , in the sense that

;

;

et cetera. So we try that now: let . Notice that except for , which has measure zero by the original Borel-Cantelli. (Henceforth we shall ignore and completely.) Since the are disjoint, we get , and, as the sum of all converges absolutely, we get

.

Hence, if we can prove the plausible-sounding statement

we’ll be halfway done. Here we’re so close to the finitary case that the same combinatorial argument works. Fix and recall that is the (denumerable) set of -element families of , for instance,

.

For , let . For fixed , all are disjoint, and their union is obviously , whence

.

Now, each is also the disjoint union of a few , namely, those for which ; and further, each is contained in exactly of the , one for each member of . Therefore,

.

This gets us half our theorem. The other half, as in the finite case, can be established more easily as follows. Since ,

On the other hand, it is clear that , the union being disjoint. It follows that , and so

.

Taking limits as in both inequalities above finally gets us the

Quantitative Borel-Cantelli Lemma. Let be a measure space, a family of measurable sets such that , and . Then

.

In particular, we have the bounds

.

Proof. We’ve done everything but make explicit the limit in the previous line. It’s just a consequence of

.