# Randomized Algorithms (Spring 2010)/Introduction

This is the first lecture of the Randomized Algorithms class. In this lecture, I will use two examples: randomized Quicksort and Karger's min-cut algorithm, to demonstrate what randomized algorithms look like. Two basic principles are used to analyze these algorithms: linearity of expectations, and independence of events.

These two algorithms belong respectively to two important classes of randomized algorithms: Las Vegas algorithms and Monte Carlo algorithms. I will introduce their definitions at the end of this lecture.

## Randomized Quicksort

The following is the pseudocode of the famous Quicksort algorithm, whose input is a set ${\displaystyle S}$ of numbers.

• if ${\displaystyle |S|>1}$ do:
• pick an element ${\displaystyle x}$ from ${\displaystyle S}$ as the pivot;
• partition ${\displaystyle S}$ into ${\displaystyle S_{1}}$, ${\displaystyle \{x\}}$, and ${\displaystyle S_{2}}$, where all elements in ${\displaystyle S_{1}}$ are smaller than ${\displaystyle x}$ and all elements in ${\displaystyle S_{2}}$ are larger than ${\displaystyle x}$;
• recursively sort ${\displaystyle S_{1}}$ and ${\displaystyle S_{2}}$;

The time complexity of this sorting algorithm is measured by the number of comparisons.

For the deterministic quicksort algorithm, the pivot element is usually the element in a fixed position (e.g. the first one) of the ${\displaystyle S}$. This will make the worst-case time complexity ${\displaystyle \Omega (n^{2})}$, which means there exists a bad case ${\displaystyle S}$, sorting which will cost us ${\displaystyle \Omega (n^{2})}$ comparisons, every time!

It is just so unfair to have an unbeatable input for this brilliant algorithm. So we tweak the algorithm a little bit:

### Algorithm: RandQSort

• if ${\displaystyle |S|>1}$ do:
• uniformly pick a random element ${\displaystyle x}$ from ${\displaystyle S}$ as the pivot;
• partition ${\displaystyle S}$ into ${\displaystyle S_{1}}$, ${\displaystyle \{x\}}$, and ${\displaystyle S_{2}}$, where all elements in ${\displaystyle S_{1}}$ are smaller than ${\displaystyle x}$ and all elements in ${\displaystyle S_{2}}$ are larger than ${\displaystyle x}$;
• recursively sort ${\displaystyle S_{1}}$ and ${\displaystyle S_{2}}$;

### Analysis

Our goal is to analyze the expected number of comparisons during an execution of RandQSort with an arbitrary input ${\displaystyle S}$. We achieve this by measuring the chance that each pair of elements are compared, and summing all of them up due to Linearity of Expectation.

Let ${\displaystyle a_{i}}$ denote the ${\displaystyle i}$th smallest element in ${\displaystyle S}$. Let ${\displaystyle X_{ij}\in \{0,1\}}$ be the random variable which indicates whether ${\displaystyle a_{i}}$ and ${\displaystyle a_{j}}$ are compared during the execution of RandQSort. That is:

{\displaystyle {\begin{aligned}X_{ij}&={\begin{cases}1&a_{i}{\mbox{ and }}a_{j}{\mbox{ are compared}}\\0&{\mbox{otherwise}}\end{cases}}.\end{aligned}}}

Elements ${\displaystyle a_{i}}$ and ${\displaystyle a_{j}}$ are compared only if one of them is chosen as pivot. After comparison they are separated (thus are never compared again). So we have the following observation:

Claim 1: Every pair of ${\displaystyle a_{i}}$ and ${\displaystyle a_{j}}$ are compared at most once.

