# Dependence and second Borel-Cantelli lemma.

I'll put the problem and then I'll explain my problem.

Problem: Let ${A_n}$ be events such as

$\operatorname{Cov}(I_{A_i},I_{A_j})=E[I_{A_i}I_{A_j}]-E[I_{A_i}]E[I_{A_j}]\leq 0,\ \forall i\neq j\tag{1}$

If $\sum P(A_i)=\infty$ then $P[\lim \sup A_n]=1$.

Answer: By (1) we have that $\operatorname{Cov}(I_{A^c_i},I_{A^c_j})\leq 0$ too. So $P(\lim \inf A_n^c)=P(\lim \bigcap A_n^c)=\lim P(\bigcap A_n^c)\overset{Q!} {\leq} \lim \prod P(A_n^c)= \lim \prod (1-P(A_n))\leq \lim e^{-\sum P(A_n)}=0$

The detail is that in the inequality marked with a "Q!" I used that $P(\bigcap A_n)\leq \prod P(A_n)$. It is intuitive but i couldn't prove through the problem statement. But it is interesting result. We could use B-C lemma even for correlated events, since they are negatively correlated. What do you guys think about it?

• try showing that the variance is smaller than the mean. Then since the mean in going to $\infty$ the st. dev. is much smaller and by a markov type inequality, the sum must be fairly large. – mike Apr 19 '12 at 22:10

I think Fristedt & Gray's book on probability proves a version of Borel--Cantelli that assumes only nonpositive correlation rather than independence. In particular, that means pairwise independence is enough.

Later edit: Here's what I find in A Modern Approach to Probability Theory by Bert Fristedt and Lawrence Gray, page 79:

Lemma 5. [Borel-Cantelli] Let $(A_1,A_2,\ldots)$ be a sequence of events in a probability space $(\Omega,\mathcal{F},P)$. Assume that for each $i\ne j$, the events $A_i$ and $A_j$ are either negatively correlated or uncorrelated. Let $A=\lim\sup_{n\to\infty} A_n$. If $\sum_{n=1}^\infty P(A_n)=\infty,$ then $P(A)=1$.

• This is awesome. Thank you! – Rodolfo Apr 19 '12 at 23:54
• Fristedt and Gray set an exercise right after this statement: prove the result by using the Kochen-Stone lemma. – Michael Hardy Apr 20 '12 at 19:24

The result you mention as being intuitive does not hold. To see this, one can recall the classical example of three uncorrelated dependent events, which is $A_1=[U=1]$, $A_2=[V=1]$ and $A_3=[UV=1]$, where $U$ and $V$ are i.i.d. $\pm1$ symmetric Bernoulli random variables.

Then the events $A_i$ are pairwise independent, each $A_i$ has probability $\frac12$, and $A_1\cap A_2\cap A_3=[U=V=1]$ hence $\mathrm P(A_1\cap A_2\cap A_3)=\frac14\gt\frac18=\mathrm P(A_1)\mathrm P(A_2)\mathrm P(A_3)$.

• True, my mind mislead me. Do you any idea how to prove that then? Thanks. – Rodolfo Apr 19 '12 at 21:56
• This is (a special case of) Kochen-Stone lemma, which is based on Paley-Zygmund inequality. Googling these keywords will unearth several excellent short proofs. – Did Apr 19 '12 at 22:13
• Rodolfo: I am lost: did you intend to ask for general versions of BC, or, as explicitely written in your post, for the validity of inequality "Q!"? – Did May 7 '12 at 12:21

The answer is given in Theorem 5 below. This post is essentially a reiteration of [1]'s first section ("Generalization of the Borel-Cantelli lemma").

Let $(\Omega, \mathcal{F}, P)$ be a probability space. Let $A_1, A_2, \dots \in \mathcal{F}$ be an infinite sequence of positive events (i.e. $P(A_n) > 0$ for every $n \in \{1, 2, \dots\}$). Note that this implies, in particular, that for every $k \in \{1, 2, \dots\}$, $E\big(\mathbb{1}_{A_k}\big) > 0$. For every $n \in \{1, 2, \dots\}$ define $X_n:\Omega\rightarrow\mathbb{R}$ to be the random variable $X_n := \sum_{k = 1}^n \mathbb{1}_{A_k}$.

