Note for RA

• Why do we need randomized algorithms? (Pros and Cons)

Faster => But weaker guarantees

Simpler code but harder to analyze.

Sometimes it might be the only option, e.g., Big Data, Machine Learning, Security, etc.

• Classification of Randomized Algorithms

Las Vegas & Monte Carlo.

Las Vegas algorithms always get a good answer but don’t know how long it takes. => $RandQS(S)$.

Monte Carlo algorithms might give a wrong answer, but we have the trade-off between the running time and the probability of returning the correct solution. => $RandMinCut(G)$.

• QuickSort - Pseudocode

The basic idea of the quicksort is sorting an array by comparing each element with the selected pivot in the iteration.

function QS(S={s1, ..., sn})
Assumes all elements in S are distinct.
  if |S| <= 1 then
    return list(S)
  else
    Pick pivot x in S
    L <- {y in S | y < x}
    R <- {y in S | y > x}
    return QS(L) + [x] + QS(R)

• QuickSort - Lemma 1

In the basic algorithm, we don’t specify how to pick the pivot. However, for any pivoting strategy, QS correctly sort the numbers.

Proof - By induction on $n$.

1. $n = 0, 1$ => Trivial
2. We assume it holds for up to $n-1$ numbers.
3. Then by induction hypothesis $QS(L)$ and $QS(R)$ are sorted as their size are less or equal to $n-1$.

Hence, $QS(L) + [x] + QS(R)$ is sorted.

• RandQS(S) - Pseudocode

Randomized QuickSort Algorithm specifies the method of picking the pivot is to pick pivot $x\in S$ uniformly at random.

function RANDQS(S={s1, ..., sn})
Assumes all elements in S are distinct.
  if |S| <= 1 then
    return S
  else
    Pick pivot x in S, uniformly at random
    L <- {y in S | y < x}
    R <- {y in S | y > x}
    return RANDQS(L) + [x] + RANDQS(R)

• RandQS(S) - Analyse

If lucky, everytime we pick the middle one to be the pivot during the iteration. Then, $

L

\le \frac{n}{2}$ and $

R

\le \frac{n}{2}$. The running time is, picking pivot + comparing,

\[T(n) = O(n) + 2T(\frac{n}{2}) \\ = O(n) + 2(O(\frac{n}{2})+2T(\frac{n}{4})) \\ = O(n) + 2O(\frac{n}{2})+4O(\frac{n}{4})+ ...+nO(1) \\ =O(n)+2O(\frac{n}{2})+...+nO(1)\]

As every term except $nO(1)$ is $O(\log n)$, hence the running time is $O(n\log n)$.

If we are unlucky, the running time should be $\Omega(n^2)$.

However, we show the interest on the average time.

From the pseudocode, we can know the running time of the algorithm is dominated by the number of comparisons.