Therefore the sum of ${\displaystyle X_{ij}}$ for all pair ${\displaystyle \{i,j\}}$ gives the total number of comparisons. The expected number of comparisons is ${\displaystyle \mathbf {E} \left[\sum _{i=1}^{n}\sum _{j>i}X_{ij}\right]}$. Due to Linearity of Expectation, ${\displaystyle \mathbf {E} \left[\sum _{i=1}^{n}\sum _{j>i}X_{ij}\right]=\sum _{i=1}^{n}\sum _{j>i}\mathbf {E} \left[X_{ij}\right]}$. Our next step is to analyze ${\displaystyle \mathbf {E} \left[X_{ij}\right]}$ for each ${\displaystyle \{i,j\}}$.

By the definition of expectation and ${\displaystyle X_{ij}}$,

{\displaystyle {\begin{aligned}\mathbf {E} \left[X_{ij}\right]&=1\cdot \Pr[a_{i}{\mbox{ and }}a_{j}{\mbox{ are compared}}]+0\cdot \Pr[a_{i}{\mbox{ and }}a_{j}{\mbox{ are not compared}}]\\&=\Pr[a_{i}{\mbox{ and }}a_{j}{\mbox{ are compared}}].\end{aligned}}}

We are going to bound this probability.

Claim 2: ${\displaystyle a_{i}}$ and ${\displaystyle a_{j}}$ are compared if and only if one of them is chosen as pivot when they are still in the same subset.

This is easy to verify: just check the algorithm. The next one is a bit complicated.

Claim 3: If ${\displaystyle a_{i}}$ and ${\displaystyle a_{j}}$ are still in the same subset then all ${\displaystyle \{a_{i},a_{i+1},\ldots ,a_{j-1},a_{j}\}}$ are in the same subset.

We can verify this by induction. Initially, ${\displaystyle S}$ itself has the property described above; and partitioning any ${\displaystyle S}$ with the property into ${\displaystyle S_{1}}$ and ${\displaystyle S_{2}}$ will preserve the property for both ${\displaystyle S_{1}}$ and ${\displaystyle S_{2}}$. Therefore Claim 3 holds.

Combining Claim 2 and 3, we have:

Claim 4: ${\displaystyle a_{i}}$ and ${\displaystyle a_{j}}$ are compared only if one of ${\displaystyle \{a_{i},a_{j}\}}$ is chosen from ${\displaystyle \{a_{i},a_{i+1},\ldots ,a_{j-1},a_{j}\}}$.

And apparently,

Claim 5: Every one of ${\displaystyle \{a_{i},a_{i+1},\ldots ,a_{j-1},a_{j}\}}$ is chosen equal-probably.

This is because our RandQSort chooses the pivot uniformly at random.

Claim 4 and Claim 5 together imply:

{\displaystyle {\begin{aligned}\Pr[a_{i}{\mbox{ and }}a_{j}{\mbox{ are compared}}]&\leq {\frac {2}{j-i+1}}.\end{aligned}}}
 Remark: Perhaps you feel confused about the above argument. You may ask: "The algorithm chooses pivots for many times during the execution. Why in the above argument, it looks like the pivot is chosen only once?" Good question! Let's see what really happens by looking closely. For any pair ${\displaystyle a_{i}}$ and ${\displaystyle a_{j}}$, initially ${\displaystyle \{a_{i},a_{i+1},\ldots ,a_{j-1},a_{j}\}}$ are all in the same set ${\displaystyle S}$ (obviously!). During the execution of the algorithm, the set which containing ${\displaystyle \{a_{i},a_{i+1},\ldots ,a_{j-1},a_{j}\}}$ are shrinking (due to the pivoting), until one of ${\displaystyle \{a_{i},a_{i+1},\ldots ,a_{j-1},a_{j}\}}$ is chosen, and the set is partitioned into different subsets. We ask for the probability that the chosen one is among ${\displaystyle \{a_{i},a_{j}\}}$. So we really care about "the last" pivoting before ${\displaystyle \{a_{i},a_{i+1},\ldots ,a_{j-1},a_{j}\}}$ is split. Formally, let ${\displaystyle Y}$ be the random variable denoting the pivot element. We know that for each ${\displaystyle a_{k}\in \{a_{i},a_{i+1},\ldots ,a_{j-1},a_{j}\}}$, ${\displaystyle Y=a_{k}}$ with the same probability, and ${\displaystyle Y\not \in \{a_{i},a_{i+1},\ldots ,a_{j-1},a_{j}\}}$ with an unknown probability (remember that there might be other elements in the same subset with ${\displaystyle \{a_{i},a_{i+1},\ldots ,a_{j-1},a_{j}\}}$). The probability we are looking for is actually ${\displaystyle \Pr[Y\in \{a_{i},a_{j}\}\mid Y\in \{a_{i},a_{i+1},\ldots ,a_{j-1},a_{j}\}]}$, which is always ${\displaystyle {\frac {2}{j-i+1}}}$, provided that ${\displaystyle Y}$ is uniform over ${\displaystyle \{a_{i},a_{i+1},\ldots ,a_{j-1},a_{j}\}}$. The conditional probability rules out the irrelevant events in a probabilistic argument.