Lemma 1

For every $n \in \{1, 2, \dots\}$, $$\frac{\sum_{i=1}^n\sum_{j=1}^nP(A_i\cap A_j)}{\big(\sum_{k=1}^nP(A_k)\big)^2} = \frac{E\big(X_n^2\big)}{E^2(X_n)}.$$

Proof

Let $n \in \{1, 2, \dots\}$. Then \begin{align} \sum_{k = 1}^nP(A_i) &= \sum_{k = 1}^nE\big(\mathbb{1}_{A_i}\big) \\ &= E\bigg(\sum_{i = 1}^n\mathbb{1}_{A_i}\bigg) \\ &= E(X_n) \\ \sum_{i = 1}^n\sum_{j = 1}^nP(A_i\cap A_j) &= \sum_{i = 1}^n\sum_{j = 1}^nE\big(\mathbb{1}_{A_i\cap A_j}\big) \\ &= \sum_{i = 1}^n\sum_{j = 1}^nE\big(\mathbb{1}_{A_i}\mathbb{1}_{A_j}\big) \\ &= E\Bigg(\sum_{i = 1}^n\sum_{j = 1}^n\mathbb{1}_{A_i}\mathbb{1}_{A_j}\Bigg) \\ &= E\Bigg(\Bigg(\sum_{k = 1}^n\mathbb{1}_{A_k}\Bigg)^2\Bigg) \\ &= E\big(X_n^2\big) \end{align}

Q.E.D.

Lemma 2

For every $n \in \{1, 2, \dots\}$, $$\frac{E\big(X_n^2\big)}{E^2(X_n)} = 1 + \frac{V(X_n)}{E^2(X_n)}.$$

Proof

Let $n \in \{1, 2, \dots\}$. The conclusion is a consequence of the fundamental variance identity $V(X_n) = E\big(X_n^2\big) - E^2(X_n)$.

Q.E.D.

Lemma 3

If $\sum_{n = 1}^\infty P(A_n) = \infty$ and $$\underset{n\rightarrow\infty}{\underline{\lim}}\frac{V(X_n)}{E^2(X_n)} = 0,$$ then $P\bigg(\underset{n\rightarrow\infty}{\overline{\lim}}A_n\bigg) = 1$.

Proof

Choose an increasing sequence $n_1 < n_2 < \dots$ in $\{1, 2, \dots\}$ such that $$\sum_{k=1}^\infty \frac{V\big(X_{n_k}\big)}{E^2\big(X_{n_k}\big)} < \infty.$$ Then for every $\varepsilon \in (0,1)$, \begin{align} \sum_{k = 1}^\infty P\Big((1-\varepsilon)E\big(X_{n_k}\big) \geq X_{n_k}\Big) &= \sum_{k = 1}^\infty P\big(E\big(X_{n_k}\big) - X_{n_k} \geq \varepsilon E\big(X_{n_k}\big)\big) \\ &\leq \sum_{k = 1}^\infty P\Big(\big|X_{n_k} - E\big(X_{n_k}\big)\big| \geq \varepsilon E\big(X_{n_k}\big)\Big) \\ &\overset{\text{Chebyshev}}{\leq} \sum_{k = 1}^\infty \frac{V\big(X_{n_k}\big)}{\varepsilon^2\ E^2\big(X_{n_k}\big)} \\ &< \infty. \end{align} Hence by the Borel-Cantelli lemma $$P\bigg(X_{n_k} > (1-\varepsilon)E\big(X_{n_k}\big)\ \text{eventually}\bigg) = 1. \tag{*}\label{star}$$ Since \begin{align} \sup_{n \in \{1, 2, \dots\}}E\big(X_n\big) &= \sup_{n \in \{1, 2, \dots\}}E\bigg(\sum_{k = 1}^n\mathbb{1}_{A_k}\bigg)\\ &= \sup_{n \in \{1, 2, \dots\}} \sum_{k = 1}^nE\big(\mathbb{1}_{A_k}\big) \\ &= \sup_{n \in \{1, 2, \dots\}} \sum_{k = 1}^nP(A_k) \\ &= \sum_{k = 1}^\infty P(A_k) \\ &= \infty, \end{align} and since $X_1 \leq X_2 \leq \cdots$, we have $\sup_{k \in \{1, 2, \dots\}}E\big(X_{n_k}\big) = \infty$. Therefore \eqref{star} implies that $$P\bigg(\sup_{k\in\{1, 2, \dots\}} X_{n_k} = \infty\bigg) = 1.$$ It remains to observe that $$\bigg\{\sup_{k\in\{1, 2, \dots\}} X_{n_k} = \infty\bigg\} = \underset{k\rightarrow\infty}{\overline{\lim}}A_{n_k} \subseteq \underset{n\rightarrow\infty}{\overline{\lim}}A_n.$$

