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

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?

$$\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$$

• Thanks for your nice answer. This is indeed rough, but it convinces me. I am looking now at Fatou's lemma, hoping it will help me make it more formal, or more elegant.
– Bach
Mar 29 '14 at 17:22

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$$.