Summing all up:

{\displaystyle {\begin{aligned}\mathbf {E} \left[\sum _{i=1}^{n}\sum _{j>i}X_{ij}\right]&=\sum _{i=1}^{n}\sum _{j>i}\mathbf {E} \left[X_{ij}\right]\\&\leq \sum _{i=1}^{n}\sum _{j>i}{\frac {2}{j-i+1}}\\&=\sum _{i=1}^{n}\sum _{k=2}^{n-i+1}{\frac {2}{k}}&&({\mbox{Let }}k=j-i+1)\\&\leq \sum _{i=1}^{n}\sum _{k=1}^{n}{\frac {2}{k}}\\&=2n\sum _{k=1}^{n}{\frac {1}{k}}\\&=2nH(n).\end{aligned}}}

${\displaystyle H(n)}$ is the ${\displaystyle n}$th Harmonic number. It holds that

{\displaystyle {\begin{aligned}H(n)=\ln n+O(1)\end{aligned}}}.

Therefore, for an arbitrary input ${\displaystyle S}$ of ${\displaystyle n}$ numbers, the expected number of comparisons taken by RandQSort to sort ${\displaystyle S}$ is ${\displaystyle \mathrm {O} (n\log n)}$.

## Minimum Cut

Let ${\displaystyle G(V,E)}$ be a graph. Suppose that we want to partition the vertex set ${\displaystyle V}$ into two parts ${\displaystyle S}$ and ${\displaystyle T}$ such that the number of crossing edges, edges with one endpoint in each part, is as small as possible. This can be described as the following problem: the min-cut problem.

For a connected graph ${\displaystyle G(V,E)}$, a cut is a set ${\displaystyle C\subseteq E}$ of edges, removal of which causes ${\displaystyle G}$ becomes disconnected. The min-cut problem is to find the cut with minimum cardinality. A canonical deterministic algorithm for this problem is through the max-flow min-cut theorem. A global minimum cut is the minimum ${\displaystyle s}$-${\displaystyle t}$ min-cut, which is equal to the minimum ${\displaystyle s}$-${\displaystyle t}$ max-flow.

Do we have to rely on the "advanced" tools like flows? The answer is "no", with a little help of randomness.

### Karger's Min-Cut Algorithm

We will introduce an extremely simple algorithm discovered by David Karger. The algorithm works on multigraphs, graphs allowing multiple edges between vertices.

We define an operation on multigraphs called contraction: For a multigraph ${\displaystyle G(V,E)}$, for any edge ${\displaystyle uv\in E}$, let ${\displaystyle contract(G,uv)}$ be a new multigraph constructed as follows: ${\displaystyle u}$ and ${\displaystyle v}$ in ${\displaystyle V}$ are replaced by a singe new vertex whose neighbors are all the old neighbors of ${\displaystyle u}$ and ${\displaystyle v}$. In other words, ${\displaystyle u}$ and ${\displaystyle v}$ are merged into one vertex. The old edges between ${\displaystyle u}$ and ${\displaystyle v}$ are deleted.

Karger's min-cut algorithm is described as follows:

