Discover

In probability theory, the 'Borel-Cantelli lemma' is a theorem about sequences of events. In a slightly more general form, it is also a result in measure theory. It is named after Émile Borel and Francesco Paolo Cantelli.
Let (''E''_''n'') be a sequence of events in some probability space.
The Borel-Cantelli lemma states:
:If the sum of the probabilities of the ''E''_''n'' is finite
::
:then the probability that infinitely many of them occur is 0, that is,
::$Pleft(limsup\_\{n\; oinfty\}\; E\_n$
ight) = 0.,
Here, "lim sup" denotes limit superior. Note that no assumption of independence is required.
For example, suppose (''X''_''n'') is a sequence of random variables, with Pr(''X''_''n'' = 0) = 1/''n''² for each ''n''. The sum of Pr(''X''_''n'' = 0) is finite (in fact it is $pi^2/6$ - see Riemann zeta function), so the Borel-Cantelli Lemma says that the probability of ''X''_''n'' = 0 occurring for infinitely many ''n'' is 0. In other words ''X''_''n'' is nonzero almost surely for all but finitely many ''n''.
For general measure spaces, the Borel-Cantelli lemma takes the following form:
:Let μ be a measure on a set ''X'', with σ-algebra ''F'', and let (''A''_''n'') be a sequence in ''F''. If
::
:then
::$muleft(limsup\_\{n\; oinfty\}\; A\_n$
ight) = 0.,
A related result, sometimes called the 'second Borel-Cantelli lemma', is a partial converse of the first Borel-Cantelli lemma. It says:
:If the events ''E''_''n'' are independent and the sum of the probabilities of the ''E''_''n'' diverges to infinity, then the probability that infinitely many of them occur is 1.
The assumption of independence can be weakened to pairwise independence, but in that case the proof is more difficult.
The infinite monkey theorem is a special case of this lemma.

Contents

References

References

★ Feller W., ''An Introduction to Probability Theory and Its Application'', John Wiley & Sons, 1968 (3rd Edition).