Quantitative Borel-Cantelli
Published:
In this entry we discuss a stronger version of the Borel-Cantelli lemma. Recall the second Borel-Cantelli:
Theorem (Borel-Cantelli) Suppose that the sequence $\{A_n\}$ is independent and
\[\sum_{n=1}^{\infty} \mathbb{P}(A_n) = \infty .\]Then
\[\mathbb{P}\left(\limsup_{n} A_n \right) = 1.\]This result essentially says that under the independence assumption, infinitely many of the events $\{ A_n\}$ occur with probability one. A quantitative result here means having asymptotics for the number of events that indeed occur as we perform more experiments. We formulate now the precise result:
Theorem (Quantitative Borel-Cantelli): Suppose that the sequence $\{A_n\}$ is independent and
\[\sum_{n=1}^{\infty} \mathbb{P}(A_n) = \infty .\]Then
\[\dfrac{\sum_{k=1}^n 1_{A_k} }{\sum_{k=1}^n \mathbb{P}(A_k)} \to 1\]almost surely.
Intuitively we can think of this result in the following way: suppose the events $A_n$ happen over time (where the index $n$ represents the time evolution). For a sample $\omega$, we know that infinitely many of the events $A_n$ will occur, that is, $\sum_n 1_{A_n}(\omega) = \infty$. The above result says that up to time $m$, the fraction of events that we can expect to have happened is roughly $\dfrac{1}{n}\sum_{k=1}^m\mathbb{P}(A_k)$.
The strategy of the proof consists of two parts:
- We prove convergence in probability,
- We prove almost sure convergence along a subsequence, from which we upgrade the convergence.
Proof:
Define the sequence of random variables $X_n = 1_{A_n}$, and denote their corresponding sums by $S_n = X_1 + \dots + X_n$. As usual when proving convergence in probability, we plan to use Chebyshev’s inequality for the sums, hence we need to obtain its mean and bound its variance above. By linearity of the expectation, we can compute the expectation as
\[\mathbb{E}(S_n) = \sum_{k=1}^n \mathbb{E}(X_k) = \sum_{k=1}^n \int_\Omega 1_{A_n}(x) d\mathbb{P}(x) = \sum_{k=1}^n \mathbb{P}(A_n).\]On the other hand, since the events are independent, the random variables $X_n$ are uncorrelated, and hence we can compute their variance as
\[\operatorname{var}(S_n) = \sum_{k=1}^n \operatorname{var}(X_n) \leq \sum_{k=1}^n \mathbb{E}(X_k^2) = \sum_{k=1}^n \mathbb{E}(X_k) ,\]so $\operatorname{var}(S_n) \leq \mathbb{E}(S_n)$. We put this together in the Chebyshev’s inequality, which for any $\epsilon > 0$ yields
\[\mathbb{P}(\left| \dfrac{S_n}{\mathbb{E}(S_n)} - 1 \right| > \epsilon) = \mathbb{P}(\left| S_n -\mathbb{E}(S_n) \right| > \epsilon\mathbb{E}(S_n)) \leq \dfrac{\operatorname{var}(S_n)}{\epsilon^2\mathbb{E}(S_n)^2} \leq \dfrac{1}{\epsilon^2 \sum_{k=1}^n \mathbb{P}(A_n)} \to 0\]as $n\to \infty$. This proves the first part of the argument.
For the second part, we define the random index $n_k = \inf\{ n: \mathbb{E}(S_n)\geq k^2 \}$ and the random sum $T_k = S_{n_k}$. Note that $k^2 \leq \mathbb{E}(T_k) \leq k^2 + 1$, which together with the converngence in probability of $S_n$ imply that
\[\mathbb{P}(\left| T_k -\mathbb{E}(T_k) \right| > \epsilon\mathbb{E}(T_k)) \geq \dfrac{1}{\epsilon^2 k^2}.\]Thus, $\mathbb{P}(\left| T_k -\mathbb{E}(T_k) \right| > \epsilon\mathbb{E}(T_k))$ is summable, and so by Borel-Cantelli lemma, we have that $\mathbb{P}(\left| T_k -\mathbb{E}(T_k) \right| > \epsilon\mathbb{E}(T_k) \text{ i.o.}) = 0$. Since $\epsilon$ is arbitrary, we obtain that $T_k/\mathbb{E}(T_k) \to 1$ as $k\to\infty$. We will show that the convergence $S_n/\mathbb{E}(S_n)\to 1$ happens in the same set where $T_k/\mathbb{E}(T_k) \to 1$. Suppose $\omega \in \{T_k/\mathbb{E}(T_k) \to 1 \}$. Then, for any $n\geq 1$, there is $k\geq 1$ such that $n_k \leq n < n_{k+1}$, which implies that
\[\dfrac{T_{k}}{\mathbb{E}(T_{k+1})} \leq \dfrac{S_n}{\mathbb{E}(S_n)} \leq \dfrac{T_{k+1}}{\mathbb{E}(T_k)}\]Finally, note that for such $\omega$, one has $\dfrac{\mathbb{E}(T_k)}{\mathbb{E}(T_{k+1})}\to 1$ as $k\to\infty$ since
\[k^2 \leq \mathbb{E}(T_k)\leq \mathbb{E}(T_{k+1}) \leq (k+1)^2 + 1.\]This completes the proof. $\square$
It is important to remark that some of the ideas used here are quite fundamental: showing weaker convergence along subsequences, and then upgrading it using a Borel-Cantelli argument. It is also worth pointing out that in the context of Dynamical System, Borel-Cantelli and quantitative Borel-Cantelli have been extended in several different directions; we mention a few of them:
- Chernov and Kleinboch proved a Borel-Cantelli lemma for Gibbs measures in topological Markov chains and certain Anosov diffeomorphisms,
- Dolgopyat proved a version for sequences of balls in a uniformly partially hyperbolic setting,
- Kim proved a quantitative Borel-Cantelli result for 1-dimensional non-uniformly expanding maps (Liverani-Saussol-Vaienti maps), with respect to the invariant measure.
- Gouezel proved a similar but with respect to the Lebesgue measure.
- Gupta, Nicol and Ott proved a quantitative result for non-uniformly expanding 1-dimensional maps of the interval satisfying certain distortion condition.
- Carney and Nicol proved a quantitative result for non-integrable observables with respect to dynamics on manifolds and absolutely continuous measures.
Leave a Comment