5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – mike Apr 19 '12 at 22:10
4
$\begingroup$

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

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

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

$\endgroup$
  • $\begingroup$ True, my mind mislead me. Do you any idea how to prove that then? Thanks. $\endgroup$ – Rodolfo Apr 19 '12 at 21:56
  • 2
    $\begingroup$ 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. $\endgroup$ – Did Apr 19 '12 at 22:13
  • $\begingroup$ 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!"? $\endgroup$ – Did May 7 '12 at 12:21
0
$\begingroup$

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.

$\endgroup$

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.