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?


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

  • $\begingroup$ 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. $\endgroup$
    – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.