Probabilistic Analysis and

Randomized Algorithms

Probabilistic Analysis & Randomized Alg. 1 / 53

Worst-Case Running Time

We are interested on how the running time scales with input size

Normally we are interested in worst case running time

(worst case of all inputs of a given size)

Definition - Worst-Case Running Time

I - some input
T(I) - running time for input I
T(n) - worst-case running time for input size n

T(n) = max{T(I)}inputs I of size n

Probabilistic Analysis&Randomized Alg. 2 / 53

Average-Case Running Time

We could be interested in average-case

Measure performance in ”typical” inputs
I What is a typical input?

There are algorithms with large gap between ”average performance”

and worst case.

Can we improve worst-case by adding randomization?

Probabilistic Analysis & Randomized Alg. 3 / 53

The hiring problem
Imagine you need to hire a new office assistant
Suppose you use the following algorithm:

Hiring Algorithm for n candidates

best = 0 // candidate 0 is a least-qualified dummy candidate
for i = 1 to n
interview candidate i
if candidate i is better than candidate best
best = i
hire candidate i

We will focus not on the running time, but instead on the costs
incurred by interviewing and hiring.
I Interviewing has a low cost (let’s call it ci )
I Hiring has an higher cost (let’s call it ch )
Probabilistic Analysis & Randomized Alg. 4 / 53
The hiring problem: cost

What is the cost of the algorithm?

Suppose you end up hiring m persons out of the n candidates

The total cost is O(ci n + ch m):
I No matter how many people we hire, we always interview n candidates
I The cost associated with interviewing is always used: ci n
I We can therefore focus on the hiring cost (ch m), which varies
according to the candidates and the order in which they are interviewed

Note how this models a common algorithm paradigm:

I finding a min or max value in a sequence and how often we update the
notion on who’s winning

Probabilistic Analysis & Randomized Alg. 5 / 53

The hiring problem: cost

Assume we have a total order among all the candidates

I We can compare two candidates and decide which one is better
I We can rank each candidate with an unique number from 1 to n.
We will use rank(i) to denote the rank of candidate i
(assume an higher rank means a better candidate)

The input can now be described as a permutation of h1, 2, . . . , ni

Worst-case analysis
I What is the worst possible input?
I If the candidates come in increasing ranking order, then we will need
to hire all of them: O(ch n)
I Good thing this is not always the case... In fact we don’t know in
which order will they come. What would happen on a typical case?
(what would the best-case scenario be?)

Probabilistic Analysis & Randomized Alg. 6 / 53

Probabilistic Analysis

Probabilistic Analysis
The use of probability in the analysis of algorithms:

We must have some knowledge or make assumptions about the

distribution of the input
We can then make an average-case analysis, averaging the cost
over all possible inputs
For our problem, we could assume all possible permutations are
equally likely (the ranks form an uniform random permutation).
I But what if the above is not the case? What if the real distribution is
skewed and some permutations are more likely than other?

Probabilistic Analysis & Randomized Alg. 7 / 53

Hiring Problem: a randomized algorithm

Randomized Hiring Algorithm for n candidates

randomly permute the list of candidates // the only ”new” line
best = 0 // candidate 0 is a least-qualified dummy candidate
for i = 1 to n
interview candidate i
if candidate i is better than candidate best
best = i
hire candidate i

In order to have great control over the order of the candidates, we

could explicitly choose randomly which candidate to interview next
I We now are enforcing a random order, regardless of the input!

Probabilistic Analysis & Randomized Alg. 8 / 53

Randomized Algorithms

Randomized algorithms
We call an algorithm randomized if its behavior is determined not only by
its input but also by values produced by a random-number generator

Most programming environments offer a (deterministic)

pseudorandom-number generator: it returns numbers that ”look”
statistically random

We typically refer to the analysis of randomized algorithms by talking

about the expected cost (ex: the expected running time)

We can use probabilistic analysis to analyse randomized algorithms

Probabilistic Analysis & Randomized Alg. 9 / 53

Basics of Probabilistic Analysis

Consider rolling two dice and observing the results.

