Editing Borel–Cantelli lemma (section)

==Converse result==

A related result, sometimes called the '''second Borel–Cantelli lemma''', is a partial converse of the first Borel–Cantelli lemma. The lemma states: If the events ''E''<sub>''n''</sub> are [[statistical independence|independent]] and the sum of the probabilities of the ''E''<sub>''n''</sub> diverges to infinity, then the probability that infinitely many of them occur is 1. That is:<ref name=":0" />

{{math theorem|name=Second Borel–Cantelli Lemma|math_statement= If  <math>\sum^{\infty}_{n = 1} \Pr(E_n) = \infty</math>  and the events <math>(E_n)^{\infty}_{n = 1}</math>  are independent, then  <math>\Pr(\limsup_{n \to \infty} E_n) = 1.</math>}}

The assumption of independence can be weakened to [[pairwise independence]], but in that case the proof is more difficult.

The [[infinite monkey theorem]] follows from this second lemma.

===Example===
The lemma can be applied to give a covering theorem in '''R'''<sup>''n''</sup>.  Specifically {{harv|Stein|1993|loc=Lemma X.2.1}}, if ''E''<sub>''j''</sub> is a collection of [[Lebesgue measure|Lebesgue measurable]] subsets of a [[compact set]] in '''R'''<sup>''n''</sup> such that
<math display="block">\sum_j \mu(E_j) = \infty,</math>
then there is a sequence ''F''<sub>''j''</sub> of translates
<math display="block">F_j = E_j + x_j </math>
such that
<math display="block">\lim\sup F_j = \bigcap_{n=1}^\infty \bigcup_{k=n}^\infty F_k = \mathbb{R}^n</math>
apart from a set of measure zero.

===Proof ===

Suppose that <math display="inline">\sum_{n = 1}^\infty \Pr(E_n) = \infty</math>  and the events <math>(E_n)^\infty_{n = 1}</math>  are independent. It is sufficient to show the event that the ''E''<sub>''n''</sub>'s did not occur for infinitely many values of ''n'' has probability 0. This is just to say that it is sufficient to show that
<math display="block"> 1-\Pr(\limsup_{n \to \infty} E_n) = 0. </math>

Noting that:
<math display="block">\begin{align}
1 - \Pr(\limsup_{n \to \infty} E_n) &= 1 - \Pr\left(\{E_n\text{ i.o.}\}\right) = \Pr\left(\{E_n \text{ i.o.}\}^c \right) \\
& = \Pr\left(\left(\bigcap_{N=1}^\infty \bigcup_{n=N}^\infty E_n\right)^c \right) = \Pr\left(\bigcup_{N=1}^\infty \bigcap_{n=N}^\infty E_n^c \right)\\
&= \Pr\left(\liminf_{n \to \infty}E_n^{c}\right)= \lim_{N \to \infty}\Pr\left(\bigcap_{n=N}^\infty E_n^c \right),
\end{align}
</math> it is enough to show: <math display="inline">\Pr\left(\bigcap_{n=N}^{\infty} E_n^{c}\right) = 0</math>. Since the <math>(E_n)^{\infty}_{n = 1}</math> are independent:
<math display="block">\begin{align}
\Pr\left(\bigcap_{n=N}^\infty E_n^c\right) 
&= \prod^\infty_{n=N} \Pr(E_n^c) \\
&= \prod^\infty_{n=N} (1-\Pr(E_n)).
\end{align}
</math>
The [[convergence test]] for [[Infinite product|infinite products]] guarantees that the product above is 0, if <math display="inline">\sum_{n = N}^\infty \Pr(E_n)</math> diverges. This completes the proof.