馃攳
S01.10 Bonferroni's Inequality - YouTube
Channel: MIT OpenCourseWare
[0]
in this segment we will discuss a little
[3]
bit the Union bound and then discuss a
[6]
counterpart which is known as the
[8]
bonferroni inequality let us start with
[10]
a story suppose that we have a number of
[14]
students in some class and we have a set
[19]
of students that are smart let's call
[21]
that set a one so this is the set of
[25]
smart students and we have a set of
[28]
students that are beautiful
[30]
and let's call that set a two so a two
[35]
is the set of beautiful students if I
[39]
tell you that the set of smart students
[42]
is small and the set of beautiful
[45]
students are small then you can probably
[50]
conclude that there are very few
[52]
students that are either smart or
[56]
beautiful what does this have to do with
[58]
probability well when we say very few
[61]
are smart we might mean that if I pick a
[64]
student at random there's only a small
[67]
probability that they pick a smart
[69]
student and similarly for beautiful
[71]
students can we make this statement more
[75]
precise indeed we can we have the Union
[80]
bound that tells us that the probability
[83]
that I pick a student that is either
[86]
smart or beautiful is less than or equal
[91]
to the probability of picking a smart
[93]
student plus the probability of picking
[97]
a beautiful student so if this
[101]
probability is small and that
[102]
probability is small then this
[105]
probability will also be small which
[107]
means that there is only a small number
[109]
of students that are either smart or
[111]
beautiful now let us try to turn this
[115]
statement around its head suppose that
[120]
most of the students are smart and most
[125]
of the students are beautiful so in this
[128]
case I'm telling you that this sets a 1
[130]
and a 2 are big
[133]
now if the set a1 is big then it means
[139]
that this set here the complement of a1
[145]
is a small set and if I tell you that
[149]
the set a2 is big then it means that
[155]
this set here which is a complement of
[159]
a2 is also small so everything outside
[166]
here is a small set which means that
[171]
whatever is left which is the
[173]
intersection of a1 and a2 should be a
[177]
big set so we should be able to conclude
[181]
that in this case most of the students
[185]
belong to the intersection so they're
[187]
both smart and beautiful how can we turn
[191]
this into a mathematical statement it's
[194]
the following inequality that we will
[197]
prove shortly but what it says is that
[200]
the probability of the intersection is
[203]
larger than or equal to something and if
[207]
this probability is close to 1 which
[211]
says that most of the students are smart
[213]
and this probability is close to 1 which
[215]
says that more students are beautiful
[217]
then this difference here is going to be
[221]
close to 1 plus 1 minus 1 which is 1
[225]
therefore the probability of the
[227]
intersection is going to be larger than
[230]
or equal to some number that's close to
[232]
1 so this one will also be close to 1
[235]
which is the conclusion that indeed most
[238]
students fall in this intersection and
[240]
they're both smart and beautiful so what
[244]
we will do next will be to derive this
[246]
inequality and actually generalize it so
[253]
here is the relation that we wish to
[254]
establish we want to show that the
[257]
probability of a certain event is bigger
[260]
than something how do we show that one
[265]
way is to show that
[267]
the probability of the complement of
[269]
this event namely this event here we
[275]
want to show that this event has small
[278]
probability now what is this event here
[282]
we can use the Morgan's laws which tell
[285]
us that this event is the same as this
[289]
one that is the complement of an
[293]
intersection is the union of the
[296]
complements since these two sets or
[299]
events are identical it means that their
[303]
probabilities will also be equal and
[311]
next we will use the Union bound to
[314]
write this probability as being less
[317]
than or equal to the sum of the
[320]
probabilities of the two events whose
[322]
Union we are taking now we're getting
[328]
close except that here we have
[330]
complements all over whereas up here we
[333]
do not have any complements what can we
[335]
do well the probability of a complement
[338]
of an event is the same as one minus the
[343]
probability of that event and we do the
[350]
same thing for the terms that we have
[352]
here this probability here is equal to
[356]
one minus the probability of a1 and this
[361]
probability here is equal to one minus
[363]
the probability of a2 and now if we take
[369]
this inequality cancel this term with
[373]
that term and then move terms around
[377]
what we have exactly is exactly this
[380]
relation that we wanted to prove it
[384]
turns out that this inequality has a
[386]
generalization to the case where we take
[389]
the intersection of n events and this
[393]
has again the same intuitive content
[395]
suppose that each one of these events a
[398]
1 up to a
[400]
is almost certain to occur that is it
[403]
has a probability close to 1 in that
[406]
case this term will be close to n we
[410]
subtract n minus 1 so this term on the
[413]
right hand side will be close to 1
[416]
therefore the probability of the
[418]
intersection will be larger than or
[422]
equal to something that's close to 1 so
[424]
this is big essentially what it's saying
[427]
is that we have big sets and we take
[429]
their intersection then that
[432]
intersection will also be big in terms
[434]
of having large probability how do we
[437]
prove this relation exactly the same way
[440]
as it was proved for the case of two
[442]
sets namely instead of looking at this
[446]
event we look at the complement of this
[449]
event and we use the Morgan's laws to
[455]
write this complement as the union of
[458]
the complements these two are the same
[465]
sets or events so they have the same
[468]
probability and then we use the Union
[473]
bound to write this as being less than
[476]
or equal to the probabilities of all
[479]
those sets now this is equal to 1 minus
[488]
the probability of the intersection this
[495]
side here is equal to 1 minus the
[500]
probability of a1 this is one term we
[504]
get n such terms the last one being 1
[509]
minus the probability of a n and we
[515]
still have an inequality going this way
[517]
we collect those ones that we have here
[520]
there's n of them and 1 here so we're
[525]
left with n minus 1 terms that are equal
[528]
to 1 and this gives rise to this term we
[531]
have
[532]
all the probabilities of the various
[534]
events that appear with the same sign
[536]
this gives rise to this term and finally
[540]
this term here will correspond to that
[542]
term namely if we start with this
[545]
inequality and just rearrange a few
[547]
terms we obtain this inequality up here
[550]
so these bonferroni inequalities are a
[554]
nice illustration of how one can combine
[557]
the Morgan law set theoretic operations
[559]
and the Union bound in order to obtain
[563]
some interesting relations between
[565]
probabilities
Most Recent Videos:
You can go back to the homepage right here: Homepage