Proving the Kochen-Stone lemma using the Paley-Zygmund inequality

Question

I am trying to understand a proof to a lemma by Kochen and Stone which appears here, using the Paley-Zygmund inequality.

I'll repeat the proof in a detailed manner, and explain what bothers me about it.

Lemma (Kochen-Stone). $\ $ Let $A_n$ be a sequence of events with $\sum\mathbb{P}(A_n)=\infty$ and \begin{equation*} \liminf_{k\to\infty}\frac{\sum_{1\le m,n \le k}\mathbb{P}(A_m\cap A_n)}{\left(\sum_{n=1}^k\mathbb{P}(A_n)\right)^2}<\infty \end{equation*} then, there is a positive probability that $A_n$ occur infinitely often.

Proof (partial). $\ $ Fix $\ell<k$. Let $X=\sum_{n=\ell}^{k}1_{A_n}$; it follows that \begin{equation*} \mathbb{E}(X)=\sum_{n=\ell}^{k}\mathbb(A_n) \end{equation*} and \begin{equation*} \mathbb{E}(X^2)=\sum_{\ell\le m,n \le k}\mathbb{P}(A_n\cap A_m). \end{equation*}

Using Paley-Zygmund inequality for $\theta=0$ (it's not mentioned in the wikipedia page, but the inequality holds for $\theta=0$ as well), we obtain \begin{eqnarray*} \mathbb{P}\left(\bigcup_{n=\ell}^{k}A_n\right) &=& \mathbb{P}(X>0)\\ &\ge& \frac{\left(\sum_{n=\ell}^{k}\mathbb{P}(A_n)\right)^2} {\sum_{\ell\le m,n \le k}\mathbb{P}(A_n\cap A_m)}\\ &\ge& \frac{\left(\sum_{n=1}^{k}\mathbb{P}(A_n) -\sum_{n=1}^{\ell-1}\mathbb{P}(A_n)\right)^2} {\sum_{1\le m,n \le k}\mathbb(A_n\cap A_m) -\sum_{1\le m,n < \ell}\mathbb(A_n\cap A_m)} \end{eqnarray*}

Now, it holds that $\mathbb{P}(A_n\text{ occurs i.o.}) = \lim_{\ell\to\infty}\lim_{k\to\infty}\mathbb{P}\left(\bigcup_{n=\ell}^{k}A_n\right)$; however, I can't see how I can bound that probability away from 0. Am I missing some minor detail here?

Answer 1

Here's a rough answer to your question. We have

$$ \frac{\left(\sum_{n=1}^{k}\mathbb{P}(A_n) -\sum_{n=1}^{\ell-1}\mathbb{P}(A_n)\right)^2} {\sum_{1\le m,n \le k}\mathbb{P}\mathbb(A_n\cap A_m) -\sum_{1\le m,n < \ell}\mathbb{P}\mathbb(A_n\cap A_m)}\geq \frac{\left(\sum_{n=1}^{k}\mathbb{P}(A_n) -\sum_{n=1}^{\ell-1}\mathbb{P}(A_n)\right)^2} {\sum_{1\le m,n \le k}\mathbb{P}\mathbb(A_n\cap A_m)} $$

Fix $l \in \mathbb{N}_1$. Since $\lim_{k \rightarrow \infty}\sum_{n = 1}^k \mathbb{P}(A_n) = \infty$, by assumption, if $k$ is sufficiently large, $$ \left(\sum_{n=1}^{k}\mathbb{P}(A_n) -\sum_{n=1}^{\ell-1}\mathbb{P}(A_n)\right)^2 \approx \left(\sum_{n=1}^{k}\mathbb{P}(A_n)\right)^2 $$

So if $k$ is sufficiently large, $$ \frac{\left(\sum_{n=1}^{k}\mathbb{P}(A_n) -\sum_{n=1}^{\ell-1}\mathbb{P}(A_n)\right)^2} {\sum_{1\le m,n \le k}\mathbb{P}\mathbb(A_n\cap A_m)} \approx \frac{\left(\sum_{n=1}^{k}\mathbb{P}(A_n)\right)^2} {\sum_{1\le m,n \le k}\mathbb{P}\mathbb(A_n\cap A_m)} = \frac{1}{\frac{\sum_{1\le m,n \le k}\mathbb{P}\mathbb(A_n\cap A_m)}{\left(\sum_{n=1}^{k}\mathbb{P}(A_n)\right)^2}} $$

Suppose $$ \liminf_{k\to\infty}\frac{\sum_{1\le m,n \le k}\mathbb{P}(A_m\cap A_n)}{\left(\sum_{n=1}^k\mathbb{P}(A_n)\right)^2} = c < \infty $$

This means that no matter how large $k$ is, there is always some $k' \geq k$, such that $$ \frac{\sum_{1\le m,n \le k'}\mathbb{P}(A_m\cap A_n)}{\left(\sum_{n=1}^{k'}\mathbb{P}(A_n)\right)^2} \approx c $$

So for infinitely many $k$'s

$$ \mathbb{P}\left(\bigcup_{n=\ell}^{k}A_n\right) \geq \frac{1}{\frac{\sum_{1\le m,n \le k}\mathbb{P}\mathbb(A_n\cap A_m)}{\left(\sum_{n=1}^{k}\mathbb{P}(A_n)\right)^2}} \approx \frac{1}{c} $$

Since $\mathbb{P}\left(\bigcup_{n=\ell}^{k}A_n\right)$ is decreasing in $k$, we have, approximately, $$ \lim_{k \rightarrow \infty}\mathbb{P}\left(\bigcup_{n=\ell}^{k}A_n\right) \geq \frac{1}{c} $$

Since $l$ was arbitrary, $$ \lim_{l \rightarrow \infty}\lim_{k \rightarrow \infty}\mathbb{P}\left(\bigcup_{n=\ell}^{k}A_n\right) \geq \frac{1}{c} > 0 $$

Answer 2

Here is a proof from Rick Durrett's Probability.

Let $X_n = \sum_{k\le n} 1_{A_k}$, $Y_n = \frac{X_n}{E(X_n)}$, the Kochen-Stone lemma means $\limsup_{n\to\infty} \frac{1}{E(Y_n^2)}<\infty$. Here is an inequality we will use: $P(Y_n > a) \ge \frac{(1-a)^2}{E(Y_n^2)}$, here $a$ is a constant. This comes from the Paley-Zygmund inequality, we can easily prove it with Cauchy-Schwarz inequality. By Borel-Cantelli lemma, we have $P(A_k, i.o.) = 1$. Since $P(\cup_{m\ge n} Y_m) \ge \max_{m\ge n} P(Y_m)$, it follows that $P(\limsup Y_n)\ge \limsup P(Y_n)$. Thus

$1 = P(A_n,i.o.) \ge P(\limsup Y_n > a) \ge \limsup P(Y_n > a) \ge (1-a)^2 \frac{1}{E(Y_n^2)}$,

Which means $\limsup_{n\to\infty} \frac{1}{E(Y_n^2)} < \infty$.