Borel–Cantelli Lemma
   HOME

TheInfoList



OR:

In
probability theory Probability theory or probability calculus is the branch of mathematics concerned with probability. Although there are several different probability interpretations, probability theory treats the concept in a rigorous mathematical manner by expre ...
, the Borel–Cantelli lemma is a
theorem In mathematics and formal logic, a theorem is a statement (logic), statement that has been Mathematical proof, proven, or can be proven. The ''proof'' of a theorem is a logical argument that uses the inference rules of a deductive system to esta ...
about
sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is cal ...
s of events. In general, it is a result in
measure theory In mathematics, the concept of a measure is a generalization and formalization of geometrical measures (length, area, volume) and other common notions, such as magnitude (mathematics), magnitude, mass, and probability of events. These seemingl ...
. It is named after
Émile Borel Félix Édouard Justin Émile Borel (; 7 January 1871 – 3 February 1956) was a French people, French mathematician and politician. As a mathematician, he was known for his founding work in the areas of measure theory and probability. Biograp ...
and Francesco Paolo Cantelli, who gave statement to the lemma in the first decades of the 20th century. A related result, sometimes called the second Borel–Cantelli lemma, is a partial converse of the first Borel–Cantelli lemma. The lemma states that, under certain conditions, an event will have probability of either zero or one. Accordingly, it is the best-known of a class of similar theorems, known as zero-one laws. Other examples include Kolmogorov's zero–one law and the Hewitt–Savage zero–one law.


Statement of lemma for probability spaces

Let ''E''1, ''E''2, ... be a sequence of events in some
probability space In probability theory, a probability space or a probability triple (\Omega, \mathcal, P) is a mathematical construct that provides a formal model of a random process or "experiment". For example, one can define a probability space which models ...
. The Borel–Cantelli lemma states: Here, "lim sup" denotes limit supremum of the sequence of events. That is, lim sup ''E''''n'' is the outcome that infinitely many of the infinite sequence of events (''E''''n'') actually occur. Explicitly, \limsup_ E_n = \bigcap_^\infty \bigcup_^\infty E_k.The set lim sup ''E''''n'' is sometimes denoted , where "i.o." stands for "infinitely often". The theorem therefore asserts that if the sum of the probabilities of the events ''E''''n'' is finite, then the set of all outcomes that contain infinitely many events must have probability zero. Note that no assumption of
independence Independence is a condition of a nation, country, or state, in which residents and population, or some portion thereof, exercise self-government, and usually sovereignty, over its territory. The opposite of independence is the status of ...
is required.


Example

