the Borel-Cantelli lemmas
/ bor-EL kan-TEL-ee /
Run an experiment forever and watch for some event each time — a record high temperature, a coin streak of a thousand heads, a sensor glitch. Two natural questions: will the event eventually stop happening for good, or will it keep recurring no matter how far out you go? The Borel-Cantelli lemmas answer this by looking at one number: the sum of the event's probabilities over all the trials.
The phrase 'happens infinitely often' means the event recurs again and again with no last occurrence. First lemma (no independence required): if the probabilities sum to a finite number, sum of P(A_n) < infinity, then with probability 1 the event happens only finitely often — eventually it stops for good. Intuitively, if the chances shrink fast enough to be summable, the tail of occurrences must dry up; the proof is just the union bound applied to the tail. Second lemma (independence required): if the events are independent and their probabilities sum to infinity, sum of P(A_n) = infinity, then with probability 1 the event happens infinitely often. So for independent events the dividing line is sharp — summable means finitely often, non-summable means infinitely often, a clean zero-one dichotomy.
These lemmas are the standard machinery for proving almost-sure statements — claims that hold with probability 1, the strongest kind. They are the engine behind the strong law of large numbers and behind sharp statements like the law of the iterated logarithm. The honest subtlety: the two directions are not symmetric. The first lemma needs nothing but summability; the second genuinely requires independence — without it, non-summable probabilities can fail to force infinitely-often (imagine one fixed event repeated forever, with probability 1/2 it simply never happens at all, yet the probabilities sum to infinity).
Toss a coin forever; let A_n be 'heads on toss n'. Here P(A_n) = 1/2 and the sum is infinite, and tosses are independent, so by the second lemma heads occur infinitely often, with probability 1 — as expected. By contrast, if A_n had probability 1/n^2 (summable), the first lemma would force A_n to stop occurring after some finite point, almost surely.
Summable probabilities: finitely often. Non-summable AND independent: infinitely often.
The two directions are asymmetric: the first lemma needs only summability, but the second genuinely requires independence. Without independence, non-summable probabilities need not force infinitely-often.