Q.E.D.

Corollary 4

1. For every $n \in \{1, 2, \dots\}$, $$\frac{\sum_{i=1}^n\sum_{j=1}^nP(A_i\cap A_j)}{\big(\sum_{k=1}^nP(A_k)\big)^2} \geq 1.$$

2. If $\sum_{n = 1}^\infty P(A_n) = \infty$ and $$\underset{n\rightarrow\infty}{\underline{\lim}} \frac{\sum_{i=1}^n\sum_{j=1}^nP(A_i\cap A_j)}{\big(\sum_{k=1}^nP(A_k)\big)^2} = 1,$$ then $P\Big(\underset{n\rightarrow\infty}{\overline{\lim}}A_n\Big) = 1$.

Proof

1. By Lemma 1 and Lemma 2.

2. By Lemma 1, Lemma 2, and Lemma 3.

Q.E.D.

Theorem 5

If $\sum_{n = 1}^\infty P(A_n) = \infty$ and if the $A_n$'s are negatively correlated in the sense that for every $i, j \in \{1, 2, \dots\}$ such that $i\neq j$, $P(A_i\cap A_j) \leq P(A_i)P(A_j)$, then $P\Big(\underset{n\rightarrow\infty}{\overline{\lim}}A_n\Big) = 1$.

Proof

By Corollary 4 it suffices to show that $$\underset{n\rightarrow\infty}{\underline{\lim}} \frac{\sum_{i=1}^n\sum_{j=1}^nP(A_i\cap A_j)}{\big(\sum_{k=1}^nP(A_k)\big)^2} \leq 1.$$ This is a consequence of the following observations. \begin{align} \frac{\sum_{i=1}^n\sum_{j=1}^nP(A_i\cap A_j)}{\big(\sum_{k=1}^nP(A_k)\big)^2} &\leq \frac{\sum_{\substack{i,j\in\{1,\dots,n\}\\i\neq j}}P(A_i)P(A_j) + \sum_{k=1}^nP(A_k)}{\big(\sum_{k=1}^nP(A_k)\big)^2} \\ &= \frac{\big(\sum_{k = 1}^nP(A_k)\big)^2}{\big(\sum_{k=1}^nP(A_k)\big)^2} + \frac{\sum_{k = 1}^nP(A_k)\big(1 - P(A_k)\big)}{\big(\sum_{k=1}^nP(A_k)\big)^2} \\ &\leq 1 + \frac{\sum_{k = 1}^nP(A_k)}{\big(\sum_{k=1}^nP(A_k)\big)^2} \\ &= 1 + \frac{1}{\sum_{k=1}^nP(A_k)}. \end{align}

Q.E.D.

Works cited

[1] P. Erdős and A. Rényi. On Cantor's Series with Convergent $\sum\frac{1}{q_n}$. Mathematical Institute, Eötvös Loránd University, Budapest. Received 6 April, 1959.