# Hopefully Interesting

## March 14, 2008

### Quantitative Borel-Cantelli Lemma

Filed under: math.CA,motivated theorems — Pietro @ 12:00 pm
Tags: ,

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 $(X,\mathcal{M},\mu)$ be a measure space, and $(E_n)_{n\in\mathbb{N}}$ a sequence of measurable sets such that $\sum_{n\in\mathbb{N}} \mu(E_n) < \infty$. Then the points of $X$ that lie in infinitely many $E_n$ 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 $F_\infty$ to be the set of points lying in infinitely many $E_n$, and notice that $F_\infty = \bigcap_{n\in\mathbb{N}} \bigcup_{k\geq n} E_k$. It follows that $F_\infty$ is measurable, and contained in each cofinite union $\bigcup_{k\geq n} E_k$. Now, $\mu(\bigcup_{k\geq n}E_k) \leq \sum_{k\geq n} \mu(E_k)$, and the latter goes to zero as $n\to\infty$, because $\sum_{n\in\mathbb{N}} \mu(E_n)$ converges. Thus $\mu(F_\infty)=0$, as claimed. $\Box$

Alright, so the set of points lying in “very many” $E_n$ is “very small”. A natural quantitative question to ask at this point is: how small is the set of points lying in “moderately many” $E_n$? More precisely, if $F_k$ is the set of points lying in at least $k$ of the $E_n$, and $G_k = F_k \backslash F_{k+1}$ the set of points lying in exactly $k$ of the $E_n$, can we get bounds on $\mu(F_k)$ and $\mu(G_k)$, depending on $k$?

It seems plausible. If a point $x\in X$ lies in at least $k$ of the sets $E_n$, adding up all the $\mu(E_n)$ seems to be “counting” $x$ at least $k$ times. Therefore, intuitively, $\sum_{n\in\mathbb{N}} \mu(E_n)$ should be at least $k\cdot\mu(F_k)$, for each $k$, which gives an $O(1/k)$ upper bound on $\mu(F_k)$. Since $G_k$ is a subset of $F_k$, the same bound applies.

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

