Borel–Cantelli Lemmas

If the total length is finite, the points hit infinitely often form a null set — ∑m(En)<∞⇒m(lim sup⁡En)=0\sum m(E_n) < \infty \Rightarrow m(\limsup E_n) = 0. With independence the converse holds.

m(lim sup⁡n→∞En)=0(∑n=1∞m(En)<∞)m(\limsup_{n\to\infty} E_n) = 0 \quad \left(\sum_{n=1}^{\infty} m(E_n) < \infty\right)
∑m(En)=∞, En independent ⇒m(lim sup⁡En)=1\sum m(E_n) = \infty,\ E_n \text{ independent } \Rightarrow m(\limsup E_n) = 1

Examples & Exercises

Let En=[0,1n2]E_n = [0, \frac{1}{n^2}] (n≥1n \ge 1). Verify directly that lim sup⁡n→∞En={0}\limsup_{n \to \infty} E_n = \{0\}, and prove completely, via the bound m(lim sup⁡En)≤∑k≥Nm(Ek)m(\limsup E_n) \le \sum_{k \ge N} m(E_k), that m(lim sup⁡En)=0m(\limsup E_n) = 0 — the first Borel–Cantelli lemma for this example.

lim sup⁡n→∞En=⋂N≥1⋃k≥NEk={0}\limsup_{n \to \infty} E_n = \bigcap_{N \ge 1}\bigcup_{k \ge N} E_k = \{0\}
m(lim sup⁡En)≤∑k≥N1k2  →N→∞  0m(\limsup E_n) \le \sum_{k \ge N} \frac{1}{k^2} \;\xrightarrow[N \to \infty]{}\; 0
Summable mode, n=20n = 20: cumulative length ∑k≤201k2≈1.5962\sum_{k \le 20} \frac{1}{k^2} \approx 1.5962 (of π26≈1.6449\frac{\pi^2}{6} \approx 1.6449); the red limsup approximation piles up near [0,0.01][0, 0.01] only.
Show proof
  1. lim sup⁡n→∞En=⋂N≥1⋃k≥NEk\limsup_{n \to \infty} E_n = \bigcap_{N \ge 1} \bigcup_{k \ge N} E_k is the set of points belonging to infinitely many EkE_k. Since Ek=[0,1k2]E_k = [0, \frac{1}{k^2}] is decreasing, ⋃k≥NEk=EN=[0,1N2]\bigcup_{k \ge N} E_k = E_N = [0, \frac{1}{N^2}], and ⋂N≥1[0,1N2]={0}\bigcap_{N \ge 1} [0, \frac{1}{N^2}] = \{0\} (any nonzero point is dropped once 1N2\frac{1}{N^2} falls below it). Hence lim sup⁡En={0}\limsup E_n = \{0\} — a single point of measure 0.
  2. Now the measure bound. For each NN, lim sup⁡En⊆⋃k≥NEk\limsup E_n \subseteq \bigcup_{k \ge N} E_k, so by countable subadditivity m(lim sup⁡En)≤∑k≥Nm(Ek)=∑k≥N1k2m(\limsup E_n) \le \sum_{k \ge N} m(E_k) = \sum_{k \ge N} \frac{1}{k^2}. This holds for every NN.
  3. Since ∑k≥11k2=π26<∞\sum_{k \ge 1} \frac{1}{k^2} = \frac{\pi^2}{6} < \infty, the tail sums vanish: for every ε>0\varepsilon > 0 there is NN with ∑k≥N1k2<ε\sum_{k \ge N} \frac{1}{k^2} < \varepsilon (tails of a convergent series tend to 0). Hence m(lim sup⁡En)<εm(\limsup E_n) < \varepsilon for every ε>0\varepsilon > 0, so m(lim sup⁡En)=0m(\limsup E_n) = 0 — matching the direct computation {0}\{0\}. That is the first Borel–Cantelli lemma on this example.

In a measure space (X,m)(X, m), prove completely that for any sequence of measurable sets {En}\{E_n\} with ∑n≥1m(En)<∞\sum_{n \ge 1} m(E_n) < \infty, m(lim sup⁡n→∞En)=0m(\limsup_{n \to \infty} E_n) = 0 (the first Borel–Cantelli lemma). No independence is needed.

