Welcome back. So, today we will discuss Borel-Cantelli
lemmas. So, Borel-Cantelli lemmas say that if you given a sequence of
event it gives condition under which only finitely many of these events will occur.
I will state to properly now. . So, as usual you have given a probability
space some omega f p is given to you. So, there
is Borel-Cantelli lemmas that we will study there are actually few more versions, but
we will study that 2 most famous mos. The first
Borel-Cantelli lemma is this says the
following. If A 1 A 2 dot is a sequence of events such that
some over n equals 1 through infinity probability of A n is finite. Then
almost surely or it probability 1 only finitely many
A i is will occur it is A n is will occur. .. So, A 1 A 2 dot this is a sequence of events,
so there all f measurable. So, all these events will have some probabilities associated
with them. So, if it, so happens that the sum of the probabilities of A n equal to 1
to infinity is finite then the B C lemma BorelCantelli lemma1 says almost surely that is with probability
1 only finitely many of the A n is will occur. So, I will help you digested
to a little bit better first I want to, so there are
only 2 possibilities. So, this summation it is probability of A
n is a non-negative this is like a non-negative sequence p of A n is non-negative sequence.
So, if sum n non-negative sequence n equals to 1 to infinity it is well defined it is
always well defined. The question is whether it goes
to something finite or goes to plus infinity there are only 2 possibilities. So, the first
B C lemma talks about the case when it is finite
if the second Borel-Cantelli lemma talks about the case it is infinite the we will
first deal with in this finite. So, I will help you
parts what is this finitely many A n is occurring it is and the second Borel-Cantelli
lemma I will just state both and then explain both of them. So, this is like a partial
second Borel-Cantelli lemma like a partial converse to the first B C lemma.
So, it is says that if this is infinite then infinitely many A n is occur, but not quite
you need independents here you do not need any
independents. Then almost surely infinite occur. So, these 2 are the statements first
Borel-Cantelli lemma says is the summation of
the probability is finite only finitely many A n is will occur. And second says if the .summation infinity and you have independents
then infinitely many A n is will occur with probability 1 both are probability. So,
let us let us try to understand the first BorelCantelli lemma occurs. So, you are looking
at this guy, so probability of A n as sum sequence p n some numbers p n which sum to
something that is finite. So, what we will have is A is the sequence of events whose
probability going down to 0, because if A if a
you know that if a series sums to something finite the nth term has to go to 0 that you
know, but the converse is not true. So, you have sequence of events which is becoming
more and more unlikely. So, in that case it is not only true that p n probability of A
n is going to 0 it is also true that the sum is
finite which is saying more than that nth term is
going to 0. So, you are you have the sequence of events which are becoming more and
more unlikely and there becoming more unlikely rather fast. So, that the summation is
finite. So, which means this implies that beyond a
certain point beyond sum finite let us say n
naught none of this A n is will occur all most surely there exists some n naught beyond
which none of this all is A is fails to occur, because they are becoming, so unlikely, that
is what it means. So, there, so finitely man see finitely many A n is will occur means
some A n is will occur. But beyond a point there exist some n naught it beyond which
none of this A n is will occur that is what this means similarly, for this part if you
are talking about infinitely many A n is occurring;
that means, what, so you go as far as you like as big an as you like. But beyond that
n there exist at least some A n will occurs no
matter what n you look at that is what this finitely many A n is and infinitely many A
n is occurring means is this intuitively everybody
with me. So, I will introduce some notation to make this more formal. So, I want to talk
about see I am both these lemmas talk about some event of only finitely many A n is happening
or infinitely many A n is happening. So, I will actually denote that, so there
is a particular notation for it. .. So, event that infinitely many A n is occur
this is what I want to characterize. So, I want
to write this as some unions in intersections of A i is and that is done as follows you
write n equals to 1 through infinity union i equal to n through infinity A i. So it is
a nested it is an intersection and union and
this event is called, so this is denoted often by
A n infinitely often this is simply notation for this event this is an event that we will
encounter few times. So, this is just denoted by A n i o what this means is
this I will help you pass this in a minute, but, you will agree
that since A i is are events and I am only taking countable unions in intersections what
results will also be a event, because this is
just countable union in intersections of these A i is, so it has to be f measurable. So,
this is also an event and I can genuinely refer
to it as some event for which i can assign probabilities to be that clear first of all.
So, what the Bore-Cantelli lemma1 says is that this event has 0 probability in this
case and has probability 1 in the second case that
is what the B C lemma says everybody with me of course, I have to explain to you what
that that all is intersection or union means. So, I will help you parts this as follows.
So, let us make a definition let B n equal to
union i equals n through infinity A i. So, then I have A n i o is equal to intersection
b n. I am just, so this guy here I am calling B n
to help you pars it. So, whenever you have this
nested unions in intersection actually in your home work you will see 3 of them In 1
home work here the just 2 what you do is you start from the most union or intersection
and then work your way out. So, I am going to call that B n I am indexing it by n, .because I am starting from n here. Now, so
what is B n can somebody tell me what in words what B n is? At least B n is the event
that at least one of A n A n plus 1 A n plus 2
etcetera occurs r at least one of A n A n plus 1 A n plus 2 etcetera occurs that is
b n. So, for that reason B n is some tended refers
to as the nth tail event. It saying that o from
n onwards at least one of the A is occurs A n A n plus 1 A n plus 21 of them at least
one of them occurs and then what is A n infinitely
often. So, it just the intersection of these nth tail event. So, this is the event that
all the B n is occur for every n B n occurs by
definition. So, B n is again the nth tail event which means for every n at least one
of A n A n plus 1 A n plus 2 etcetera occurs. So,
which means no matter how big your n is I will
have a at least one of the A n is after that n occurring. So, no matter how far I go no
matter how big let us say my n naught is beyond that n naught one of this A i is will still
occur. So, the first Borel-Cantelli lemma says that A n infinitely often this event
has 0 probability.
In this case the second Borel-Cantelli lemma says this event has probability 1 in this
case are there any questions on this point before
I prove this results? The proves are actually fairly elementary once you manage to understand
what it is that the lemma says the proving it is not very easy not very difficult.
So, A i is, so this I have defined B n as the
union from n to n to infinity. So, this is B n is the event that at least one of A n
plus A n A n plus 1 A n plus 2 etcetera occurs for
that given n. So, it is called the nth tail event.
So, given n it is the event that at least one of A n A n plus 1 A n plus 2 etcetera
occurs and this is the event that each one of the
B n circle. It is means for every n I will say that
this event has occurred if each of the B n circles which means for every n. I must have
a at least one of A n A n plus 1 A n plus 2
etcetera occurring. For every n I need at least
one of A n A n plus 1 A n plus 2 etcetera occur any questions? Proof B C lemma1 is easy
to prove. .. Proof, see remember that first Borel-Cantelli
lemma does not need independents or any other further constrains if it. So, happens
that some over n equal to 1 to infinity p of A n
is finite then this will apply only finitely many A n is will occur. So, what do I have
to prove? I have to prove that in the first case
this event has probability 0. So, that the complementary event finitely often will have
probability 1 see what is the complement of this will become? This intersection will become
a union then the union becomes A intersection and then you will have a complement.
This means there exists an n such that each of the further A i fails to occur which
is where this is what finitely often means. So,
you can this use de Morgan and flip this around if you want.
So first Borel-Cantelli lemma, so you have you want to look at this you want to look
at probability of essentially is this
you want to show this is equal to 0. And what is the if I
see something like this what is the first thing I do? I invoke continuity of probabilities
now, this B n is I think this B n is will turn out to be nested increasing or nested
decreasing B n is are. So, B n is the event that at least one of A n A n plus 1 etcetera
occurs. So, B n plus 1 is, so nested decreasing. So, this B n is like Russian dollars no
they are nested decreasing everybody with just think about it if at least one of A n
A n plus 1 A n plus 2 etcetera occurs. That is
bigger set than at least one of A n A n plus 1 A
n plus 2 etcetera occurring. So, I can use continuity of probability, so write this as
probability of agree this is continuity of probability and using the fact that B n is
nested decreasing. .So, that is equal to limit n going to infinity
probability of my B n is after all union i equals n through infinity A i. I have just
copied what B n is now I can use union bound on that. I have a union of events. So, the
probability of union is less than or equal to sum
of the individual probabilities after all I have to get to a sum of probabilities are
some point. So, this is less than or equal to lemma
n tend to infinity a some over i equals n through infinity probability of A i. So, this
is union bound this continuity of probabilities. So, now, the proof is almost over reason is
I know that the summation this is the converging summation this converges to something
finite. And you know that this guy is that tails some of a convergent series and
as n goes to infinity the tails sum has to go to 0
you know that from your sequences in series. So, this has to be equal to 0 as n goes to
infinity this goes to 0. So, I have proved what I have proven? I have
proven that with probability 1. So, with probability 0 there is probability 0 that
infinitely many A n is will occur which means the
probability 1 only finitely many A n is will occur which means beyond the point A n is
will all A n is will fail to occur beyond a certain n naught none of the A n is
will occur. So, this is a very simple proof. So, this
is hardly 3 steps with me, any questions? So,
now, you have to prove second Borel-Cantelli lemma. Second Borel-Cantelli lemma says
that it is a partial converse why I am saying is that partial converse? You need
independents right it does not says that no matter how this is this summation will infinite.
I will always have infinite that is not what it saying you need independents you have it
is for this stipulating independents. The second
Borel-Cantelli lemma it is a little bit of it
requires sum algebraic jealousy here. So, I will prove a lemma to prove a lemma.
So, the second B C lemma I want to prove another lemma to prove it. Suppose 0 less
than or equal to p i less than or equal to 1 is such that sum over p i equals infinity
then product i equals 1 through infinity 1 minus
p i equal to 0. So, this statement has nothing to with probability assets it just a you are
saying that if something if series sums to infinity it series of numbers you have this
p i which have between 0. And one you can think of the mess probabilities, but it not
necessarily the case it sums to infinity. So, then
you have this product is 0. So, the proof of this is again just algebra. So, we have
the following. So, we have log, so it is follows
from this flag log 1 minus x is always less than or equal to minus x for x in 01. This
is something you can prove this is just an .identity this is identically true for all
x n 01. So, you apply, so you take a logarithm of
this. So, let me do that. . So, you have log product i equals 1 through
infinity 1 minus p i equal to log of limit intending to infinity product i equal 1 through
n 1 minus p i. So, this guys say I want to prove this guy is 0. So, I want to I am just
taking log, because it is a product log of a
product just becomes a summation. So, this will become, so this I am writing as a limit.
So, now, I have less than or equal to log of pi i equal 1 through k 1 minus p i for
all k. So, this can only be bigger I am only going,
so this is for n bigger and bigger, so I am multiplying number that less than. So, if
I stop at some point I only be bigger and log is
monotonic. So, this is again simple algebra just nothing very deep here. Now what do I
do? I have log of all this product which is equal to I can write it as log of a product
is sum of the logarithm.
I will have sum over i equal 1 through k log 1 minus p i which is less than or equal to
sum over i equals 1 through k minus p i. This relationship, because of this guy, so first
or note that you just a note that here. So, from
there you get this and this is also true for all
k. So, taking k to infinity, so if I take k to infinity what happens to this term? I
know that sum over p i is infinity. So, this summation
will go to minus infinity it just means the product will go to 0. So, we have log of all
those product 1 minus p i this way we will go
to minus infinity implying the result. So, that is
just a lemma to prove the lemma and this .lemma has nothing do it probability just
algebra. So, now, I want to really prove this Borel-Cantelli lemma 2 actually let me keep
this part of the board I will prove number 2
here. So, I have to prove. . So, in order to prove Borel-Cantelli lemma
2 I have to prove probability of A n infinitely often is 1 or I can prove that the complement
has 0 probability that is also. So, what I will look at is in fact, the probability of
the complement of this guy. So, I have 1 minus the probability of A n infinitely often is
equal to the probability of union n equals1 through infinity d n complementary. I am looking
at the probability of the complement A n finitely often essentially and that I am
suing de Morgan to de Morgan on this. So, this I
will again use union bound sum over n equals 1 through infinity probability of B n
complement. Now, I want to prove that this is equal to what I want to prove this is equal
to 0. So, I must, so in order for this to be 0 I need the only way this can be 0 is
each of this B n complements should have 0 probability
otherwise it is this is not happened. So, I want to prove that each of this is 0
and therefore, your upper bounded by 0 which means it is 0. So, here I go, so you have
we will show probability of B n complement equal to 0 for all n greater than or equal
to 1 indeed fix n and n greater than or equal to n.
Then you have probability that intersection i equals n through m A i complement is equal
to, so this is… So, I am taking an finite intersection of a complements. So, why I am
doing that? I want to prove that B n complement has 0 probability and B n complement .will have intersection A i complement, but
it will it will go from n to infinity. But I mean
eventually i will send m to infinity use continuity of probabilities. So, if you look at this
A i is are independent events you can prove that A i is are independent events then a
complement or also independent events you have to prove it you do it as a home work.
So, this you will get this what will happened to this will product out this is have pi i
equals n through m probability of a complements which is 1 minus probability of A i.
Now, if I sent m to infinity what happens? So, if I sent m to infinity, so look at this
very carefully if I send m to infinity limit m
tends to infinity I will use continuity of probability is to put the infinity here which
is give me probability of B n complement. And then I will get i equals n through infinity
1 minus p of A i. So, what I am saying is thus probability of B n complement is equal
to limit m tends to infinity probability of intersection i equals n through n through
m A i complement. So, this is by what relation? This is, because of continuity of probabilities,
because B n complement is the intersection n equals i equals n through infinity
A i complement. I am writing it as a limit using continuity of probabilities and by this
relation I will get this is equal to a product. So, I will put the limit here. So, that will
become i equals 1 through infinity, so may be
skipping 1 step here1 minus p of A i. So, statement of the lemma is that almost
surely A n is occur infinity almost surely means with probability 1 w p 1 or a dot s
is something that used interchangeably it means
that the probability of the event is 1. So, now, this I know what this is why? Because
I have see I am going from some n to infinity,
but I know that if I sum p of A i from n to infinity I will get infinity. So, by that
simple algebraic lemma this will be this will be 0
for all n greater than or equal to 1 by the lemma by that earlier algebraic lemma, because
this p of A i sum to infinity, so this product will be 0 by that lemma. So, which means for
every n greater than or equal to 1 probability of B n complement is 0 which means that
guy will be. So, from here you can conclude that is 0, because each of this is 0, so this
summation is 0. So, probability of A n occurring infinitely often is 1. So, I will give an
example in little bit first I want to make sure that you understand the proof.
So, just look over it one more time it is not a difficult proof all steps are remain
use repeatedly use union bound continuity of probability
these are things that you keep using all the time k in this kind of proof. So I
will, so in what remains of this lecture I will give
an example to illustrate first B C lemma second B C lemma. And I will also illustrate .that if you through away independents it
completely through away independents from the
second lemma. And you still have this it does not necessarily mean that infinitely many
A n is will occur a probability 1. So, it is not a complete converse first shall I do
the example, so do some example. So, simplest
example is you are looking at whether sum of the certain probabilities goes to infinity
or is finite. So, you have to look for some convergence series or non-convergence some
something that is goes to infinity some divergence.
. So, example see I am going to toss. So, it
is like this infinite coin toss model except my
probability measure is not going to be what we already studied. So, I am going to toss
coins infinitely many times and my sigma algebra is are familiar sigma algebra whatever
we did. Except now, the probability measure is not going to be my half the fair coin
measure i am going to put something more complicated on it. Let p a well let A i be the
event that the i th toss is heads as usual we studied this look at looked this before.
And let p be a probability measure on omega f
such that probability of A n equal to 1 over n
for all n greater than equal to 1. So, I am taking some probability measure which has
the property that the probability of the n th
toss turning up heads is 1 by n. So, I will, so this
is 1 by n. So, this has the probability that summation is infinity. So, I will later make,
so sum over 1 by n is infinite if I make this
1 by n square it is summation is finite you know. So, it is, so if I want to give the
example of the first Borel-Cantelli lemma I should .probably just gave 1 by n square to begin
with if I give 1 by n to be example for the second lemma. So, let me keep 1 by n square.
So, I have not specifying see I have not told you what the measure is the entire sigma
algebra you take whatever measure you want has that has this property. I have not see
I only specified measures for A n I have not
told you what the measure. So, you have to do
the full the full story like we did it for the fair coin toss model, but I am saying
let p b any probability measure which has this property
you can prove that you can formalize this no problem, but all I am saying.
So, let us think about the, this intuitively I am saying that I have this infinite coin
tosses the probability of the first toss being heads
is 1 probability of second toss being heads is
1 forth say third toss being heads is 1 ninth and so on. So, it is becoming heads or
becoming very unlikely as you go along the probability of the 100 toss being heads will
only be 1 and only 10000 is very unlikely as you go along. So, you have, so this is
since sum over p of A n is finite actually you if
you sum n equals 1 through infinity of p of A n
you will get pi square over 6. It does not matter what value it is finite sum over n
equal to 1 through infinity 1 over n square is finite.
B C lemma B C lemma 1 implies that almost surely only finitely many heads will occur.
. So, all I am saying is that if your heads
are becoming more and more unlikely like 1 by n
square. So, in the n th toss the probability of finding heads is only 1 by n square I am .saying that there exists an n naught almost
surely beyond which no heads will occur. You will get only tails beyond n naught you
get only tails and with probability 1 there exists n naught such that beyond n naught
there exists only tails that is what this is
saying. So, heads will stop occurring all together with probability 1. Correct, is that
clear? Student: i th toss heads will not occur.
No. So, no the statement says almost surely only finitely heads will occur which means
there exists with probability 1 there exists an n naught beyond which there will be no
heads with probability 1. There will be no heads what so ever beyond a certain n naught
and such an n naught exists with probability point.
Student: So, for any positive. So, for any given n th probability of heads
is 1 by n squared, but what I am saying is the
what the Borel-Cantelli lemma saying is that there exists sum n beyond which you will
never see the head with probability 1 where the set of all coin tosses which corresponds
to having infinitely many heads will have probability will have measure 0. The set of
all coin tosses in 01 power infinity which correspond
to infinitely many heads will have probability 0 that is what this is saying.
So, now, if you want to tweak it around and make it to an example for B C lemma 2 what
you have to do? So, suppose, so you have to of course, make this coin tosses independent
you have to make a appropriate model in which. So, next suppose
p of A n equal to 1 by n and that A n is are independent. So, you
have independent coin tosses now. So, in earlier case you do not even independents you
did not need independents at all. Now you are saying that this coin tosses are
independent and my probabilities are now 1 over n. So, in my seventeenth toss the
probability of getting heads will 1 by 17. Student: ((Refer Time: 45:45))
No there exists no with probability 1 there exists an n naught beyond which no heads
will occur. Student: ((Refer Time: 45:58)) .That is not what I am saying i am looking
at A n infinitely often. I am saying probability of A n infinitely often is 0 do not looking
at probability of A n naught plus 1 see which I
am saying this Borel-Cantelli lemma is very easy to state, but difficult to digest, so
think about it. So, in this case let me just finish
this example. So, you understand this example, so you have you tossing coins independently
and the probability of finding heads in n th
tosses 1 over n. So, here also that heads are becoming more and more unlikely. So, in
the 100 toss the probability of heads is 1 over
100 and probability of tail is 99 over 100. So, it is becoming over likely to see more
heads, but, according to second B C lemma see
since. So, what I am saying is since sum over 1 over n is infinity and the events are
independent. B C lemma to implies that almost surely infinitely many
heads will occur, so what is saying is. So, if you just look
at this as n, so let say this is n equal to 1 and
then you are looking far out. So, if you are looking far out if you looking at sum 100
the probability of finding heads is 1 over 100.
If you are go to 1000 it is 1 over 1000. But what B C lemma 2 saying is no matter how
far our you go you are guaranty to find with probability 1 you are guaranty to find
at least 1 head turning up. No matter how far
out you go. So, although, so you may imagine that n is the million the probability of
heading getting head is 1 in a1 in a million. But, I am saying that if you look at million
plus 1 bla the rest of that tally events there is a daily event there will be 1 head popping
up somewhere with probability 1. No matter how far out you go you can go to million a
billion is becoming more and more unlikely, but, if you look at the entire tail there
will be at least 1 head popping off. So this is
a highly non-trivial result I want to this is not
something that you can easily predict with some elementary probability calculation. So,
if you have 1 by n you get infinitely many heads occurring although it becoming more
and more unlikely. But if you make it 1 over n power 1 plus delta then the series will
converse then the heads will stop occurring all together. So, this is 1 over n is this
transition point. So the probability of heads is not 1 over
n, but 1 over n plus n power 1.001 then heads is
stop occurring almost surely, because the series will converse. So, I hope this example
think about it takes some time to digest. The final point I want to make is that you
cannot completely get away from the independents
in the B C lemma 2. For example, if you take you fix any event e whose probability
strictly between 0 and 1. And you take all you
are A n is to be equal to that e this is all your A n is i equal to the that event e then
sum .over probability of A n will be definitely
infinite, because you are summing something between. So, that will be infinite, but still
the probability of infinitely many A n is are
occurring will be simply the probability that e occurs because all the A n is are equal
to e. So, you cannot just throw away this independence,
but it is also true that you do not strictly need independents with independence
the B C lemma 2 works. But you can make a slight relaxation on that independence also
which is why there are many Bore-Cantelli lemmas. But you will only worry about this
1 and 2 1 does not require any structure 2 for
2, we have independence you cannot through away.
Thank you, I will stop here. .