We call this an experiment.
It has 36 possible outcomes:
1-1, 1-2, 1-3, 1-4, 1-5, 1-6, 2-1, 2-2, 2-3, ..., 6-4, 6-5, 6-6
Each of these outcomes has probability 1/36 (assuming fair dice)
What is the probability of the sum of dice being 7?
Add the probabilities of all the outcomes satisfying this condition:
1-6, 2-5, 3-4, 4-3, 5-2, 6-1 (probability is 1/6)

Probabilistic Analysis & Randomized Alg. 10 / 53

Basics of Probabilistic Analysis

In the language of probability theory, this setting is characterized by a

sample space S and a probability measure p.
Sample Space is constituted by all possible outcomes, which are
called elementary events
In a discrete probability distribution (d.p.d.), the probability
measure is a function p(e) (or Pr (e)) over elementary events e such
that:
I p(e) ≥ 0 for all e ∈ S
P
I p(e) = 1
e∈S
An event is a subset of the sample space.
For a d.p.d. the probability of an event is just the sum of the
probabilities of its elementary events.

Probabilistic Analysis & Randomized Alg. 11 / 53

Basics of Probabilistic Analysis

A random variable is a function from elementary events to integers

or reals:
Ex: let X1 be a random variable representing result of first die and X2
representing the second die.
X = X1 + X2 would represent the sum of the two
We could now ask: what is the probability that X = 7?

One property of a random variable we care is expectation:

Expectation
For a discrete random variable X over sample space S, the expected value
of X is:
P
E[X ] = Pr (e)X (e)
e∈S

Probabilistic Analysis & Randomized Alg. 12 / 53

Basics of Probabilistic Analysis

In words: the expectation of a random variable X is just its average

value over S, where each elementary event e is weighted according to
its probability.
Ex: If we roll a single die, the expected value is 3.5
(all six elementary events have equal probability).

One possible rewrite of the previous equation, grouping elementary

events:
Expectation (possible rewrite)
P
E[X ] = Pr (X = a)a
a

Probabilistic Analysis & Randomized Alg. 13 / 53

Basics of Probabilistic Analysis

More generally:

Expectation (rewrite using disjoint events)

For any partition of the sample space into disjoint events A1 , A2 , . . .:
Pr (Ai ) E[X |Ai ]
P P P
E[X ] = Pr (e)X (e) =
i e∈Ai i

E[X |Ai ] is the expected value of X given Ai , defined to be:

1 P
Pr (Ai ) Pr (e)X (e).
e∈Ai

Probabilistic Analysis & Randomized Alg. 14 / 53

Basics of Probabilistic Analysis

An important fact about expected values is Linearity of Expectation:

Theorem - Linearity of Expectation

For any two random variables X and Y : E[X + Y] = E[X] + E[Y]

Proof for discrete random variables:

P
E[X + Y ] = Pr (e)(X (e) + Y (e)) =
P e∈S P
= Pr (e)X (e) + Pr (e)Y (e) = E[X ] + E[Y ]
e∈S e∈S

It is not necessary that the variables are independent

This theorem is very important for the analysis of algorithms:

complicated variables become a sum of simple variables which we can
analyse separately.

Probabilistic Analysis & Randomized Alg. 15 / 53

A first example

Suppose we unwrap a fresh deck of n cards and shuffle it until the cards
are completely random.
How many cards do we expect to be in the same position as they
were at the start?

X : number of cards that end in the same position as they started

We are looking for E[X ]!
By linearity of expectation we can write this as a sum of Xi , where
Xi = 1 if the i-th card ends up in position i, and Xi = 0 otherwise:
n
P
X = X1 + X2 + . . . + Xn = Xi
i=1
Pr (Xi = 1) = 1/n where n is the number of cards!
Pr (Xi = 1) is also E[Xi ] (E[Xi ] = 1 · Pr (Xi = 1) + 0 · Pr (Xi = 0))
E[X ] = E[X1 + . . . + Xn ] = E[X1 ] + . . . + E[Xn ] = 1

Probabilistic Analysis & Randomized Alg. 16 / 53

Indicator Variables

In the previous example we used an indicator random variable:

Indicator Random Variable