MinCut(multigraph ${\displaystyle G(V,E)}$)

• while ${\displaystyle |V|>2}$ do
• choose an edge ${\displaystyle uv\in E}$ uniformly at random;
• ${\displaystyle G=contract(G,uv)}$;
• return the edges between the only two vertices in ${\displaystyle V}$;

A better way to understand Karger's min-cut algorithm is to describe it as randomly merging sets of vertices. Initially, each vertex ${\displaystyle v\in V}$ corresponds to a singleton set ${\displaystyle \{v\}}$. At each step, (1) a crossing edge (edge whose endpoints are in different sets) is chosen uniformly at random from all crossing edges; and (2) the two sets connected by the chosen crossing-edge are merged to one set. Repeat this process until there are only two sets. The crossing edges between the two sets are returned.

### Analysis

For a multigraph ${\displaystyle G(V,E)}$, fixed a minimum cut ${\displaystyle C}$ (there might be more than one minimum cuts), we analyze the probability that ${\displaystyle C}$ is returned by the MinCut algorithm. ${\displaystyle C}$ is returned by MinCut if and only if no edge in ${\displaystyle C}$ is contracted during the execution of MinCut. We will bound this probability ${\displaystyle \Pr[{\mbox{no edge in }}C{\mbox{ is contracted}}]}$.

 Lemma 1 Let ${\displaystyle G(V,E)}$ be a multigraph with ${\displaystyle n}$ vertices, if the size of the minimum cut of ${\displaystyle G}$ is ${\displaystyle k}$, then ${\displaystyle |E|\geq nk/2}$.