Counting lemma. Suppose $S$ is a finite set, endowed with the structure of a measure space $(S,2^S,\#)$, where $\#$ is the counting measure (ie, $\# A$ is the number of elements in $A$). Let $E_1,\ldots,E_N$ be subsets of $S$, and define $F_k, G_k$ as above. Then

$\sum_{n=1}^N \# E_n = \sum_{k=1}^N \# F_k = \sum_{k=1}^N k\cdot \# G_k$

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

Since $F_{k+1} \subseteq F_k$, we easily get, for each $m$,

$\sum_{n=1}^N \# E_n = \sum_{k=1}^N \# F_k \geq \sum_{k=1}^m \# F_k \geq m\cdot \# F_m \Longrightarrow \# F_m \leq \frac{1}{m} \sum_{n=1}^N \# E_n$.

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

It suffices to establish measurability of all the $F_k$, and the idea is just a finitary version of the argument expressing $F_\infty$, above, as a union of intersections. Let $\mathfrak{E}_k$ be the (denumerable) set of $k$-element subsets of $\{E_n : n\in\mathbb{N}\}$. Obviously, if $\mathcal{E} \in \mathfrak{E}_k$, then $\cap \mathcal{E}$ is measurable, whence $\bigcup_{\mathcal{E}\in\mathfrak{E}_k} \cap\mathcal{E}$ is measurable. But that’s exactly $F_k$.

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

$\sum_{n\in\mathbb{N}} \mu(E_n) = \sum_{k\in\mathbb{N}} \mu(F_k) = \sum_{k\in\mathbb{N}} k\cdot \mu(G_k)$.

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 $S$ proceeds by adding a point to some of the $E_n$, and seeing how the sums change; and edge-counting reinterprets the sum of $\# E_n$ 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 $E_n$, 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 $\sum_{n\in\mathbb{N}} \mu(E_n)$ converges, we know that not only do the individual $\mu(E_n)$ become small as $n\to\infty$, but a cofinite set of them becomes small.

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

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

$\begin{array}{rcl} \mu(E_1) + \mu(E_2) & = & \mu(E_1 \cup E_2) + \mu(E_1 \cap E_2) \\ & = & \mu((E_1 \cup E_2) \backslash(E_1 \cap E_2)) + 2\cdot\mu(E_1 \cap E_2). \end{array}$

Obviously, $F_1 = E_1 \cup E_2$ and $G_1 = (E_1 \cup E_2) \backslash (E_1 \cap E_2)$, while $F_2 = G_2 = E_1 \cap E_2$. Thus the conjecture holds when there are only two sets $E_1,E_2$; more than that, the relevant structures become obvious. What we should consider, instead of single points, is atoms of the $\sigma$-algebra generated by $E_1,\ldots,E_N$ — which is just a fancy way of saying “regions of the Venn diagram of the $E_n$“. More explicitly, the $2^N$ possible intersections $\tilde{E_1} \cap \ldots \cap \tilde{E_N}$, where each $\tilde{E_n}$ is either $E_n$ or its complement.

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

Weighted counting lemma. Let $S$ be a finite set, $E_1,\ldots,E_N$ some of its subsets, and define $F_k,G_k$ as before. Let $w : S \to \mathbb{R}$ be a “weight function” on elements of $S$, and for $A \subseteq S$ define $w(A) = \sum_{a\in A} w(a)$. Then

$\sum_{n=1}^N w(E_n) = \sum_{k=1}^N w(F_k) = \sum_{k=1}^N k\cdot w(G_k)$

First proof. One way to go is induction on the cardinality of $S$: add a new guy in, call him $s$, and say he’s in $m$ of the $E_n$. Observe that the leftmost sum increases by $m\cdot w(s)$ ($w(s)$ for each $E_n$ that $s$ is in). Now, $w(G_m)$ increases by $w(s)$, as does each of $F_1,\ldots,F_m$, while the other $F_k,G_k$ remain unchanged. Therefore, the middle and rightmost sums also increase by $m\cdot w(s)$. $\Box$

Second proof. Or we may take the graph-theoretic approach, defining a bipartite graph $G=P+Q$, the vertices of which are the elements of $S$ on one hand, and the sets $E_n$ on the other (P and Q, respectively). Add an edge between $s$ and $E_n$ of weight $w(s)$ whenever $s\in E_n$. 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. $\Box$

Looking at the atoms of the $\sigma$-algebra generated by $E_1,\ldots,E_N$ as “weighted elements” of the $E_n$, w.c.l. trivially gives

Quantitative Borel-Cantelli (finite case). Let $E_1,\ldots,E_N$ be measurable subsets of a measure space $X$, and define $F_k,G_k$ as before. Then

$\sum_{n=1}^N \mu(E_n) = \sum_{k=1}^N \mu(F_k) = \sum_{k=1}^N k\cdot \mu(G_k)$.

Ideally, we should be able to take some sort of limit as $N\to\infty$ and prove the general case. The more obvious way to do that is disregard all but finitely many $E_n$, which introduces an arbitrarily small error in the $\sum\mu(E_n)$ term. However, $F_k$ and $G_k$ are sort of spread out over the $E_n$, 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 $E_n$ along the $G_k$, in the sense that

$E_i \cap G_1 = E_i \cap \bigcap_{j\neq i}E_j^c$;

$E_i \cap G_2 = E_i \cap \bigcup_{j\neq i} \left( E_j \cap \bigcap_{k\neq i,j}E_j^c \right)$;

et cetera. So we try that now: let $E_{n,k} = E_n \cap G_k$. Notice that $E_n = \bigcup_{k\in\mathbb{N}}E_{n,k}$ except for $E_n \cap G_\infty$, which has measure zero by the original Borel-Cantelli. (Henceforth we shall ignore $F_\infty$ and $G_\infty$ completely.) Since the $G_k$ are disjoint, we get $\mu(E_n) = \sum_{k\in\mathbb{N}} \mu(E_{n.k})$, and, as the sum of all $\mu(E_n)$ converges absolutely, we get

$\sum_{n\in\mathbb{N}} \mu(E_n) = \sum_{n\in\mathbb{N}} \sum_{k\in\mathbb{N}} \mu(E_{n,k}) = \sum_{k\in\mathbb{N}} \sum_{n\in\mathbb{N}} \mu(E_{n,k})$.

Hence, if we can prove the plausible-sounding statement

$\sum_{n\in\mathbb{N}} \mu(E_{n,k}) = k\cdot\mu(G_k)$

we’ll be halfway done. Here we’re so close to the finitary case that the same combinatorial argument works. Fix $k$ and recall that $\mathfrak{E}_k$ is the (denumerable) set of $k$-element families of $E_n$, for instance,

$\mathfrak{E}_2 = \{ \ \{E_1,E_2\},\{E_1,E_3\}, \ldots \{E_i,E_j\}, \ldots\}$.

For $\mathcal{E}\in\mathfrak{E}_k$, let $E_{\mathcal{E},k} = \bigcap\mathcal{E}\cap G_k$. For fixed $k$, all $E_{\mathcal{E},k}$ are disjoint, and their union is obviously $G_k$, whence

$\sum_{\mathcal{E}\in\mathfrak{E}_k} \mu(E_{\mathcal{E},k}) = \mu(G_k)$.

Now, each $E_{n,k}$ is also the disjoint union of a few $E_{\mathcal{E},k}$, namely, those for which $E_n\in\mathcal{E}$; and further, each $E_{\mathcal{E},k}$ is contained in exactly $k$ of the $E_n$, one for each member of $\mathcal{E}$. Therefore,

$\sum_{n\in\mathbb{N}} \mu(E_{n,k}) = k \cdot \sum_{\mathcal{E}\in\mathfrak{E}_k} \mu(E_{\mathcal{E},k}) = k\cdot\mu(G_k)$.

This gets us half our theorem. The other half, as in the finite case, can be established more easily as follows. Since $G_k = F_k \backslash F_{k+1}$,

$\begin{array}{rcl}\sum_{k=1}^N k\cdot\mu(G_k) & = & (\mu(F_1) - \mu(F_2)) + 2\cdot (\mu(F_2) - \mu(F_3)) + \ldots + N\cdot(\mu(F_N) - \mu(F_{N+1}))\\ & = & \sum_{k=1}^N \mu(F_k) - N\cdot\mu(F_{N+1})\leq \sum_{k=1}^N \mu(F_k)\\ & \leq & \sum_{k\in\mathbb{N}} \mu(F_k).\end{array}$

On the other hand, it is clear that $F_k = \bigcup_{l\geq k} G_l$, the union being disjoint. It follows that $\mu(F_k) = \sum_{l\geq k} \mu(G_l)$, and so

$\sum_{k=1}^N \mu(F_k) = \sum_{k=1}^N k\cdot\mu(G_k) + N\cdot\sum_{k\geq N} \mu(G_k) \leq \sum_{k\in\mathbb{N}} k\cdot\mu(G_k)$.

Taking limits as $N\to\infty$ in both inequalities above finally gets us the

Quantitative Borel-Cantelli Lemma. Let $(X,\mathcal{M},\mu)$ be a measure space, $(E_n)_{n\in\mathbb{N}}$ a family of measurable sets such that $\sum_{n\in\mathbb{N}}\mu(E_n) < \infty$, $F_k = \{x\in X : x \textrm{ is in at least }k\textrm{ of the }E_n\}$ and $G_k =F_k\backslash F_{k+1}$. Then

$\sum_{n\in\mathbb{N}} \mu(E_n) = \sum_{k\in\mathbb{N}} \mu(F_k) = \sum_{k\in\mathbb{N}} k\cdot\mu(G_k)$.

In particular, we have the bounds

$\mu(G_k)\leq\mu(F_k) \leq \frac{1}{k}\sum_{n\in\mathbb{N}} \mu(E_n)$

$\lim_{k\to\infty}k\cdot\mu(F_k) = 0$.

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

$\lim_{N\to\infty}\sum_{k=1}^N k\cdot\mu(G_k) = \lim_{N\to\infty} \sum_{k=1}^N \mu(F_k) - N\cdot\mu(F_{N+1}) = \lim_{N\to\infty} \sum_{k=1}^N \mu(F_k)$. $\Box$