The indicator
( random variable I{A} associated with event A is defined as:
1 if A occurs
I{A} =
0 if A does not occur

Indicator random variables may be very handy in simplifying our

analysis, by giving us a simpler way to model our desired cost

Note that if XA = I{A}, then E[XA ] = Pr (A)

E[XA ] = 1 · Pr (A) + 0 · Pr (A) where A is the complement of A)

Probabilistic Analysis & Randomized Alg. 17 / 53

Example using indicator variables - Birthday Paradox

Suppose we have n persons in a room. What is the expected

number of persons having the same birthday?
What is the probability that any two persons i and j have the same
birthday? (suppose birthdays are independent)
I Let’s assume a year has y = 365 days, all equally likely for a birthday
I Let bk the birthday of person k
I Probability of two persons having as birthday the day d is:
Pr (bi = d and bj = d) = Pr (bi = d) · Pr (bj = d) = y12

I Probability of two persons having the same birthday is:

y y
1 1
P P
Pr (bi = bj ) = Pr (bi = d and bj = d) = y2 = y
d=1 d=1
I More intuitively, after we choose the first birthday bi , the probability
that bj is the same is 1/y

Probabilistic Analysis & Randomized Alg. 18 / 53

Example using indicator variables - Birthday Paradox

Let’s use
( the following random indicator variable:
1 if persons i and j have the same birthday
Xij =
0 otherwise
E[Xij ] = Pr (i and j having the same birthday) = 1/y
Let X be the random variable that counts the number of pairs of
people with the same birthday:
n
P n
P
X= Xij
i=1 j=i+1

Taking expectation of both sides and applying linearity of

expectations:
n n n n
P P P P n
1 n(n−1)
E[X ] = E[ Xij ] = E[Xij ] = 2 y = 2y
i=1 j=i+1 i=1 j=i+1

Probabilistic Analysis & Randomized Alg. 19 / 53

Example using indicator variables - Birthday Paradox

n(n−1)
Expected number of persons having the same birthday: 2y
(n is the number of persons in the room; y the number of days in an year)

How many persons so that we can expect that (at least) one pair of
persons will have same birthday?
I When n(n − 1) ≥ 2y , E[X ] ≥ 1
I For the case of y = 365 the smallest integer is n = 28:
28 × 27 = 756 > 2 × 365 = 730
√
I For a given y , the answer is in the order of Θ( y)
(is this what your intuition told you when you heard the problem?)

Probabilistic Analysis & Randomized Alg. 20 / 53

Hiring Problem: a randomized algorithm

Back to our example:

Randomized Hiring Algorithm for n candidates
randomly permute the list of candidates
best = 0 // candidate 0 is a least-qualified dummy candidate
for i = 1 to n
interview candidate i
if candidate i is better than candidate best
best = i
hire candidate i

What is the expected hiring cost of this algorithm?

Probabilistic Analysis & Randomized Alg. 21 / 53

Hiring Problem: probabilistic analysis
Let’s use the following random indicator variable:
Consider
( the event the i-th iteration of the loop in the algorithm:
1 if candidate i is hired
Xi =
0 otherwise
E[Xi ] = Pr (candidate i is hired)
Because the order is random:
I Cand. i has prob. 1/i of being better than cand. 1 through i − 1
(can you see why?)
I E[Xi ] = 1/i
Let X be the number of candidates we hire. Then:
X = X1 + X2 + . . . + Xn
n n n
1/i = ln(n) + O(1)
P P P
E[X ] = E[ Xi ] = E[Xi ] =
i=1 i=1 i=1
1 1
[the sum Hn = 1 + 2
+ ··· + n
is known as the harmonic series and Hn = ln(n) + O(1)]

We interview n people, but we only hire approximately ln(n) of them!

The expected hiring cost is O(ch log n)
Probabilistic Analysis & Randomized Alg. 22 / 53
Quicksort

Quicksort Algorithm
Given array with n elements
1 Pick an element p of the array as the pivot
(or halt if the array has size 0 or 1).
2 Split the array into sub-arrays LESS, EQUAL, and GREATER by
comparing each element to the pivot
I LESS has all elements less than p
I EQUAL has all elements equal to p
I GREATER has all elements greater than p.
3 recursively sort LESS and GREATER.

The algorithm is not fully specified: how to pick the pivot?

Probabilistic Analysis & Randomized Alg. 23 / 53

Naive Quicksort

For a first version let’s do the following:

Naive Quicksort
Run Quicksort as given before, each time choosing the leftmost element
as the pivot

You can see an animation in the VisuAlgo website.

Probabilistic Analysis & Randomized Alg. 24 / 53

Naive Quicksort
Worst Case

What is the worst-case running time?

Image the array is already sorted:

The pivot will be the smallest element
In step 2, all other elements will go to GREATER
Since the GREATER array will be sorted, the process will continue,
each time with one less element
This will result in Ω(n2 ) time.
Since step 1 is executed at most n times, and step 2 takes at most n
steps, time will be O(n2 )
Thus, the worst-case running time is Θ(n2 )

(what about the best case)?

Probabilistic Analysis & Randomized Alg. 25 / 53

Naive Quicksort
Average Case

It turns out that the average-case running time is O(n log n)

(averaged over all different orderings of n elements)

Small consolation if the inputs we have are the bad ones...

(ex: almost sorted arrays)

Can we get around this problem?

Probabilistic Analysis & Randomized Alg. 26 / 53

Randomized Quicksort

Let’s now do the following:

Randomized Quicksort
Run Quicksort as given before, each time choosing random element as the
pivot

You can see an animation in the VisuAlgo website.

Probabilistic Analysis & Randomized Alg. 27 / 53

Randomized Quicksort

What is now the worst-case running time?

We will prove that for any given input array I, the expected time of
this algorithm, E[T(I)], is O(n log n).

This is the Worst-Case Expected Time bound.

Better than the average-case bound: we are no longer assuming

anything from the input!
I Ex: if the input is almost sorted, it will not affect this.
Peculiar, as before: as making the algorithm probabilistic gives us
more control over the running time.

Probabilistic Analysis & Randomized Alg. 28 / 53

Analysing Randomized Quicksort

The running time of quicksort is dominated by the number of direct

comparisons between elements, made when we are comparing with the
pivot and splitting the array into LESS, EQUAL and GREATER.
(all the other parts take O(n), as selecting the pivot takes O(1) and there
will be < 2n calls to the recursive function)

Theorem - Comparisons in Randomized Quicksort

The expected number of comparisons made by randomized quicksort on an
array of size n is O(n log n).

Let us prove this theorem using... indicator variables!

Probabilistic Analysis & Randomized Alg. 29 / 53

Analysing Randomized Quicksort

Let Xij be a random indicator variable with value:

1 if the algorithm does compare the i-th smallest and j-th smallest
elements in the course of sorting
0 if it does not

Let X denote the total number of comparisons made by the algorithm.

Since we never compare the same pair of elements twice, we have:
n−1
P n
P
X= Xij
i=1 j=i+1

And therefore
n−1
P n
P
E[X ] = E[Xij ]
i=1 j=i+1

Probabilistic Analysis & Randomized Alg. 30 / 53

Analysing Randomized Quicksort

Consider one Xij , for i < j.

Consider ek to be the element on the k-th position, and imagine the

elements in sorted order.
If the pivot is between ei and ej , then they will go to separate buckets
and we never compare them
If the pivot is ei or ej , then we do compare them
If the pivot is smaller than ei or greater than ej , then they will go to
the same bucket and we need to choose another pivot

Probabilistic Analysis & Randomized Alg. 31 / 53

Analysing Randomized Quicksort

Pr (Xij = 1) = Pr (ei or ej is selected as pivot in the interval [i, j])

This interval has size j − i + 1, and only 2 pivots out of these positions
(precisely i and j) would give origin to a comparison between ei and ej
Therefore, overall, the probability that Xij = 1 is 2/(j − i + 1).
(In words, ei is compared to ei+1 with probability 1, ei is compared to ei+2 with
probability 2/3, ei is compared to ei+2 with probability 2/4, and so on)
n−1 n n−1 n n−1
P n−i n−1 n
P P P P 2 P 2 P P 2
E[x ] = E[Xij ] = j−i+1 = k+1 < k
i=1 j=i+1 i=1 j=i+1 i=1 k=1 i=1 k=1

Probabilistic Analysis & Randomized Alg. 32 / 53

Analysing Randomized Quicksort
n−1 n n−1
2
2(Hn − 1)
P P P
E[X ] < k =
i=1 k=i i=1

Remember that 1 + 12 + 13 + 14 + . . . + n1 is denoted as Hn , and is called the

n-th Harmonic Number (as we saw before), and that Hn = O(log n)
Therefore:

E[x ] < 2n(Hn − 1) = O(n log n) (We have proved what we wanted!)

In terms of the number of comparisons it makes, Randomized Quicksort

is equivalent to randomly shuffling the input and then handing it off
to Naive Quicksort.
So, we have also proven that Naive Quicksort has O(n log n) average-case
running time.

Probabilistic Analysis & Randomized Alg. 33 / 53

Types of Randomized Algorithms

QuickSort always returns a correct result (a sorted array) but its

runtime is a random variable (with O(n log n) in expectation)
We are now going to see a different type of randomized algorithm:
the runtime is fixed, but it may give incorrect answers some of the
time.

Las Vegas Algorithms

Randomized algorithms which always output the correct answer, and
whose runtimes are random variables, are called Las Vegas algorithms.

Monte Carlo Algorithms

Randomized algorithms which always terminate in given time bound, but
output the correct answer with at least some (high) probability (say with
3/4 prob.) are called Monte Carlo algorithms.

Probabilistic Analysis & Randomized Alg. 34 / 53

The Minimum Cut Problem
We are now going to present a simple but elegant Monte Carlo
randomized algorithm for the Minimum Cut Problem
A multigraph is a graph where there might be more than one edge
between the same pair of nodes. In this lecture, when we say graph,
we mean a multigraph.
Consider a graph G = (V , E ), with number of vertices |V | = n and
number of edges |E | = m. The figure below shows an example of a
graph with n = 8 nodes and m = 11 edges.

Probabilistic Analysis & Randomized Alg. 35 / 53

The Minimum Cut Problem

Given a graph G, a cut is a set of edges whose removal splits the

graph into at least two connected components. The edges of a
cut are know as crossing edges.

A minimum cut is a cut of minimum size, that is, with the minimum
possible number of edges in it.

For the example graph given above, the minimum cut has size 1:

Probabilistic Analysis & Randomized Alg. 36 / 53

The Minimum Cut Problem
For other graphs the minimum cut might be bigger:

min cut of size 2 min cut of size 3

There might be more than one minimum cut in the same graph:

The minimum cut it at most equal to the minimum degree of any

node in G. Can you see why?
Probabilistic Analysis & Randomized Alg. 37 / 53
The Minimum Cut Problem
Motivation

This problem has a long history and is applicable in many areas:

I Imagine you want to know how ”robust” is a network in the sense of
the minimum number of links whose failure disconnects the network
I Imagine you want to partition a graph into two groups of nodes with
the least amount of connections between them
I ...

The classical way to solve this problem is to use maximum flow

algorithms, whose most efficient form can be very complex

Today we will describe a simple randomized algorithm for this task

(The algorithm was discovered by David Karger when he was a PhD student)

Probabilistic Analysis & Randomized Alg. 38 / 53

The Minimum Cut Problem
Contracting an Edge

Karger’s algorithm uses a primitive graph operation called

contracting or collapsing an edge.

To contract an edge (u, v ), we create a new node uv , keeping all the

edges between all u and v to outside nodes, and removing the
self-loops in the new node.
The following figure gives two examples of edge contractions:

We will use the notation G/(u, v) to denote the resulting graph after
contracting the edge (u, v )

Probabilistic Analysis & Randomized Alg. 39 / 53

The Minimum Cut Problem
Contracting an Edge

What happens to the minimum cut when we contract an edge?

I For any cut in G/(u, v ), there is a cut in G with the exact same
number of crossing edges
(note that the converse is not necessarily true)
I This implies that an edge contraction cannot decrease the minimum
cut size
I Moreover, it only increases the minimum cut size if the contracted edge
is part of all possible minimum cuts!

These observations are at the heart of Karger’s Algorithm.

Probabilistic Analysis & Randomized Alg. 40 / 53

The Minimum Cut Problem
Karger’s Algorithm - a first version

GuessMinCut(G) - version #1
1 Repeat while there are still more than 2 nodes in the graph
I Pick an edge (u, v ) uniformly at random in current graph G and
contract it
2 Return the only existing cut in the graph G

Let’s see examples of the algorithm running:

A run which returns a non-optimal minimum cut (with 3 edges):

A run which actually returns an optimal cut (with 2 edges):

Probabilistic Analysis & Randomized Alg. 41 / 53

The Minimum Cut Problem
Probability of being correct

An easy and simple algorithm. But how well does it do?

Theorem
GuessMinCut(G) version #1 returns a minimum cut with probability at least:
2 1 1
= n ≥ n2
n(n−1) ()2

It seems like a tiny probability of being correct... (and is!)

(for a 1000 node graph, we are claiming a 1-in-million chance of being correct!)

On the other hand, out of the 2m possible subsets of edges, this

simple algorithm zooms in a minimum cut with probability 1/n2 ...
pretty awesome, really!
(we will soon see how to make the probability much better)

Probabilistic Analysis & Randomized Alg. 42 / 53

The Minimum Cut Problem
Probability of being correct

Let’s prove the theorem of the previous slide:

There might be several minimum cuts in G. Let’s fix some minimum
cut C with k edges.
When we are at a graph with n − i nodes (i ≥ 0):
I We will have at least k(n − i)/2 edges: every node must have at least
degree k and every edge is incident to two nodes.
I If we choose edges uniformly at random, the probability we choose an
edge of C is therefore at most k out of k(n − i)/2 which is 2/(n − i).
I In other words, the probability that we don’t ”screw up” by choosing
an edge of the minimum cost on this iteration is at least 1 − 2/(n − i).

(continues on next slide)

Probabilistic Analysis & Randomized Alg. 43 / 53

The Minimum Cut Problem
Probability of being correct

The probability that the cut C survives the first iteration is at least
1 − n2 = n−2n
More generally, the probability that the cut C survives the (i + i)-th
2
iteration is at least 1 − n−i = n−i−2
n−i
So, the probability that the cut survives all the (n − 2) iterations until
we are left with a graph of two nodes is:
n−3
Y
Pr [C survives round #(i + 1)]
i=0
n−3
Y n−i −2
≥
i=0
n−i
n−2 n−3 n−4 1
= × × × ...
n n−1 n−2 3
2
= (and our proof is finished)
n(n − 1)
Probabilistic Analysis & Randomized Alg. 44 / 53
The Minimum Cut Problem
Running time

What about the running time?

Each iteration implies one contraction and costs O(n) time
(can you see how to implement it?)
The entire algorithm takes therefore O(n2 )
(we could also use a minimum spanning tree to obtain an equivalent
formulation for a O(m log m) running time, but we will not discuss it here)

We therefore now have a simple Monte Carlo algorithm with

time O(n2 ) and with probability of being correct at least n12
We want something better, and we will now see how to improve (a
lot) this probability.

Probabilistic Analysis & Randomized Alg. 45 / 53

The Minimum Cut Problem
Improving the Success Probability

One way to improve the success probability is just to... try, try again!
GuessMinCut(G, M) - (improved) version #2
1 Run the previous GuessMinCut(G) algorithm M times, independently
2 Return the smallest cut found in these M runs

The runtime of the algorithm is clearly O(Mn2 )

What about the probability?
I We are happy if at least one of the runs finds a minimum cut C
I So, if we fail, all runs must have failed to find C ! What are the odds?
Pr (all M runs fail)
= Pr (1st run fails) × Pr (2nd run fails) × . . . × Pr (M-th run fails)
1 1 1
≤ (1 − 2 ) × (1 − 2 ) × . . . × (1 − 2 )
n n n
1 M
= (1 − 2 )
n
Probabilistic Analysis & Randomized Alg. 46 / 53
The Minimum Cut Problem
Improving the Success Probability

1 M
The failure probability is at most (1 − n2
)

One of most useful inequalities ever

(1 + x ) < e x for all x ∈ R
2
Using this inequality, the failure probability is at most e −M/n
If we repeat the algorithm M = n2 ln n times, the failure probability is
at most e − ln n = 1/n
In fact, if we repeat M = cn2 ln n, the failure probability is at most
e −c ln n = 1/nc
We went from small probability of success (1/n2 ) to a small
probability of failure (1/nc )!
We have now a simple Monte Carlo algorithm with time
1
O(cn4 log n) and with probability of being incorrect at most nc

Probabilistic Analysis & Randomized Alg. 47 / 53

Monte Carlo Algorithms
Success Probability

Recall this important ”trick” with Monte Carlo algorithms:

Amplification
If you have have a Monte Carlo algorithm with a small probability of
success, you can usually repeat the algorithm independently many times
and reduce the failure probability.

When the failure probability is a polynomial fraction (like 1/nc ), we

say that the algorithm is correct with high probability

Probabilistic Analysis & Randomized Alg. 48 / 53

The Minimum Cut Problem
Improving the runtime

O(n4 log n) seems still a little high cost for our minimum cut
randomized algorithm. Can we improve the runtime?
Notice that the initial iterations are less riskier the final ones:
I In the first iteration our chance of ”screwing up” is at most 2/n
I On the last iteration this goes up to 2/3!
We are now going to talk about a speed-up idea due to D. Karger
and C. Stein (the ”S” in ”CLRS”):
First, we should run the normal algorithm in a ”safe” phase until
we have t nodes remaining:
I What would a good value of t be? Let’s try to repeat this while we still
have a cumulative chance of success higher than 1/2
I Doing the calculations like before (see slide 44), the probability that we
t(t−1)
still have a minimum cut when we have t nodes left is: n(n−1)
√ √
(n/ 2)·(n/ (2)−1)
I When we have about t = √n , then n(n−1) ≈ 12
(2)

Probabilistic Analysis & Randomized Alg. 49 / 53

The Minimum Cut Problem
Improving the runtime

The full improved algorithm is the following:

BetterGuess(G) - (improved) version #3

If n ≤ 8 then % (n = |V (G)|)
find the min-cut by brute force
Else √
H ← graph G contracted until we reach n/ 2 nodes
X1 ← BetterGuess(H)
X2 ← BetterGuess(H)
return min(X1 , X2 )

The dual recursive call is there to improve the probability of success

What is now the running time?
I This recursion corresponds to the recurrence:
T (n) = 2T ( √n2 ) + O(n2 )+ = O(n2 log n) (using master theorem)
Probabilistic Analysis & Randomized Alg. 50 / 53
The Minimum Cut Problem
Improving the runtime

Ok, so our algorithm has runtime O(n2 log n) (much better!)

But what about the probability of success? Let Pn be the probability
that a min-cut C survives in a graph with n nodes.
Pn = Pr (C survives contractions) × Pr (C survives one of the recursive calls)
1
≥ · Pr (C survives 1 of the recursive calls)
2
1
= · (1 − Pr (C is killed in both the recursive calls))
2
1
= · (1 − (1 − Pn/√2 )2 )
2
This recursion can be solved to show that Pn = Ω(1/ log n)
(a proof can be seen in the auxiliary material available at the course website; note
also√we were a little bit lose on the limit of t which should more formally be
dn/ 2 + 1e - this ”constant” factor, however, does not affect our result)
This means our probability of success is at least 1/ log n
Probabilistic Analysis & Randomized Alg. 51 / 53
Monte Carlo Algorithms
Improving the runtime

So our improved algorithm has Ω(1/ log n) success probability

[much better than the initial version, which was Ω(1/n2 )]

At the same time, the runtime is O(n2 log n)

[not that much worse than the O(n2 ) of the initial version]

Using amplification, we can also improve this success probability to

1/n (it suffices to repeat it M = log2 n times)
(using the ”most useful inequality ever”)

Because the runtime is O(Mn2 log n), we have now a Monte Carlo
algorithm with time O(cn2 log3 n) and with probability of being
incorrect at most n1c
(and that is more than enough for today...)

Probabilistic Analysis & Randomized Alg. 52 / 53

Monte Carlo vs Las Vegas

Can we transform a Las Vegas algorithm into a Monte Carlo one?

Can we transform a Monte Carlo algorithm into a Las Vegas one?

That will be one of the subjects of the exercises in homework #2 :)

Probabilistic Analysis & Randomized Alg. 53 / 53