Welcome to part one of our probability
review. The first time that we need these
concepts in this course is for those that
wanna understand the analysis of Quick
Sort. Why it runs in big O of end log and
time on average. And these topics will
also come up a couple of other times in
the course. For example when we study a
randomized algorithm for the minimum cut
problem in graphs. And also when we try to
understand the performance of hashing.
Here are the topics we're going to cover.
We'll start at the beginning with sample
spaces, and then we'll discuss, events and
their probabilities. We'll talk about
random variables, which are real valued
functions on a sample space. We'll talk
about expectation, which is basically the
average value of a random variable. We'll
identity and prove a very important
property, called the linearity of
expectation, which will come up over and
over again in our analyses of randomized
processes. So that's gonna be the topics
for part one, that will conclude the video
with one example tying these concepts
together in load balancing. And, this
video is by no means the only source you
can turn to, to learn. About these
concepts. A couple of other sources I
recommend are the online lecture notes by
Eric [inaudible] and Tom [inaudible].
Also, there's a wiki book on discreet
probability, which you could, check out.
And I wanna be clear, this is really not
meant to be a course or a tutorial on
probability concepts. It's really only
meant to be a refresher. So I'm gonna go
at a reasonably fast pace, and it's gonna
be a pretty cursory presentation. And if
you want a more thorough review, I would,
I would check out one of these other
sources, or your favorite book on discreet
probability. And along those same lines,
I'm thinking that many of you have seen
some of this material before. Don't feel
compelled, like, to, to watch this video
straight [inaudible]. Beginning to the
end. Feel free to just sort of dip in, and
review the concepts, that you need a
refresher on. So, let's start at the
beginning with sample spaces. So, what is
a sample space? Well we're analyzing
random processes, so any number of things
can happen. And the sample space is just a
collection of all of those things that
could happen. So this is basically the
universe in which we're gonna discuss
probabilities and average values. So I'll
often use annotation bigo mega to describe
the sample space. So one thing that we've
got going for us in the design of
algorithm is typically we can take omega
to be a finite set. So that's why we're
only dealing only with discreet
probability which is a very happy thing.
Cause that's much more elementary then
more general probability. So I realize
this is sort of a super abstract concept,
and the next few definitions will also be
abstract, so I'm going to use two very
simple, very concrete running examples to
illustrate the next few concepts. So the
first example is just going to be, we take
two six sided dice and we roll them. So
then of course what's the sample space?
Well, it's just all of the possible
outcomes of just two dice. In addition to
defining the outcomes; everything that
could possibly happen, we need to define
what is the probability of each individual
outcome. So, of course, the probability of
each outcome should be at least zero,
should be non negative and there's also
the obvious constraint that the sum of the
probability should be one. So, exactly one
thing's gonna happen. Now I realize this
is a, a super abstract concept and the
next few definitions are also a little
abstract, so throughout them I'm going to
use two really simple, really concrete
examples to illustrate what these concepts
mean. So, the first example is just gonna
be you take two six sided dice, and you
roll them, and then of course, the sample
space is just the 36 different outcomes
you could have of these two dice. And
assuming that each of these two dice is
well crafted, then we expect each of these
36 outcomes to be equally likely to occur
with a probability of 1/36. The second
running example I'm going to use is more
directly related to algorithms and it's
motivated by the quick sort algorithm.
Recall that we're studying the
implementation of quick sort that chooses
a pivot uniformly at random in every
recursive call. So let's just focus on the
very first outermost call of quick sort
and think about the random choice of the
pivot just in that call. So then the
sample space, all of the different things
that could happen is just all of the N
different choices for a pivot, assuming
the array has length N. So we can
represent the sample space just as
integers one, two all the way up to N,
corresponding to the array index, of the
randomly chosen pivot. And again, by
definition, by the construction of our
code, each of these events, each of these
things is equally likely, probability of
one over N. Now let's talk about events.
An event is nothing more than a subsets of
all of the things that could happen. That
is a subset of the sample space omega. The
probability of the event is exactly what
you would think it would be. It's just the
sum of the probabilities of all of the
outcomes contained in that event, right?
So an event is just a bunch of stuff that
might happen, we know the probability of
each individual thing that could happen,
we add them up to get the probability of
an event. So the next two quizzes are
meant to give you some practice with these
concepts and in particular, the last few
to compute the probability of events in
our two running examples. So in the first
quiz, this is our first running example
where we think about two dice and we have
our 36 possible outcomes. Consider the
subset of outcomes in which the sum of the
two dice equals seven. What is the
probability of that event? Right, so the
correct answer is the third one, the
probability is one over six. Why is that?
Well, first, let's be more precise about
what this event is. What are the outcomes
in which the sum of the dices equal to
seven. Well there's exactly six such
outcomes. One six. Two five. Three four.
Four three. Five two and six one. Each of
the 36 outcomes is equally likely has a
probability of one over 36. So we have six
members of the set, usually [inaudible]
one over 36, so the probability is one
sixth. Let's move on to the next quiz,
which considers our second running
example, namely the randomly chosen pivot
in the outermost call to quick sort on an
input array of length n. So, recall that
in quick sort, when you choose a pivot,
you then partition the array around the
pivot, and this splits the input array
into two sub arrays. A left one, elements
less that the pivot, and a right one,
those bigger than the pivot. And the more
balanced the split into these two sub
problems, the better. So, ideally, we'd
like a fifty, fifty split. So what this
quiz asks you is what fraction of pivots,
that is what's probability that a randomly
chosen pivot. [inaudible] will give you a
reasonably good split, meaning both of the
sub-problems have size at least 25%. That
is you get a split 25/75 or better. That's
what this quiz asks about, what's the
probability that the randomly chosen pivot
satisfies that property? So the correct
answer to this quiz is again, the third
option. It's a 50 percent probability you
get a 25/75 split or better. So to see
why, let's, again, be precise about what
is the event that we're talking about?
Then we'll compute its probability. So,
when does a pivot give you a 25/75 split
or better? Well, for concreteness, suppose
the array contained just the integers
between one and 100. Now, what's the
property we want? We want that both of the
two sub arrays, have at least 25 percent
of the elements. Neither one has more than
75 percent of the elements. Well, if we
choose an element that's 26 or bigger in
value, then the left sub problem will have
at least 25 elements. It's the numbers one
through 25, and if we choose an index
which is, choose an element that's at most
75, then the right sub-array's going to
have at least 25 elements in the numbers
76 to 100. So anything between 26 and 75,
inclusive is going to give us a 25-75
split, more generally. Any pivot from the
middle 50 percent of the quan, of the
quintiles is gonna give us the desired
split. So we do badly if we get something
within the first quarter, we do badly if
we get something within the last quarter.
Anything in the middle works. So more
formally we can say that the event s that
we're analyzing is among the possible
pivot choices. We're interested in the
ones that is not in the first quarter or
not in the last quarter. Now the
coordinately of; the number of pivots in
this set is essentially one-half of the
overall pivot choices. I'm ignoring,
fractions here for simplicity. So the
probability of this event is the,
coordinality of this. Divided by or times
the probability of each of the individual
outcomes. And since we choose the pivot
unit from them at random each one has the
probability of one over n so you get n
over two divided by n or one half. Okay,
now that we've explored the concept of
events in our running two examples, we see
that the probability that the sum of two
dice is equal to one-sixth. A useful fact
to know if you're every playing craps. And
we know that a pivot gives us a 25, 75
split or better in randomized quick sort
with fifteen percent probability, a useful
fact if you want to develop intuition for
why quick sort is in fact quick. So that's
events. Let's move on to random variables.
So random variables are basically some
statistic measuring what happens in the
random outcome. So formally if we want to
define it, it's a real value function
defined on the sample space omega. So
given an outcome, given a realization of
the randomness this gives you back a
number. Now the random variable that we
most often care about in algorithm design
is the running time of a randomized
algorithm. That's the case for example
with the quick sort algorithm. So notice
that is in fact a random variable. If we
know the state of the world, if we know
the outcome of all of the coin flips that
our code is going to make, then there is
just some running time of our algorithm.
So in that sense it's a random variable.
Given the outcomes of the coin flips, out
pops a number, the running time, say in
milliseconds of the algorithm. Here I'm
gonna give you a couple more modest
examples of random variables in our two
running examples. If we're rolling two
dice, one very simple random variable
takes as input the outcome, so that the
result of the two dice, and spits out, the
sum. So that's certainly a reign of
variable. In any given outcome it's gonna
take on some integer value between two at
the minimum and twelve at the maximum. Our
second running example is the randomly
chosen pivot made by the outermost
[inaudible] quick sort. So let's think
about the random variable which is the
size, meaning the sub array length past to
the first recursive call. Equivalently
this reign of variable is the number of
elements of the input array smaller than
the randomly chosen pivot. So, this is the
random variable that takes on some
integral value between zero at the
smallest, that's if we happen to pick the
pivot equal to the minimum of the array
and n minus one at the largest. That's if
we happen to pick the maximum element as
the pivot element. Next let's talk about
the expectation of a random variable. This
is really nothing more than the average,
and of course when you take the average of
some statistic, you want to do it weighted
by the probability of its various values.
So let's just make that precise real
quick. So consider some random variable,
capital x, the expectation, this is also
called the expected value. And the
notation is capital e square bracket, then
of the random variable. And again in
English the expectation is just the
average value, naturally weighted by the
probability of the various possible
outcomes. Or more mathematically we sum,
over everything that could happen so that
little I denote one possible outcome. We
look at the value of this random variable,
when that outcome occurs and then we
weight it times the probability of that
outcome occurring. So the next two quizzes
ask you to compute the expectation of the
two random variables that we identified on
the previous slide. So the first quiz is
about two dice and the random variable,
which is the sum of the values of those
two dice. What is the average value of
that random variable? What is its
expectation? Okay, so the answer to this
question is the second option. The average
value is seven. There's a bunch of
different ways to see that. In my opinion,
the best way to compute this is using
linearity of expectation, which is the
next concept we're gonna cover. If you
wanted to, you can just compute this by
brute force by which I mean you could
iterate over all 36 possible outcomes,
look at the value of the two dice in each
and just evaluate that sum we had in the
definition on the last slide. A slightly
sneakier way to do it if you don't know
linearity of expectation would be to pair
up the various outcomes. So, it's equally
likely that sum of the two dice is two. Or
twelve. It's equally likely to be three.
Or eleven. Four and ten and so on. Each
way of paring up these values of the two
dice results in fourteen. And when you
average you get seven. But again, this,
the right way to do this is linear of
expectation which we'll cover next. So,
the second quiz covers the second random
variable we identified. So now we're back
to Quicksort and the random pivot shows in
the outermost [inaudible] and the question
is how big, on average, an expectation is
the sub-array in the first recursive call?
Equivalently, on average how many elements
are going to be less than the randomly
chosen pivot? So the correct answer to
this quiz is the third option. In fact,
it's actually quantity N minus one over
two, not N over two, but basically half of
the elements. Again, there's sort of a
sneaky way to see this, if you want, which
is that clearly the two recursive calls
are symmetric. The expected value of the
left recursive call is going to be the
same as the size of the right recursive
call. The two recursive calls always
comprise N minus one of the elements, so
because they're symmetric, you expect half
in each, so N minus one over two in each.
Though for this problem, I think it's
perfectly fine just to compute this using
the definition of expectation. So if we
let X denote the random variable that we
care about; the sub array size. Then we
can just compute directly by summing over
all of the possible outcomes, all of the
possible choices of the pivot. So with
probability one over N we chose the
minimum of the pivot resulting in zero
elements being passed to the first
recursive call. With probability one over
N we pick the second smallest element
resulting in one element being passed to
the first recursive call. If probability
one over N we pick the third smallest
given us a summary size of two. And so on.
And then, with probability one over N, we
picked the maximum element, giving us the
sub array size of N-1. So if you just sort
of compute this sum out, you will get, as
expected, N-1 over two. So expectation is
the last definition that I'm going to give
you in this part one of the probability
review. Next if our fifth and final
concept for this video, which is linearity
of expectation. And that's not a
definition, that's more of a theorem. So
what is linearity of expectation? Well
this is a very simple property of random
variables that's super, super important.
This comes up all the time when we analyze
randomized algorithms and random processes
more generally. So what is linearity of
expectation? Well it's the following very
simple claim. Which I'll sometimes denote
just by line X for short. Suppose you've
got a bunch of random of variables defined
on the same sample space. Then if you want
to think of the expected value of the sum
of these random of variables. It doesn't
matter if you take the sum first and then
take the expectation. Or if you take the
expectations first and then the sum. That
is the expected value of a sum of random
variables. Is equal to, the sum of the
expectations of the individual random
variables. And one of the reasons lean,
linearity of expectation is so
ubiquitously useful is because it always
works no matter what these random
variables are, in particular, even when
the random variables are not independent.
Now, I haven't defined independent random
variables yet. That will come in part two
of the probability review, but hopefully
you have an intuitive sense of what
independence means. So things are
independent if knowing something about one
of the random variables doesn't influence
what you expect from the other random
variable. Now I realize the first time you
see linearity of expectation, it's a
little hard to appreciate. So first of all
as far as applications, we'll see plenty
throughout this course. Pretty much every
single application of probability that
we'll see, the analysis will involve
linearity of expectation. But it may be
hard to appreciate why this is not a
tautology. Just symbolically it may look
like it has to be true. But to point out
that there is content here. If I replace
the sums by products, then this equation
would in general be false. If the reign of
variables are not independent. So the same
thing is not true about products. It's
really about sums. [sound] So let me just
give you a trivial illustration of
linearity of expectation, point out how it
really easily allows us to evaluate the
sum of two dice. Doing our first running
example let's introduce the first random
variables X one and X two for the results
of the first and second die, respectively.
Now computing the expected value of a
single die is easy. There's only six
values to enumerate over. Contrast that
with the 36 outcomes to numerate over when
we evaluated the sum of the two dies. So
the average value of a single die, you
won't be surprised to hear, is 3.5, right?
So it ranges, integers between one and six
uniformly, so 3.5 on average and now,
using [inaudible] expectation, the sum of
two dice is simply double the average
value of a single one. So in the next
slide, I'm going to prove this property,
prove linearity of expectation. But
frankly, the proof is, is pretty trivial.
So if you don't care about the proof,
that's fine. You can skip it without loss.
I'm including it just for completeness.
And I gotta say, I don't know of another
mathematical statement which is
simultaneously so trivial to prove, and so
unbelievably useful. There's really
something remarkable about linearity of
expectation. So how does the proof go?
Well, honestly, we just write out the sum,
the definition of an expectation. We
reverse the sums, and we're done. So, let
me start with the right-hand side of the
equation. So that's, that was the sum of
the expectations of the random variables.
So now, let's just apply the definition of
expectation. So, it's just a weighted
average over the possible outcomes. And
now, instead of summing first over the,
the reign of variable j and then over the
realized outcome I, I am going to, to it
in a reversed order. I'm going to sum
first over the outcome I and then over the
random variable j. Now the probability of
outcome I is independent of j. So we can
yank the p of I outside of that inter-sum.
But now what have we got? So inside the
parentheses, we simply have the value of
the sum of the X-I's, X-X-J's on the
outcome I. And over here, we're just
averaging the sum of the X-J's with
respect to the probabilities, the P-I's.
So this is just the definition of the
expectation of the sum of the reign of
variables. So that's it. So linearity of
expectation is really just a reversal of
the double sums. Now for those of you who
are rusty on these kind of manipulations,
I just want to point out, you know this
reversal of the double sum itself, is
there's nothing complicated at all, about
what's going on. So if you want a really
pedestrian way to think about what's
happening, just imagine that we take these
sum adds, these [inaudible]. And we just
write them out in a grid, where one, or
let's just say the columns are indexed by
the random variable J and the rows are
indexed by the outcome I. And in a given
cell of this grid, we'd just write the sum
in XJI times PI And the point is both of
the double sums, both the first one and
the second one, are just the sum of all of
the entries in this grid. In the first sum
we first group things according to the row
and then sum each of them up and the
second sum, we group things according to
the column. We do column sums and then sum
up the column sums. But either way it's
just some of the entries in the grid, so
it doesn't matter which way you sum. Okay?
So reversal of double sums is just a
trivial thing. So if you get lost in the
notation with these double sums, the point
is, you can just interpret each of them in
terms of this grid. Both of these double
sums are nothing more than the sum of the
values in all of the cells of this grid.
One order of summation just says you group
first according to row sums, and then sum
those up. That's the first summation. The
second summation, you first take column
sums, and then sum those up. But of course
it doesn't matter. You just get the
results of everything in the grid, okay?
So there's no, [inaudible], no tricks up
my sleeve when I reverse these sums. It's
a totally elementary trivial thing, okay?
So, again, linearity expectation. Trivial
to prove. Incredibly useful, don't forget
it. So I want to conclude this video with
one final example in order to tie together
all of the concepts that we just learned
or just reviewed. And, it's going to be an
example of load balancing. A sign in
process used to servers. But this in fact
is quite important for the analysis of
hashing that we're going to see toward the
end of the course as well. But for now
let's just think about the, the following
simple problem. For some integer n you
have n computer processes would have to be
assigned to n servers in some way. Now
you're feeling really lazy. Okay. So
you're just gonna take each of the
processes and you're just gonna assign it
to a totally random server. Okay? With
each server equally likely to get a given
process. And the question I want to study
is, does this laziness cost you, at least
on average? So if you look at a server,
what's the expected load? So let's proceed
to the solution, the answer to this
question. So, before you start talking
about expectations, one has to be clear
about the sample space and what are the
probabilities of the various outcomes? So
remember the sample space omega just
denotes every possible thing that can
happen. So what are we doing? For each
process, we're assigning it to a random
server, so all of the things that can
happen are all of the different
assignments of these end processes to
these end servers and if you think about
it, there are N raised to the N possible
outcomes, because you have N choices for
each of the N processes. Moreover, because
each process is assigned to one of the
servers uniformly at random, each of these
[inaudible] assignments is equally likely.
Probability one over N to the N. Now that
we have a sample space, we're in a
position to define a random variable. And
we already know what random variable we
care about. We care about the average load
of a server. Now, all of the servers are
exactly the same, so we just have to focus
on one server, let's say the first server.
And look at the number of processes
assigned to it. And if you go back to the
problem statement what we're asked is to
compute the expected value of Y. The
expected number of processes assigned to a
server. [sound] Now, of course, in
principle we could go to the definition of
expectation and just compute by brute
force the sum over all possible outcomes
of the value of y and take the average.
Unfortunately there are end of the end
different outcomes. And that's a lot. So,
what can we do other than this brute force
computation? Well, recall our example of
linear of expectation and the sum of two
dice. We observed that instead of com.
Computing the sum by enumerating all
thirty-six outcomes. It was much better to
focus on a single dye, compute its
expectation and then conclude with
linearity of expectation. So we'll do the
same thing here, instead of focusing on
the sum Y, we'll focus on constituent
parts of Y. So whether or not a single
process gets assigned to the first server
and then we'll get away with that with
linearity of expectation. So, more
precisely, for a given process, J, let's
define XJ to be whether to be one if and
only if the j process gets assigned to the
first server, zero otherwise. 01 random
variables like XJ are often called
indicator random variables. That's because
they, in effect, indicate whether or not a
certain event occurs. In this case,
whether or not the [inaudible] process
gets assigned to the first server. Why did
I make this definition? Well, observe that
the total number of processes that gets
assigned to the first server is simply the
sum from J equal one to N of XJ. Xj Says
whether or not a given process; the Jade
process is on the first server. The total
number is the sum of these over all J. Now
the benefit from this maneuver is we only
to compute the expectation of a extremely
simple indicator random variable XJ. This
is like the win that we got when we're
summing up two dice by instead of having
to compute the sum, the expected value of
the sum, we just had to focus on the
expectation of a single die. That was
really easy. Similarly here the
expectation of a single XJ is really easy.
Specifically, let's write it out just
using the definition of the expectation.
So the expected value of an X J is. Well.
Let's group together all the outcomes in
which it takes on the value zero. So, the
contributions of the expectation is zero
for all of those outcomes. And then
there's the rest of the outcome where X J
takes on the value one. And in those cases
it contributes one to the expectation.
Now, obviously, we get some happy
cancellation happening here, with the zero
part, and all we have to worry about is
the probability that XJ takes on the value
one. Okay, what was XJ again? How did we
define it? Remember it's the event that,
it's one exactly when the Jth process gets
assigned to the first server. How are
processes assigned. Or, remember the
proposed solution assigned to each
process, to each of the end servers,
equally likely, with uniform probability.
So, the probability that the Jth process
gets assigned to the first server, is one
over N. So this leaves us with just the
sum, from j equal one to n, of one over n.
That is, we just sum up one over n with
itself n times. This of course is equal to
one. So summarizing, the expected number
of processes assigned to a given server is
exactly one. So really on average we don't
lose much for our laziness of just
randomly spraying the process to the
servers. On average for any given server
we do fine. And that's a good illustration
of the role that randomness plays in a lot
of algorithm designed in computer science
more generally. Often using random choices
you can do surprisingly well with very
little work and that's indeed part of the
crux of quick short, if you choose pivots
at random you get an average running time
of N log N just as good as. So at the end
of the day what we find is that the
expected number of processes assigned to a
given server; say the first server, is
just one. So, at least if we only care
about averages, we lose very little from
this trivial process of randomly spraying
the process through the server. On average
any given server has just one process on
it. This is characteristic of the role
that randomization plays in algorithm
design and computer science more
generally. Often we can get away with
really simple heuristics just by making
random choices. Of course, quicksort is
one example of that, where we get an
extremely prevalently used practical
sorting algorithm just by making randomly
chosen pivots in every recursive call.