Proof.
 It holds that every vertex has at least ${\displaystyle k}$ neighbors, because if there exists ${\displaystyle v}$ with ${\displaystyle neighbors, then the ${\displaystyle edges adjacent to ${\displaystyle v}$ disconnect ${\displaystyle v}$ from the rest of ${\displaystyle G}$, forming a cut of size smaller than ${\displaystyle k}$. Therefore ${\displaystyle |E|\geq kn/2}$.
${\displaystyle \square }$
 Lemma 2 Let ${\displaystyle G(V,E)}$ be a multigraph with ${\displaystyle n}$ vertices, and ${\displaystyle C}$ a minimum cut of ${\displaystyle G}$. If ${\displaystyle e\not \in C}$, then ${\displaystyle C}$ is still a minimum cut of ${\displaystyle contract(G,e)}$.
Proof.
 We first show that no edge in ${\displaystyle C}$ is lost during the contraction. Due to the definition of contraction, the only edges removed from ${\displaystyle G}$ in a contraction ${\displaystyle contract(G,e)}$ are the parallel-edges sharing both endpoints with ${\displaystyle e}$. Since ${\displaystyle e\not \in C}$, none of these edges can be in ${\displaystyle C}$, or otherwise ${\displaystyle C}$ cannot be a minimum cut of ${\displaystyle G}$. Thus every edge in ${\displaystyle C}$ remains in ${\displaystyle G}$. It is then obvious to see that ${\displaystyle C}$ is a cut of ${\displaystyle contract(G,e)}$. All paths in a contracted graph can be revived in the original multigraph by inserting the contracted edges into the path, thus a connected ${\displaystyle contract(G,e)-C}$ would imply a connected ${\displaystyle G-C}$, which contradicts that ${\displaystyle C}$ is a cut in ${\displaystyle G}$. Notice that a cut in a contracted graph must be a cut in the original graph. This can be easily verified by seeing contraction as taking the union of two sets of vertices. Therefore a contraction can never reduce the size of minimum cuts of a multigraph. A minimum cut ${\displaystyle C}$ must still be a minimum cut in the contracted graph as long as it is still a cut. Concluding the above arguments, we have that ${\displaystyle C}$ is a minimum cut of ${\displaystyle contract(G,e)}$ for any ${\displaystyle e\not \in C}$.
${\displaystyle \square }$

Let ${\displaystyle G(V,E)}$ be a multigraph, and ${\displaystyle C}$ a minimum cut of ${\displaystyle G}$.

Initially ${\displaystyle |V|=n}$. After ${\displaystyle (i-1)}$ contractions, denote the current multigraph as ${\displaystyle G_{i}(V_{i},E_{i})}$. Suppose that no edge in ${\displaystyle C}$ has been chosen to be contracted yet. According to Lemma 2, ${\displaystyle C}$ must be a minimum cut of the ${\displaystyle G_{i}}$. Then due to Lemma 1, the current edge number is ${\displaystyle |E_{i}|\geq |V_{i}||C|/2}$. Uniformly choosing an edge ${\displaystyle e\in E_{i}}$ to contract, the probability that the ${\displaystyle i}$th contraction contracts an edge in ${\displaystyle C}$ is given by:

{\displaystyle {\begin{aligned}\Pr _{e\in E_{i}}[e\in C]&={\frac {|C|}{|E_{i}|}}&\leq |C|\cdot {\frac {2}{|V_{i}||C|}}&={\frac {2}{|V_{i}|}}.\end{aligned}}}

Therefore, assuming that ${\displaystyle C}$ is intact after ${\displaystyle (i-1)}$ contractions, the probability that ${\displaystyle C}$ survives the ${\displaystyle i}$th contraction is at least ${\displaystyle 1-2/|V_{i}|}$. Note that ${\displaystyle |V_{i}|=n-i+1}$, because each contraction decrease the vertex number by 1.

In each iteration, the contracted edge is independently chosen from the current graph. The probability that the minimum cut ${\displaystyle C}$ survives all ${\displaystyle (n-2)}$ contractions is at least

{\displaystyle {\begin{aligned}\prod _{i=1}^{n-2}\left(1-{\frac {2}{|V_{i}|}}\right)&=\prod _{i=1}^{n-2}\left(1-{\frac {2}{n-i+1}}\right)\\&=\prod _{k=3}^{n}{\frac {k-2}{k}}\\&={\frac {2}{n(n-1)}}.\end{aligned}}}

Therefore, we prove the following theorem,

 Theorem For any multigraph with ${\displaystyle n}$ vertices, the MinCut algorithm returns a minimum cut with probability at least ${\displaystyle {\frac {2}{n(n-1)}}}$.

Run MinCut independently for ${\displaystyle n(n-1)/2}$ times and return the smallest cut returned. The probability that this the minimum cut is found is:

{\displaystyle {\begin{aligned}1-\Pr[{\mbox{failed every time}}]&=1-\Pr[{\mbox{MinCut fails}}]^{n(n-1)/2}\\&\geq 1-\left(1-{\frac {2}{n(n-1)}}\right)^{n(n-1)/2}\\&\geq 1-{\frac {1}{e}}.\end{aligned}}}

A constant probability!

## Las Vegas and Monte Carlo

Las Vegas（赌徒）
A randomized algorithm is called Las Vegas if its output is always correct but its running time is a random variable. Randomized quicksort is an example of Las Vegas algorithm. Its output is always a sorted table, but the running time is random.
Usually the analysis of a Las Vegas algorithm tries to bound the expected running time, or bound the running time with high probability.
Monte Carlo（醉汉）
A randomized algorithm is called Monte Carlo if its running time is fixed, but the correctness of the output is a random variable. Karger's min-cut algorithm is an example of Monte Carlo algorithm.
The analysis of a Monte Carlo algorithm tries to bound the probability of errors, the probability that the output is incorrect.

What if both the running time and the correctness are random? Sometimes, we also call it Monte Carlo.

A Las Vegas algorithm can be transformed to a Monte Carlo algorithm with fixed time complexity by truncating: fix a time threshold and force terminating once the running time pass the threshold.

A Monte Carlo algorithm can be transformed to a Las Vegas algorithm by independent trials until the correct solution is returned. Note that this method relies on the efficiency of checking the correctness of a solution. The resulting Las Vegas algorithm is efficient only when the correctness can be efficiently verified.