What is the expected number of comparisons? => $\mathbb{E}[#comparisons]$.

• Theorem 1

$\mathbb{E}[#comparisons] \in O(n\log n)$.

Proof

Let $[S_{(1)}, S_{(2)}, …, S_{(n)}]$ is sorted by $RANDQS(S)$.

For $i<j$ let $X_{ij}$ be the number of times that $S_{(i)}$ and $S_{(j)}$ are compared. We can observe that $X_{ij} \in {0, 1}$. That’s because if one of them is selected to be the pivot, then it will be the only opportunity to get $1$. Otherwise, they will never be compared to each other.

Then we get,

\[\mathbb{E}[\#comparisons] = \mathbb{E}[\sum_{i<j}X_{ij}]= \sum_{i<j}\mathbb{E}[X_{ij}]\]

Since $X_{ij} \in {0, 1 }$ and it is an indicator variable for the event that $S_{(i)}$ and $S_{(j)}$ are compared. Let $p_{ij}$ be the probability of $S_{(i)}$ and $S_{(j)}$ are compared.

Then, $\mathbb{E}[X_{ij}]=(1-p_{ij})\cdot0+p_{ij}\cdot1=p_{ij}$.

Then we get $\sum_{i<j}\mathbb{E}[X_{ij}] = \sum_{i<j}p_{ij}$.

• Lemma 2

$S_{(i)}$ and $S_{(j)}$ are compared if and only if $S_{(i)}$ or $S_{(j)}$ is first of the array ${S_{(i)}, …, S_{(j)}}$ to be chosen as pivot.

Proof

Thus, $p_{ij}$ is the conditional probability of picking $S_{(i)}$ or $S_{(j)}$ given that the pivot is picked uniformly at random in ${S_{(i)}, S_{(i+1)}, …, S_{(j)} }$:

\[p_{ij} = \Pr[c\in \{i, j\} | c\in \{i, i+1, ..., j\}, u.a.r.] = \frac{2}{j-i+1}\]

Therefore, we get

\[\begin{align*}\mathbb{E}[\#comparisons] &= \sum_{i<j}p_{ij}=\sum_{i<j}\frac{2}{j-i+1} \\ &=\sum_{i=1}^{n-1}\sum_{j=i}^{n}\frac{2}{j-i+1} \Leftarrow {Extend \sum_{i<j}} \\ &Let \ k = j-i+1, \ j_\min=i+1, k_\min=2,\ j_\max=n,k_\max=n-i+1 \\ &=\sum_{i=1}^{n-1}\sum_{k=2}^{n-i+1}\frac{2}{k}\\ &<\sum_{i=1}^{n}\sum_{k=2}^{n}\frac{2}{k} \Leftarrow add \ more \\ &=2n\sum_{k=2}^n \frac{1}{k} \\ &=2n((\sum_{k=1}^n\frac{1}{k})-1) \\ &=2n(H_n-1)\\ &\le 2n\int_1^n\frac{1}{x}dx\\ &=2n\ln n = O(n\log n) \end{align*}\]

• RandQS - Summary

When $

S

= n$, the $\mathbb{E}[#comparisons]<2nH_n\in O(n\log n)$ for any input.

---

• Min-cut

$Min-cut$ problem. Find the smallest set $C$, which is the subset of the edge, that can make the original graph from connect to disconnect by removing the set.

$C$ is called a min-cut, and $\lambda(G) =

C

$.

• RANDMINCUT - Pesudocode

function RANDMINCUT(V, E)
while |V| > 2 and E is not empty do
	Pick e in E u.a.r.
	Contract e and remove self-loops.
return E

• RANDMINCUT - Lemma 1

$RANDMINCUT(G)$ always returns a cut.

Proof => By induction on the number $k$ of iterations of the loop ($k\le n-2$).

1. $k=0$ is trivial.
2. Suppose that it is true for up to $k-1$ iterations.
3. First iteration constructs $G’$ by contracting an edge from $G$ and removing self-loops, and then, do at most $k-1$ further iterations starting from $G’$ so by the induction hypothesis, we return a cut in $G’$.

But every such cut is also a cut in $G$.

• RANDMINCUT - Observation

We observe that $RANDMINCUT(G)$ may return a cut of size $>\lambda(G)$.

Lemma

A specific min-cut C is returned if and only if no edge from C was contracted.

• RANDMINCUT - Theorem

For any min-cut $C$, the probability that $RANDMINCUT(G)$ returns $C$ is $\ge \frac{2}{n(n-1)}$.

Proof

The case that the algorithm can return the min-cut is all the contracted edges removed before are not in the $C$.

Thus, our goal is $\Pr[\epsilon_1\and…\and\epsilon_{n-2}]\ge\frac{2}{n(n-1)}$.

To know the probability of and operation.

Then, the goal is converted to $\prod_{i=1}^{n-2}p_i$ where $p_i=\Pr[\epsilon_i

\epsilon_1\and…\and\epsilon_{i-1}]$. => 待求，返回最小割即前i次都没有选到最小割集合里的边。=> Stage 1

---

1. We can know that $G_i = (V_i, E_i)$ has $n_i = n- i$ vertices as every time, the contraction operation will get rid of one vertex.

2. Contractions can not decrease the min-cut size, so $\lambda(G_i)\ge

   C

   $.

   • 至少等于，关于大于，因为$G_i$中的切同样也是$G$中的切，如果有小于的情况，则$G$的最小切就不是最小切。=> 同样也是上面一个观察的证明。

3. It follows that each vertex $v$ of $G_i$ has degree $d_i(v)$ at least $

   C

   $.

   If there is a $d_i(v)\min$ in $G_i$ such that $d_i(v)\min < \lambda(G_i)$, it is contradicting the original min-cut in $G_i$ is min-cut. => 挪掉一个点的度的边数，相当于把这个点挪出当前图，即图不再联通。Hence, $d_i(v)_\min \ge \lambda(G_i) \ge

   C

   $.

4. Summing up all degrees of $G_i$, with the usage of handshaking,

   

Finally, we get $

E_i

\ge \frac{1}{2}n_i

C

$. => Stage 2

第二步是条件概率公式。$n_{i-1}$ 是$i-1$次迭代剩下的点，1次少一个点，所以$n-(i-1)$。

Then, we can get $p_i \ge 1-\frac{2}{n-i+1}=\frac{n-i-1}{n-i+1}$. => Stage 3

Therefore, for a given min-cut, $\Pr[C \ is \ returned]\ge\frac{2}{n(n-1)}$.

• Tradeoff

Above

• Simple Implementation

In practice, using a “union-find” data structure the running time is as the following. => Polynomial time.

• Conversion

L -> M 在结束前停止，那么返回的一定不是最佳答案。

M -> L 重复多次，一定会返回最佳结果。