Suppose (''X''''n'') is a sequence of
random variable A random variable (also called random quantity, aleatory variable, or stochastic variable) is a Mathematics, mathematical formalization of a quantity or object which depends on randomness, random events. The term 'random variable' in its mathema ...
s with Pr(''X''''n'' = 0) = 1/''n''2 for each ''n''. The probability that ''X''''n'' = 0 occurs for infinitely many ''n'' is equivalent to the probability of the intersection of infinitely many 'X''''n'' = 0events. The intersection of infinitely many such events is a set of outcomes common to all of them. However, the sum ΣPr(''X''''n'' = 0) converges to and so the Borel–Cantelli Lemma states that the set of outcomes that are common to infinitely many such events occurs with probability zero. Hence, the probability of ''X''''n'' = 0 occurring for infinitely many ''n'' is 0.
Almost surely In probability theory, an event is said to happen almost surely (sometimes abbreviated as a.s.) if it happens with probability 1 (with respect to the probability measure). In other words, the set of outcomes on which the event does not occur ha ...
(i.e., with probability 1), ''X''''n'' is nonzero for all but finitely many ''n''.


Proof

Let (''E''''n'') be a sequence of events in some
probability space In probability theory, a probability space or a probability triple (\Omega, \mathcal, P) is a mathematical construct that provides a formal model of a random process or "experiment". For example, one can define a probability space which models ...
. The sequence of events \left\^\infty_ is non-increasing: \bigcup_^\infty E_n \supseteq \bigcup_^\infty E_n \supseteq \cdots \supseteq \bigcup_^\infty E_n \supseteq \bigcup_^\infty E_n \supseteq \cdots \supseteq \limsup_ E_n.By continuity from above, \Pr(\limsup_ E_n) = \lim_\Pr\left(\bigcup_^\infty E_n\right).By subadditivity, \Pr\left(\bigcup_^\infty E_n\right) \leq \sum^\infty_ \Pr(E_n).By original assumption, \sum_^\infty \Pr(E_n)<\infty. As the series \sum_^\infty \Pr(E_n) converges, \lim_ \sum^\infty_ \Pr(E_n)=0, as required.


General measure spaces

For general
measure space A measure space is a basic object of measure theory, a branch of mathematics that studies generalized notions of volumes. It contains an underlying set, the subsets of this set that are feasible for measuring (the -algebra) and the method that ...
s, the Borel–Cantelli lemma takes the following form:


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''''n'' are
independent Independent or Independents may refer to: Arts, entertainment, and media Artist groups * Independents (artist group), a group of modernist painters based in Pennsylvania, United States * Independentes (English: Independents), a Portuguese artist ...
and the sum of the probabilities of the ''E''''n'' diverges to infinity, then the probability that infinitely many of them occur is 1. That is: The assumption of independence can be weakened to
pairwise independence In probability theory, a pairwise independent collection of random variables is a set of random variables any two of which are statistical independence, independent. Any collection of Mutual independence, mutually independent random variables is p ...
, but in that case the proof is more difficult. The
infinite monkey theorem The infinite monkey theorem states that a monkey hitting keys independently and at randomness, random on a typewriter keyboard for an infinity, infinite amount of time will almost surely type any given text, including the complete works of Willi ...
follows from this second lemma.


Example

The lemma can be applied to give a covering theorem in R''n''. Specifically , if ''E''''j'' is a collection of Lebesgue measurable subsets of a
compact set In mathematics, specifically general topology, compactness is a property that seeks to generalize the notion of a closed and bounded subset of Euclidean space. The idea is that a compact space has no "punctures" or "missing endpoints", i.e., i ...
in R''n'' such that \sum_j \mu(E_j) = \infty, then there is a sequence ''F''''j'' of translates F_j = E_j + x_j such that \lim\sup F_j = \bigcap_^\infty \bigcup_^\infty F_k = \mathbb^n apart from a set of measure zero.


Proof

Suppose that \sum_^\infty \Pr(E_n) = \infty and the events (E_n)^\infty_ are independent. It is sufficient to show the event that the ''E''''n'''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 1-\Pr(\limsup_ E_n) = 0. Noting that: \begin 1 - \Pr(\limsup_ E_n) &= 1 - \Pr\left(\\right) = \Pr\left(\^c \right) \\ & = \Pr\left(\left(\bigcap_^\infty \bigcup_^\infty E_n\right)^c \right) = \Pr\left(\bigcup_^\infty \bigcap_^\infty E_n^c \right)\\ &= \Pr\left(\liminf_E_n^\right)= \lim_\Pr\left(\bigcap_^\infty E_n^c \right), \end it is enough to show: \Pr\left(\bigcap_^ E_n^\right) = 0. Since the (E_n)^_ are independent: \begin \Pr\left(\bigcap_^\infty E_n^c\right) &= \prod^\infty_ \Pr(E_n^c) \\ &= \prod^\infty_ (1-\Pr(E_n)). \end The convergence test for infinite products guarantees that the product above is 0, if \sum_^\infty \Pr(E_n) diverges. This completes the proof.


Counterpart

Another related result is the so-called counterpart of the Borel–Cantelli lemma. It is a counterpart of the Lemma in the sense that it gives a necessary and sufficient condition for the limsup to be 1 by replacing the independence assumption by the completely different assumption that (A_n) is monotone increasing for sufficiently large indices. This Lemma says: Let (A_n) be such that A_k \subseteq A_, and let \bar A denote the complement of A. Then the probability of infinitely many A_k occur (that is, at least one A_k occurs) is one if and only if there exists a strictly increasing sequence of positive integers ( t_k) such that \sum_k \Pr( A_ \mid \bar A_) = \infty. This simple result can be useful in problems such as for instance those involving hitting probabilities for
stochastic process In probability theory and related fields, a stochastic () or random process is a mathematical object usually defined as a family of random variables in a probability space, where the index of the family often has the interpretation of time. Sto ...
with the choice of the sequence (t_k) usually being the essence.


Kochen–Stone

Let (A_n) be a sequence of events with \sum\Pr(A_n)=\infty and \limsup_ \frac > 0. Then there is a positive probability that A_n occur infinitely often.


Proof

Let S_ = \sum^n_ \mathbf_. Then, note that E _2 = \left(\sum^n_ \Pr(A_i)\right)^2 and E _^2= \sum_ \Pr(A_i\cap A_j). Hence, we know that \limsup_ \frac > 0. We have that \mathbb 2 \le \mathbb \mathbf_2 \le \mathbb ^2Pr(X>0), therefore, \Pr(S_ > 0) \ge \frac. We then have \frac \ge \frac. Given m , since \lim_ \mathbb _= \infty , we can find n large enough so that \biggr, \frac - 1\biggr, < \epsilon, for any given \epsilon > 0 . Therefore, \lim_\sup_\Pr\left(\bigcup_^n A_i\right) \ge \lim_\sup_\frac > 0. But the left side is precisely the probability that the A_n occur infinitely often since \ = \. We're done now, since we've shown that P(A_k \text) > 0.


See also

*
Lévy's zero–one law In mathematicsspecifically, in the theory of stochastic processesDoob's martingale convergence theorems are a collection of results on the limits of supermartingales, named after the American mathematician Joseph L. Doob. Informally, the martin ...
* Kuratowski convergence *
Infinite monkey theorem The infinite monkey theorem states that a monkey hitting keys independently and at randomness, random on a typewriter keyboard for an infinity, infinite amount of time will almost surely type any given text, including the complete works of Willi ...


References

* * . * . * . * Durrett, Rick. "Probability: Theory and Examples." Duxbury advanced series, Third Edition, Thomson Brooks/Cole, 2005.


External links


Planet Math Proof
Refer for a simple proof of the Borel Cantelli Lemma {{DEFAULTSORT:Borel-Cantelli lemma Theorems in measure theory Theorems in probability theory Covering lemmas Lemmas