Borel-Cantelli Lemma

Theorem (3.4.2)

Let An,n∈NA_n,n\in\mathbb{N} be a sequence of events.

  1. If ∑n=1∞P(An)<∞\sum_{n=1}^\infty P(A_n)<\infty then P(An i.o.)=0P(A_n \ i.o.)=0
  2. If ∑n=1∞P(An)=∞\sum_{n=1}^{\infty}\mathbb{P}(A_{n})=\infty and Ai⊥ ⁣ ⁣ ⁣⊥Aj,∀i≠jA_{i}\perp\!\!\!\perp A_{j},\forall i\not=j then P(Am i.o.)=1\mathbb{P}(A_{m}\, i.o.)=1

that is, if summable, then the probability of AnA_n occurring Infinitely often is zero or that w.p.1.w.p.1. (with probability 1), only finitely many AnA_n’s happen.

\begin{proof} PROVING (i): By Countable subadditivity we have that P(An i.o.)=P(lim sup⁡n→∞An)=P(⋂n=1∞⋃k=n∞Ak)by definition≤P(⋃k=n∞Ak)monotonicity≤∑k=n∞P(Ak)countable subadditivity\begin{align*} \mathbb{P}(A_{n}\text{ i.o.})=\mathbb{P}\left(\limsup_{ n \to \infty }A_{n} \right)&= \mathbb{P}\left( \bigcap_{n=1}^{\infty}\bigcup_{k=n}^{\infty}A_{k} \right) &\text{by definition}\\ &\le \mathbb{P}\left( \bigcup_{k=n}^{\infty}A_{k} \right)&\text{monotonicity}\\ &\le \sum_{k=n}^{\infty}\mathbb{P}(A_{k})&\text{countable subadditivity} \end{align*}Provided that the last last sum is finite, then as n→∞n\to \infty P(lim sup⁡n→∞An)=0\mathbb{P}\left( \limsup_{ n \to \infty } A_{n}\right)=0 which gives us what we want.

PROVING (ii): So here we work with the complement of the event: {Am i.o.}c={Am finitely often}⊆⋃N≥1{AN,AN+1,… don’t occur}\{ A_{m}\text{ i.o.} \}^{c}=\{ A_{m}\text{ finitely often} \}\subseteq \bigcup_{N\ge 1}\{ A_{N},A_{N+1},\dots \text{ don't occur} \}and by Monotonicity of Probability Measure we have P({Am i.o.}c)≤∑N=1∞P({AN,AN+1,… don’t occur})\mathbb{P}(\{ A_{m}\text{ i.o.} \}^{c})\le \sum_{N=1}^{\infty}\mathbb{P}(\{ A_{N},A_{N+1},\dots \text{ don't occur} \})but, we have that P({AN,AN+1,… don’t occur})=∏n=N∞(1−P(An))≤∏n=N∞e−P(An)since 1−x≤e−x=e−∑n=N∞P(An)=e−∞=0\begin{align*} \mathbb{P}(\{ A_{N},A_{N+1},\dots \text{ don't occur} \})&= \prod_{n=N}^{\infty}(1-\mathbb{P}(A_{n}))\\ &\le \prod_{n=N}^{\infty}e^{-\mathbb{P}(A_{n})}&\text{since }1-x\le e^{-x}\\ &= e^{-\sum_{n=N}^{\infty}\mathbb{P}(A_{n})}\\ &= e^{-\infty}=0 \end{align*}Hence we get that ∀N:P({AN,AN+1,… don’t occur})=0\forall N:\mathbb{P}(\{ A_{N},A_{N+1},\dots \text{ don't occur} \})=0 giving us that P({Am i.o.}c)=0\mathbb{P}(\{ A_{m}\text{ i.o.} \}^{c})=0 and hence P({Am i.o.})=1\mathbb{P}(\{ A_{m}\text{ i.o.} \})=1 \end{proof} >[!rmk] >Note that independence is required for the second condition. A counterexample is for infinite coin tosses, let A1=A2=⋯=A_{1}=A_{2}=\dots= s.t.

Linked from