lim sup⁡n→∞En=⋂N≥1⋃k≥NEk⊆⋃k≥NEk\limsup_{n \to \infty} E_n = \bigcap_{N \ge 1}\bigcup_{k \ge N} E_k \subseteq \bigcup_{k \ge N} E_k
m(lim sup⁡En)≤∑k=N∞m(Ek)  →N→∞  0m(\limsup E_n) \le \sum_{k=N}^{\infty} m(E_k) \;\xrightarrow[N \to \infty]{}\; 0
Summable mode, n=40n = 40: cumulative length ≈1.6202\approx 1.6202, closer to π26≈1.6449\frac{\pi^2}{6} \approx 1.6449 — the tail ∑k>401k2<140=0.025\sum_{k > 40} \frac{1}{k^2} < \frac{1}{40} = 0.025 bounds the limsup measure.
Show proof
  1. Write lim sup⁡n→∞En=⋂N≥1AN\limsup_{n \to \infty} E_n = \bigcap_{N \ge 1} A_N where AN=⋃k≥NEkA_N = \bigcup_{k \ge N} E_k is a decreasing sequence (larger NN means fewer terms in the union). By definition, lim sup⁡En⊆AN\limsup E_n \subseteq A_N for every NN.
  2. By monotonicity and countable subadditivity, m(lim sup⁡En)≤m(AN)≤∑k≥Nm(Ek)m(\limsup E_n) \le m(A_N) \le \sum_{k \ge N} m(E_k). The second inequality is just that the measure of a countable union never exceeds the sum of the measures — no disjointness, no independence needed.
  3. By the hypothesis ∑k≥1m(Ek)<∞\sum_{k \ge 1} m(E_k) < \infty, the tail sums ∑k≥Nm(Ek)\sum_{k \ge N} m(E_k) tend to 0 as N→∞N \to \infty (tails of a convergent series). Hence 0≤m(lim sup⁡En)≤∑k≥Nm(Ek)→00 \le m(\limsup E_n) \le \sum_{k \ge N} m(E_k) \to 0, so m(lim sup⁡En)=0m(\limsup E_n) = 0. The proof is complete — this is the first Borel–Cantelli lemma, and problem 1's example is the special case m(Ek)=1/k2m(E_k) = 1/k^2.

Toss a die forever and let En=E_n = "the nn-th toss is a 6". The EnE_n are independent with P(En)=16P(E_n) = \frac16 and ∑P(En)=∞\sum P(E_n) = \infty. Prove rigorously that ∏k=NM(1−16)=(56)M−N+1→0\prod_{k=N}^{M}(1 - \frac16) = (\frac56)^{M-N+1} \to 0 (M→∞M \to \infty), and use it to show completely that P(lim sup⁡n→∞En)=1P(\limsup_{n \to \infty} E_n) = 1 — the second Borel–Cantelli lemma under independence.

P ⁣(⋂k=NMEkc)=∏k=NM(1−16)=(56)M−N+1→0P\!\left(\bigcap_{k=N}^{M} E_k^c\right) = \prod_{k=N}^{M}\left(1 - \tfrac16\right) = \left(\tfrac56\right)^{M-N+1} \to 0
P(lim sup⁡En)=1−P ⁣(⋃N≥1⋂k≥NEkc)=1P(\limsup E_n) = 1 - P\!\left(\bigcup_{N \ge 1}\bigcap_{k \ge N} E_k^c\right) = 1
Nonsummable mode, n=31n = 31: the first 31 sets are exactly dyadic levels 0–4, total length 5.005.00 — diverging, and every point is covered at every level, so lim sup⁡=[0,1]\limsup = [0, 1].
Show proof
  1. First, the product rigorously. By independence, P(⋂k=NMEkc)=∏k=NMP(Ekc)=∏k=NM(1−16)=(56)M−N+1P\left(\bigcap_{k=N}^{M} E_k^c\right) = \prod_{k=N}^{M} P(E_k^c) = \prod_{k=N}^{M} (1 - \frac16) = (\frac56)^{M-N+1}. Taking logs, log⁡((56)M−N+1)=(M−N+1) log⁡(56)\log\left((\frac56)^{M-N+1}\right) = (M-N+1)\,\log(\frac56), and since log⁡(56)<0\log(\frac56) < 0 this tends to −∞-\infty as M→∞M \to \infty. Hence (56)M−N+1→0(\frac56)^{M-N+1} \to 0 — the probability of "no 6 from toss NN through MM" vanishes.
  2. Now continuity of measure from below: the sets ⋂k=NMEkc\bigcap_{k=N}^{M} E_k^c decrease in MM, so P(⋂k≥NEkc)=lim⁡M→∞P(⋂k=NMEkc)=lim⁡M→∞(56)M−N+1=0P\left(\bigcap_{k \ge N} E_k^c\right) = \lim_{M \to \infty} P\left(\bigcap_{k=N}^{M} E_k^c\right) = \lim_{M \to \infty} (\frac56)^{M-N+1} = 0 — for every NN, "no 6 ever again from toss NN on" is a probability-0 event.
  3. Since (lim sup⁡En)c=⋃N≥1⋂k≥NEkc(\limsup E_n)^c = \bigcup_{N \ge 1} \bigcap_{k \ge N} E_k^c (de Morgan), subadditivity gives P((lim sup⁡En)c)≤∑N≥1P(⋂k≥NEkc)=∑N≥10=0P((\limsup E_n)^c) \le \sum_{N \ge 1} P\left(\bigcap_{k \ge N} E_k^c\right) = \sum_{N \ge 1} 0 = 0. Hence P(lim sup⁡En)=1P(\limsup E_n) = 1: a 6 occurs infinitely often, almost surely. The same argument works in general — if the events are independent and ∑pn=∞\sum p_n = \infty, then log⁡(1−pk)≤−pk\log(1 - p_k) \le -p_k gives ∑k=NMlog⁡(1−pk)≤−∑k=NMpk→−∞\sum_{k=N}^{M} \log(1-p_k) \le -\sum_{k=N}^{M} p_k \to -\infty, so the product tends to 0. That is the second Borel–Cantelli lemma.

10. Integration