So in the last video I left you with a
cliffhanger. I introduced you to the
minimum cut problem. I introduced you to a
very simple algorithm, randomized
algorithm, in the form of contraction
algorithm. We observed that sometimes it
finds the main cut and sometimes it
doesn't. And so the $64000 question is
just how frequently does it succeed and
just how frequently does it fail. So now
that I hope you've brushed up the
conditional probability and independence,
we are gonna give a very precise answer to
that question in this lecture. >>So
recalling this problem we are given as
input in undirected graph, possibly with
parallel edges, and that the goal is to
compute among the exponential number of
possible different cuts, that's with the
fewest number of crossing edges. So, for
example in this graph here, which you've
seen in a previous video, the goal is to
compute the cut (A, B). Here, cuz there are
only two crossing edges, and that's as
small as it gets. That's the minimum cut
problem and Karger proposed the following
random contraction algorithm based on
random sampling, so we have N-2
iterations, and the number of vertices
gets decremented by 1 in each iteration.
So we start with N vertices, we get down
to 2. And how do we decrease the number
of vertices? We do it by contracting or
fusing two vertices together. How do we
pick which pair of edges, which pair of
vertices to fuse? Well we pick one of the
remaining edges, uniformly at random. So
there's [inaudible] many edges there are
remaining. We pick each one, equally
likely. What, if the endpoints of that
edge are (u, v), then we collapse u and v
together into a single super node. So
that's what we mean by contracting two
nodes into a single vertex and then if
that causes any self-loops, and as we saw
the examples, we will in general have
self-loops, then we delete them before
proceeding. After the N-2
generations, only two vertices remain.
You'll recall that two vertices
naturally correspond to a cut. The first
group of the cut A corresponds to the
vertices that were fused into one of the
super vertices remaining at the end. The
other super vertex corresponds to the set
B the other original vertices of the
graph. >>So the goal of this lec, of this
video is to give an answer to the
following question: What is the
probability of success? Where by success,
we mean outputs a particular min cut (A, B).
So let's set up the basic notation. We're
gonna fix any with input graph, undirected
graph. As usual we use N to denote the
number of vertices and M to denote the
number of edges. We're also going to fix a
minimum cuts (A, B). If a graph has
only one minimum cut, then it's clear what
I'm talking about here. If a graph has
multiple minimum cuts, I'm actually
selecting just one of them. Because I'm gonna
focus on a distinguished minimum cut (A, B),
and we're only gonna define the
algorithm as successful if it outputs this
particular minimum cut (A, B). If it outputs
some other minimum cut, we don't count it.
We don't count it as successful. Okay. So,
we really want this distinguished minimum
cut (A, B). In addition to N and M,
we're gonna have a parameter K, which is
the size of the minimum cut. That is, it's
the number of crossing edges of a minimum
cut. For example, that cross (A, B). The K
edges that cross the minimum cut (A, B); we're
going to call capital F. So the picture
you wanna have in mind is, there is, out
there in the world, this minimum cut (A, B).
There's lots of edges with both end points
in A, lots of edges possibly with both
endpoints in B. But, there's not a whole
lot of edges with one endpoint in A and
one in endpoint in B. So the edges F,
would be precisely, these three crossing
edges here. >>So our next step is to get a
very clear understanding of exactly when
the execution of the contraction algorithm
can go wrong, and exactly when it's gonna
work, exactly when we're going to succeed.
So let me redraw the same picture from the
previous slide. So given they were hoping
that the contraction algorithm outputs
this cut (A, B) at the end of the day, what
could possibly go wrong? Well, to see what
could go wrong, suppose,, at some iteration,
one of the edges in capital F, remember F
are the edges crossing the min cut (A, B), so
it's these three magenta edges in the
picture. Suppose at some iteration one of
the edges of F gets chosen for
contraction. Well because this edge of F
has one endpoint in A and one endpoint in
B, when it gets chosen for contraction, it
causes this node from A and this node from
B to be fused together. What does that
mean? That means, in the cut that the
contraction algorithm finally outputs, this
node from A and this node from B will be
on the same side of the output cut. Okay,
so the cut output by the contraction
algorithm will have on one side both the
node from A and the node from B.
Therefore, the output of the contraction
algorithm if this happens will be a
different cut than (A, B), okay? It will not
output (A, B) if some edge of F is contracted.
>>And if you think about it, the converse is
also true. So let's assume now, that in
each of the N-2 iterations, the contraction
algorithm never contracts an edge from
capital F. Remember capital F are exactly
the edges with one endpoint in A and one
endpoint in B. So if it never contracts
any edge of F, then it only contracts
edges where both endpoints lie in capital
A or both endpoints lie in capital B.
Well, if this is the case then, vertices
from A always stick together in the fused
nodes, and vertices from B always stick
together in the fused nodes. There is
never A iteration where a node from A and
a node from B are fused together. What
does that mean? That means that when the
algorithm outputs <i>cuts</i> all of the
nodes in A have been grouped together, all
of the nodes in B have been grouped
together, in each of the two super nodes,
which means that the output of the
algorithm is indeed the desired
cut (A, B). Summarizing, the
contraction algorithm will do what we
want. It will succeed and output the cut
(A, B), if and only if it never chooses an
edge from capital F for contraction.
Therefore, the probability of success,
that is, the probability that the output
is the distinguished min cut (A, B), is
exactly the probability that never
contracts an edge of capital F. >>So, this
is what we're gonna be interested in here.
This really is the object of our mathematical
analysis, the probability that in all of
the N-2 iterations we never
contact an edge of capital F. So, to think
about that, let's think about each
iteration in isolation, and actually define
some events describing that. So for an
iteration I, let Si denote the event, that
we screw up an iteration I. With this
notation, we can succinctly say what our
goal is, so, to compute the probability of
success. What we wanna do is we wanna
compute the probability that <i>none</i> of the
events, S1, S2 up to N minus, S(N-2)
never occur. So, I'm gonna use this NOT(¬)
symbol to say that S1 does not happen. So
we don't screw up in iteration 1, we
don't screw up in iteration 2, we don't
screw up in iteration 3, and so on. All
the way up to, we don't screw up, we don't
contract anything from capital F, in the
final iteration, either. So summarizing,
analyzing the success probability of the
contraction algorithm boils down to
analyzing the probability of this event,
the intersection of the NOT Sis
with I ranging from iteration 1 to
iteration N-2. >>So we're gonna take
this in baby steps, and the next quiz will
lead you through the first one, which is,
let's have a more modest goal. Let's just
think about iteration 1. Let's
try and understand, what's the chance we
screw up, what's the chance we don't screw
up, just in the first iteration? So the
answer to this quiz is the second option.
The probability is K/M, where K is the
number edges crossing the cut (A, B),
and M is the total number of edges. And
that's just because the probability of S1, the probability we screw up, is just the
number of crossing edges. That's the
number of outcomes which are bad, which
cause which trigger S1, divided by the
number of edges. That's the total number
of things that could happen. And since all
edges are equally likely, it just boils
down to this. And by the definition of our
notation, this is exactly K/M. So this
gives us an exact calculation of the
failure probability in the first
iteration, as a function of the number of
crossing edges, and the number of overall
edges. Now, it turns out it's gonna be
more useful for us to have a bound not
quite as exact, an inequality. That's in
terms of the number of vertices N, rather
than the number of edges, M. The reason
for that is, it's a little hard to
understand how the number of edges is
changing in each iteration. It's certainly
going down by 1 in each iteration, because we
contract that in each iteration, but it
might go down by more than 1 when we
delete self-loops. By contrast the number
of vertices is this very steady obvious
process. One less vertex with each
successive iteration. >>So, let's rewrite
this bound in terms of the number of
vertices N. To do that in a useful way,
we make the following key observation. I
claim that, in the original graph G,
we are given as input, every vertex has at
least K edges incident on it, that is in
graph theoretic terminology, every edge
has degree at least K. Where, recall, K is
the number of edges crossing our favorite
min cut (A, B). So why is that true? Why
must every vertex have a decent number of
neighbors, a decent number of edges
incident to it. Well, it's because, if you
think about it, each vertex defines a cut
by itself. Remember, a cut is just any
grouping into other vertices into two
groups, that are not empty, that don't
overlap. So one cut is to take a single
vertex, and make that the first group, A,
and take the other N-1 vertices,
and make that the second group, capital B.
So how many edges cross this cut? Well,
it's exactly the edges that are incident
on the first note, on the note on the left
side. So every single cut, fall
exponentially many cuts, have at least
K crossing edges, then certainly the
N cuts defined by single vertices have at
least K crossing edges, so therefore, the
degree of a vertex is at least K. So
our assumption that every single cut in
the graph has at least K crossing edges
because it's a lower bound on the number
edges incident on each possible vertex.
>>So, why is that usual? Well let's recall
the following general facts about any graph; which
is that if you sum up over the degrees of
the nodes, so if you go node by node, look
at how many edges are insident on that
node, that's the degree of V, and then sum
them up over all vertices. What will you
get? You'll get exactly twice the number of
edges, okay? So this is true for any
undirected graph, that the sum of the
degrees of the vertices is exactly double-
the number of edges. To see this, you
might think about taking a graph, starting
with the empty set of edges, and then
adding the edges of the graph one at a
time. Each time you add a new edge to a
graph, obviously the number of edges goes
up by 1, and the degree of each of the
endpoints of that edge also go up by 1,
and there are, of course, two endpoints.
So every time you add an edge, the number
of edges goes up by 1, the sum of those
degrees goes up by 2. Therefore, when
you've added all the edges, the sum of the
degrees is double the number of edges that
you've added. That's why this is true.
Now, in this graph, at that we have a hand here,
every degree is at least K, and there's N
nodes. So this left hand side, of course,
is at least KN for us. So therefore if we
just divide through by 2, and flip the
inequality around, we have the number of
edges has to be at least the size of the
crossing cut, so the degrees of every
vertex times the number of vertices
divided by 2. So this is just the
primitive inequality rearranging. Putting
this together with your answer on the quiz,
since the probability of S1 is exactly K/M,
and M is at least KN/2, if
we substitute, we get that the probability
of S1 is at worst 2/N, 2 over
the number of vertices, and the K cancels out.
So that's, sort of, our first
milestone. We've figured out the chance
that we screw up in the first iteration,
that we pick some edge from the
crosses the cut (A, B). And things look good.
This is a, this is a small number, right?
So, in general, the number of vertices
might be quite big. And this says that
the probability we screw up is only 2
over the number of vertices. So, so far,
so good. Of course, this was only the
first iteration. Who knows what happens
later? >>So now that we understand the
chances of screwing up in the first
iteration, let's take our next baby step,
and understand the probability that we
don't screw up in either of the first two
iterations. That is, we're gonna be
interested. And the following probability.
The probability that we don't screw up in
the first iteration nor in the second
iteration. Now, as you go back to the
definition of a conditional probability,
to realize that we can rewrite an
intersection like this in terms of
conditional probabilities. Namely, as the
probability that we don't screw up in the
second iteration, given that we didn't do
it already, times the probability that we
didn't screw up in the first iteration.
Okay? So the probability that we miss all of
these K vulnerable edges and in the second
iteration given that we didn't contract
any of them in the first iteration. Now
notice this, we already have a good
understanding on the previous slide. We are
given a nice lower bound of this. We say
there's a good chance that we don't screw
up, probably at least 1-2/N. And in some sense we also have a
very good understanding of this
probability. We know this is 1 minus the
chance that we do screw up. And what's the
chance that we do screw up? Well, these K
edges are still hanging out in the graph.
Remember we didn't contract any, in the
first iteration that's what's given. So
there are K ways to screw up, and we choose
an edge to contract uniformly at random, so
the total number of choices is the number
of remaining edges. >>Now the problem is,
what's nice is we have an exact
understanding of this probability. This is
an equality. The problem is we don't have
a good understanding of this denominator.
How many remaining edges are there? We
have an upper bound on this. We know this
is at most N-1, assuming we got
rid of one edge in the previous iteration,
but actually what, if you think about it,
what we need of this quantity is a lower
bound and that's a little unclear because
in addition to contracting the one edge
and getting that out of the graph, we
might have created a bunch of self loops
and deleted all events. So it's hard to
understand exactly what this quantity is.
So instead we're gonna rewrite this bound
in terms of the numbers of the remaining
vertices, and of course we know it's
exactly N-1 vertices remaining. We
took two of the last iterations and
contracted down to 1. So how do we
relate the number of edges to the number of
vertices? Well we do it just in exactly
the same way as in the first iteration. We'll
make some more general observation. In
the first iteration, we observed that every
node in the original graph induces a cut.
Okay, with that node was on one side, the
other N-1 edges were on the other
side. But the fact that's a more general
statement, even after we've done a bunch
of contractions, any single node in the
contracted graph, even if it represents a
union of a bunch of nodes in the original
graph, we can still think of that as a cut
in the original graph. Right? So if
there's some super node in the contracted
graph, which is the result of fusing
twelve different things together, that
corresponds to a cut where those twelve
nodes in the original graph are on the one
side A, and the other N-12
vertices are on the other side of the cut,
B. So, even after contractions, as long as
we have at least two nodes in our
contracted graph, you can take any node
and think of it as half of a cut, one side
of a cut in the original graph.
>>Now remember, K is the number of edges
crossing our minimum cut (A, B), so
any cuts in the original graph G has to
have K crossing edges. So, since every
node in the contracted graph naturally
maps over to a cut in the original graph
with at least K edges crossing it, that
means, in the contracted graph, all of the
degrees have to be at least K. If you ever
had a node in the contracted graph that
had only say K-1 incident edges,
well then you'd have a cut in the original
graph with only K-1 edges
contradiction. So just like in the first
iteration, now that we have a lower bound
on the degree of every single vertex, we
can derive a lower bound on the number of
edges that remain in the graph. The number
of remaining edges is at least 1/2,
that's because when you sum over the
degrees of the vertices, you double count
the edges, times the degree of each
vertex, that we just argued that that's at
least K in this contracted graph, times
the number of vertices, that we know
there's exactly N-1 vertices left in
the graph at this point. So now what we do
is to plug this inequality, to plug this
lower bound of the number of remaining
edges, on, as we'll substitute that for
this denominator, so in lower bounding the
denominator, we upper bound this fraction,
which gives us a lower bound on 1 minus
that fraction, and that's what we want. So
what we find is that the probability that
we don't screw up in the second iteration
given that we didn't screw up in the first
iteration. Where again, by screwing up
means picking one of these K edges
crossing (A, B) to contract is at least
1-(2/(N-1)). So, that's pretty cool. We
took the first iteration, we analyzed it,
we showed the probability that we screw up
is pretty low, we succeed with probability of
at least 1-(2/N). In the
second iteration, our success probability
has dropped a little bit, but it's still
looking pretty good for reasonable values
of N, 1-(2/(N-1)). >>Now,
as I hope you've picked up, we can
generalize this pattern to any number of
iterations, so that the degree of every node of
the contracted graph remains at least K.
The only thing which is changing is the
number of vertices is dropping by 1. So,
extending this pattern to its logical
conclusion, we get the following lower
bound on the probability that the
contraction algorithm succeeds. The
probability that the contraction algorithm
outputs the cut (A, B), you recall we argued,
is exactly the same thing as the
probability that it doesn't contract
anything, any of the K crossing edges, any
of the set F in the first iteration, nor in
the second iteration, nor in the third
iteration, and then so on, all the way up to
the final (N-2)th iteration. Using the
definition of conditional probability,
this is just the probability that we
don't screw up in the first iteration,
times the probability that we don't screw
up in the second iteration given that we
didn't screw up in the first iteration,
and so on. In the previous two slides, we
showed that, we don't screw up in the
first iteration, with probability of at
least 1-(2/N). In the second
iteration, with probability at least 1-(2/(N-1)). And of course,
you can guess what that pattern looks
like. And that results in the following
product. Now, because we stop when we get
down to two nodes remaining, the last
iteration in which we actually make a
contraction, there are three nodes. And
then, the second to last iteration in
which we make a contraction, there are
four nodes. So that's where these last two
terms come from. Rewriting, this is just
(N-2)/N times (N-3)/(N-1), and so on. And now something
very cool happens, which is massive
cancellation, and to this day, this is
always just incredibly satisfying to be
able to cross out so many terms. So you
get N-2, cross it out here and now here,
there's going to be a pair of N-3s that
get crossed out, and N-4s, and so on. On the
other side, there's going to be a pair of
4s that get crossed out, and a pair of 3s
that get crossed out. And we'll be left
with only the two largest terms on the
denominator, and the two smallest terms in
the numerator, which is exactly 2/N(N-1). And to keep things
simple among friends, let's just be sloppy
and lower bound this by 1/(N^2).
So that's it. That's our analysis
of the success probability of Karger's
contraction algorithm. Pretty cool, pretty
slick, huh? >>Okay, I'll concede, probably
you're thinking "Hey, wait a minute. We're
analyzing the probability that the
algorithm succeeds, and we're thinking of
the number of vertices N as being big, so
we'll see here as a success probability of
only 1/(N^2), and that kinda sucks."
So that's a good point. Let me
address that problem. This is a low
success probability. So that's
disappointing. So why are we talking about
this algorithm, or this analysis? Well,
here's something I want to point out.
Maybe this is not so good, 1/(N^2) you're going to succeed, but
this is still actually shockingly high for
an brute-forth algorithm which honestly
seems to be doing almost nothing. This is
a nontrivial lower bound and non trivial
success probability, because don't forget,
there's an exponential number of cuts in
the graph. So if you try to just pick a
random cut i.e you put every vertex 50:50
left or right, you'll be doing way worse
than this. You'll have a success
probability of like 1/(2^N).
So this is way, way better than that. And
the fact that its inverse polynomial
means is that using repeated trials, we can
turn a success probability that's
incredibly small into a failure
probability that's incredibly small. So
lemme show you how to do that next. >>So,
we're gonna boost the success probability
of the contraction algorithm in, if you
think about it a totally obvious way.
We're gonna run it a bunch of times, each
one independently using a fresh batch of
random coins. And we're just going to
remember the smallest cut that we ever see,
and that's what we're gonna return, the
best of a bunch of repeated trials. Now
the question is, how many trials are we
gonna need before we're pretty confident
that we actually find the meant cut that we're
looking for? To answer this question
vigorously, let's define some suitable
events. So by Ti, I mean the event at the
Ith trail succeeds, that is the Ith
time we run the contraction
algorithm which does output that desired meant
cut (A, B). For those of you that watched
the part II of the probability review, I
said a rule of thumb for dealing with
independents is that, you should maybe, as
a working hypothesis, assume granted
variables are dependent, unless they're
explicitly constructed to be independent.
So here's a case where we're just gonna
define the random variables to be
independent. We're just gonna say that we
run [inaudible] the contraction algorithm
over and over again with fresh randomness
so that they're gonna be independent trials.
Now, we know that the, probability that a
single trial fails can be pretty big, could be as big as 1-1/(N^2). But,
here, now, with repeated trials, we're
only in trouble if every single trial
fails. If even one succeeds, then we find
the meant cut. So a different way of saying
that is we're interested in the
intersection of T1 and T2 and so on,
that's the event that every single trial
fails. And now we use the fact that the
trials are independent. So, the
probability that all of these things
happen is just the product of the relevant
probabilities. So, the product from I=1
to capital N of the probability of
not TI. Recall that we argued that the
success probability of a single trial was
bounded below by 1/(N^2). So
the failure probability is bounded above
by 1-1/(N^2). So since
that's true for each of the capital N
terms, you get an overall failure
probability for all capital N trials of
1 minus 1/(n^2) raised
to the capital of N. Alright, so that's a
little calculation. Don't lose sight of
why we're doing the calculation. We want
to answer this question, how many trials
do we need? How big does capital N need to
be before are confident that we get the
answer that we want? >>Okay, so to answer that
question I need a quick calculus fact,
which is both very simple and very useful.
So for all real numbers X, we have the
following inequality, 1+x is bound
above by e^x. So I'll just
give you a quick proof via picture. So
first think about the line 1+x. What
does that cross through? Well, that
crosses through the points when x is -1,
y is 0, and when x is 0, y is 1.
And it's a line, so this looks like this
blue line here. What does e^x look
like? Well, if you substitute x = 0,
it's gonna be 1. So in fact two curves
kiss each other at x = 0. But
exponentials grow really quickly, so as you
jack up x to higher positive numbers, it
becomes very, very steep. And for x
negative numbers it stays non-negative the
whole way. So this sort of flattens out
for the negative numbers. So, pictorially,
and I encourage you to, you know, type
this into your own favorite graphing
program. You see the e^x
bounds above everywhere, the line, the 1+x.
For those of you who want
something more rigorous, there's a bunch
of ways to do it. For example, you can
look at the [inaudible] expansion of
e^x at the point 0. >>What's the
point? The point is this allows us to do
some very simple calculations on our
previous upper bound on the failure
probability by working with exponentials
instead of working with these ugly one
minus whatevers raised to the whatever
term. So, let's combine our upper bound
from the previous slide with the upper
bound provided by the calculus fact. And
to be concrete, let's substitute some
particular number of capital N. So, let's
use little n^2 trials, where little
n is the number of vertices of the graph.
In which case, the probability that every
single trial fails to recover the cut (A, B)
is bounded above by e to the -1/(N^2). That's using the calculus
fact applied with X = -1/(N^2). And then we inherit the
capital N and the exponent which we just
substantiated to little n^2. So of
course the N^2 are gonna cancel,
this is gonna give us E^(-1),
also known as 1/E. So if we're
willing to do little n^2 trials,
then our failure probability has gone
from something very close to 1, to
something which is more like, say, 30 some
more percent. Now, once you get to a
constant success probability, it's very
easy to boost it further by just doing a
few more trials. So if we just add a
natural log factor, so instead of a little
n^2 trials, we do little n^2
times the natural log of the little n.
Now, the probability that everything fails
is bound and above by the 1/e that we
had last time, but still with the residual
natural log of N up top. And this is now,
merely 1/N. So I hope it's clear
what happened. We took a very simple, very
elegant algorithm, that almost always
didn't do what we want. It almost always
failed to output the cut (A, B). It did it
with only probability 1/(n^2).
But, 1/(n^2) is
still big enough that we can boost it, so
that it almost always succeeds just by
doing repeated trials. And the number of
repeated trials that we need is the
reciprocal of its original success
probability boosted by, for the
logarithmic factor. So that transformed
this almost always failing algorithm into
an almost always succeeding algorithm. And
that's a more general less, more general
algorithm technique, which is certainly
worth remembering. >>Let me conclude with a
couple comments about the running time.
This is probably the first algorithm of a
course, of the course where we haven't
obsessed over just what the running time
is. And I said, it's simple enough. It's
not hard to figure out what it is, but
it's actually not that impressive. And
that's why I haven't been obsessing over
it. This is not almost linear. This is not
a for free primitive as I've described it
here. So it's certainly a polynomial-time
algorithm; its running time is bounded
above by some polynomial in n and m. So
it's way better than the exponential time
you get from brute-force search through
all 2^n possible cuts. But it is
certainly, the way I've described it, we
gotta to n^2 trials, plus a log
factor, which I'm not even going to bother
writing down. And also, each trial, while
at the very least, you look at all the
edges, so that's going to be another
factor of M. So this is a bigger
polynomial than in any, almost any of the
algorithms that we're going to see. Now, I
don't wanna undersell this application of
random sampling in computing cuts because
I've just shown you the simplest, most
elegant, most basic, but therefore also
the slowest implementation of using
contractions to compute cuts. There's been
follow-up work with a lot of extra
optimizations, in particular, doing stuff
much more clever than just repeated
trials, so basically using work that you
did in previous trials to inform how you
look for cuts in subsequent trials. And
you can shave large factors off of the
running time. So there are much better
implementations of this randomized
contraction algorithm than what I'm
showing you here. Those are, however,
outside the course, scope of this course.