The primary topics in this part of the specialization are: asymptotic ("Big-oh") notation, sorting and searching, divide and conquer (master method, integer and matrix multiplication, closest pair), and randomized algorithms (QuickSort, contraction algorithm for min cuts).
Probability Review II
Loading...
From the course by Stanford University
Divide and Conquer, Sorting and Searching, and Randomized Algorithms
1930 ratings
From the lesson
Week 3
The QuickSort algorithm and its analysis; probability review.
Meet the Instructors
Tim RoughgardenProfessor
Computer Science
So welcome to part two of our probability review. This video assumes you've already
watched part one or at least are familiar with concepts covered in part one. Namely
sample spaces, events, random variables, expectation and linearity of expectation.
In this part of the review we're going to be covering just two topics. Conditional
probability and the closer related topic of independence. Both between events and
between random variables. I want to remind you that this is by no means the only
source you can or should use to learn this material. A couple of other sources free
that I recommend are lecture notes that you can find online by Eric. And also
there's a wiki book on discrete probability. So, conditional probability,
I hope you're not surprised to hear, is fundamental to understanding randomized
algorithms. That said, in the five weeks we have here, we'll probably only use it
once. And that's in analyzing the correctness of the random contraction
algorithm for computing the minimum cut of an undirected graph. So, just to make sure
we're all on the same page, here's some stuff you should have learned, from part
one of the probability review. You should know what a sample space is. This
represents all of the different outcomes of the random coin flips, all of the
different things that could happen. Often in randomized algorithm analysis, this is
just all of the possible random choices that the algorithm might make. Each
outcome has some known probability [inaudible]. By and, of course, the sum of
the probabilities equal one and remember that event is nothing more than a subset
of omega. Omega is everything that could possibly happen. S is some subset of
things that might happen and, of course, the probability of event is just the
probability of, of all the outcomes that the event contains. So, let's talk about
conditional probability. So one discusses the conditional probability of one event
given a second event. So, let X and Y denote two events, subsets of the same
sample space. You might want to think about these two events X and Y in terms of
an event diagram. So we could draw a box, representing everything that could
conceivably happen. So that's Omega. Then we can draw a blob corresponding to the
event X. So that's some stuff. Might or might not happen, who knows. And then the
other event Y is some other stuff which might or might not happen. And in general
these two events could be disjoint, that is they could have no intersection. Or
they might have a non-trivial intersection. X intersect Y. Similarly
they need not cover omega. It's possible that nothing X nor Y happens. So what's
we're looking to define is the probability of the event X given the even Y. So we
write probability of X bar Y, phrased X given Y. And the definition is, I think,
pretty intuitive. So given Y means we assume that something in Y happened.
Originally anything in omega could have happened. We didn't know what. Now we're
being told that whatever happened that lies somewhere in Y. So we zoom in on the
part of the picture that, in which contains Y. So that's gonna be our
denominator. So, our new world is the stuff in Y. That's what we know happened.
And now we're interested in the proportion of Y that is filled up with X. So, we're
interested in what fraction of Y's area is occupied by stuff in X. So X intersect Y,
divided by the probability of Y. That is by definition the conditional probability
of X given Y. Let?s turn to a quiz, using our familiar example of rolling two dice.
To make sure that the definition of conditional probability makes sense to
you. Okay, so the correct answer to this quiz is the third answer. So let's see why
that is. So what are the two events that we care about? We want to know the
probability of X given Y, where X is the event that at least one die is a one. And
Y is the events that the sum of the two dice is seven. Now, the easiest way to
explain this is let's zoom in, let's drill down on the Y. Let's figure out exactly
which outcomes Y comprises. So the sum of the two dice, being seven, we saw in the
first part of the review, there's exactly six outcomes which give rise to the sum
seven, namely the ordered pairs one, six. Two five, three four, four three, five
two, and six one. Now, remember that the probability. Of x given y is by definition
the probability of x intersect y divided by the probability of y. Now, what you
notice from this formula is we actually don't care about the probability of x per
se or even about the event x per se, just about x intersect y. So, let's just fig,
so, now we know why there has to be six outcomes. Which of those also belong to x?
Well, x is those where at least one die is one. So, x intersect y is just going to be
the one, six and the six, one. Now the probability of each of the 36 possible
outcomes is equally likely. So each one is one over 36. So since X intersects Y, has
only two outcomes. That's gonna give us two over 36 in the numerator. Since Y has
six outcomes, that gives us a six over 36 in the denominator. When you cancel
everything out, you're left with a one third. So just applying the definition of
conditional probability to the correct definition of the two relevant events, we
find that indeed a third of the time is when you have a one condition on the sum
of the two being seven. Let's move on to the independence of two events. So. Again
we consider two events, x and y. By definition, the events are dependent if
and only if the following equation holds. The probability that both of them happen.
That is the probability of x intersect y is exactly equal to the probability that x
happens times the probability that y happens. So that's a simple innocuous
looking definition. Let me re phrase it in a way that it's even more intuitive. So
I'll you check this, it's just a some trivial algebra. This equation holds, for
the events X and Y, if and only if, this is just using the definition of
conditional probability we had on the last slide, if and only if the probability of X
given Y, Is exactly the same thing as the probability of x. So, intuitively, knowing
that y happens, gives you no information about the probability that x happens.
That's the sense in which x and y are independent. And, you should also check
that this holds if and only if, the probability of y, given x, equals the
probability of y. So, symmetrically, knowing that X has occurs gives you no
information, no new information about whether or not Y has occurred. The
probability of Y is unaffected by conditioning on X. So at this juncture I
feel compelled to issue a warning. Which is, you may feel like you have a good
grasp of independence. But, in all likelihood, you do not. For example I
rarely feel confident that I have a keen grasp on independence. Of course I use it
all the time in my own research and my own work, but it's a very subtle concept. Your
intuition about independence is very often wrong, even if you do this for a living. I
know of no other source that's created so many bugs in proofs by professional
mathematicians and professional computer science researchers as misunderstandings
of independence and using intuition instead of the formal definition. So, for
those of you without much practice with independence, here's my rule of thumb for
whether or not you treat random variables as independent. If things are independent
by construction, like, for example, you define it in your algorithm, so the two
different things are independent. Then you can proceed with the analysis under the
assumption that they're independent. If there's any doubt, if it's not obvious the
two things are independent, you might want to, as a rule of thumb, assume that
they're dependent until further notice. So the slide after next will give you a new
example showing you things which are independent and things which are not
independent. But before I do that I wanna talk about independence of random
variables rather than just independence of events. So you'll recall a random variable
is from the first video on probability review. It's just a real value function
from the sample space to the real numbers. So once you know what happens you have
some number. The random variable evaluates to some real number. Now, what does it
mean for two random variables to be independent? It means the events of the
two variables taking on any given pair of values are independent events. So
informally, knowing the value taken on by one of the random variables tells you
nothing about what value is taken on by the other random variable. Recalling the
definition of what it means for two events to be independent, this just means that,
the probability that A takes on value little a, B takes on value little b. The
probability that both of those happen is just the product of the probabilities that
each happens individually. So what's useful about independence of events is
that probabilities just multiply. What's useful about independence of random
variables is that expectations just multiply. So, we're going to get an analog
of linear expectation where we can take, we can interchange an expectation in the
product freely, but I want to emphasize this, this interchange of the expectation
of the product is valid only for independent random variables and not in
general, unlike linear expectations. And we'll see a non example. We'll see how
this fails on the next slide for non independent random variables. So, I'll
just state it for two random variables, but the same thing holds by induction for
any number of random variables. If two random variables are independent, then the
expectation of their product. Equals the product of their expectations. And again,
do not forget that we need a hypothesis. Remember, linearity of expectations did
not have a hypothesis for this statement about products. We do have a hypothesis of
them being independent. So why is this true? Well, it's just a straight forward
derivation where you follow your nose or write it out here for completeness, but,
but I really don't think it's that important. So you start with the
expectation of the product. This is just the average value of A times B, of course
weighted by the probability of, of any particular value. So the way we're gonna
group that sum is we're going to sum over all possible combinations of values, A and
B, that capital A and capital B might take on, so that's gonna give us a value of A
times B. Times the probability of that big A takes on the value of little a and
capital B takes on the value of little b. So that's just by definition where this is
the value of the random variable, capital A times capital B and this is the
probability that it takes on that value with the values A and B. Now because A and
B are independent, this probability factors into the product of the two
probabilities. This would not be true if they were not independent. It's true
because they're independent. So same sum where all possible joint values of all A
and B. You still have A times B. But now we have times the probability that A takes
on the value of A times the probability that B takes on the value of B. So now we
just need to regroup these terms. So let's first sum over A. Let's yank out all the
terms that depend on little a. Notice none of those depend on little b. So we can
yank it out in front of the sum over little b. So I have an A times the
probability that big A takes on the value of little a. And then the stuff that we
haven't yanked out is the sum over b, of b times, little b times the probability that
capital B takes on the value little b. And what's here inside the quantity? This is
just the definition of the expectation of b. And then what remains after we have
factored out the expectation of b? Just this other sum which is the definition of
the expectation of a. So, indeed four independents random variables, the
expected value of the product is equal to the product of the expectations. Let's now
wrap up by tying these concepts together in an example, a simple example that
nevertheless illustrates how it can be tricky to figure out what's independent
and what's not. So here's the set up. We're going to consider three random
variables. X1, X2 and X3. X1 and X2 we choose randomly, so they're equally likely
to be zero or one. But X3 is completely determined by X1 and X2. So it's gonna be
the XOR of X1 and X2. So XOR stands for exclusive or. So what that means is that
if both of the operands are zero, or if both of them are one, then the output is
zero. And if exactly one of them is one, exactly one of them is zero, then the
output is one. So it's like the logical or function, except that both of the inputs
are true, then you output false, okay? So that's exclusive or. Now this is a little
hand wavy, when we start talking about probabilities, if we want to be honest
about it, we should be explicit about the sample space. So what I mean by this, is
that X1 and X2 take on all values, they're equally likely. So we could have a zero,
zero or a one zero or a zero one or a one, one and in each of these four cases, X3 is
determined by the first two, as the X or, so you get a zero here, a one here, a one
here and a zero there. And each of these four outcomes is equally likely. So let me
now give you an example of two random variables, which are independent, and a
non example. I'll give you two random variables which are not independent. So
first, I claim that, if you think that X1 and X3, then they're independent random
variables. I'll leave this for you to check [sound]. This may or may not seem
counter-intuitive to you. Remember X3 is derived in part from X1. Never the less,
X1 and X3, are indeed independent. And why is that true? Well, if you innumerate over
the four possible outcomes, you'll notice that all four possible two byte strings
occur as values for one and three. So here they're both zero, here they're both one,
here you have a zero and one, and here you have a one and zero. So you've got all
four of the combinations of probability one over four. So it's just as if X1 and
X3 were independent fair coin flips. So that's basically why the claim is true.
Now. That's a perhaps counterintuitive example of independent random variables.
Let me give you a perhaps counterintuitive example of dependent random variables.
Needless to say, this example just scratches the surface and you can find
much more devious examples of both independent and non-independents if you
look in, say, any good book on discrete probability. So now let?s consider the
random variable X1 product X3. And X two and the claim is these are not
independent. So this'll give you a formal proof for. The way I'm going to prove this
could be slightly sneaky. I'm not going to go back to the definition. I'm not gonna
contradict the consequence of the definition. So it's proved that they're
not independent all I need to do, is show that the product of the expectations is
not the same as the expectations to the products. Remember if they were
independent, then we would have that equality. [inaudible] Product of
expectations will equal the expectation to products. So if that's false than there's
no way these random variables are independent. So the expectation of the
product of these two random variables is just the expected value of the product of
all three. And then on the other side, we look at The product of the expected value
of X1 and X3. And the expected value of X2. So let's start with the expected value
of X2. That's pretty easy to see. That is zero half the time and that is one half
the time. So the expected value of X2 is going to be one-half. How about the
expected value of X1 and X3? Well, from the first claim, we know that X1 and X3
are independent random variables. Therefore, the expected value of their
product is just the product of their expectations. Equal this expectations
equal to the expected value of X1 times the expected value of X2, excuse me, of
X3. And again, X1 is equally likely to be zero or one. So its expected value is a
half. X3 is equally likely to be zero or one so its expected value is a half. So
the product of their expectations is one-fourth. So the right-hand side here is
one-eighth; one-half times one-fourth, so that's an eighth. What about the left-hand
side, the expected value of X1 times X3 times X2? Well, let's go back to the
sample space. What is the value of the product in the first outcome? Zero. What
is the value of the product in the second outcome? Zero. Third outcome? Zero. Forth
outcome? Zero. The product of all three random variables is always zero with
probability one. Therefore, the expected value, of course, is gonna be zero. So
indeed, the expected value of the product of X1, X3 and X2 zero does not equal to
the product of the corresponding expectations. So this shows that X1, X3
and X2 are not independent.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
