⭐文章目录⭐
👇
Randomized Algorithms
Definition
Algorithms make random decisions as the algorithm processes the worst-case input.
Examples
Hiring Problem(Secretary Problem)
There are n candidates and we need to hire the best candidates.We can only decide whether to hire a candidate or not before we meet the next candidate.
Problem1
Our goal is to minimize the total number of hired candidates.
Solution1
randomly permute all the candidates
for each candidate:
if candidate is better than the current best candidate:
hire the candidate
Expectation Analysis
$$x_i=\begin{cases}1,\quad i\ is\ hired\\0,\quad otherwise\end{cases}$$$$X=\sum_{i=1}^n x_i$$$$E(X)=\sum_{i=1}^n E(x_i)=\sum_{i=1}^n Pr(x_i=1)=\sum_{i=1}^n\frac{1}{i}\in[ln(n+1),ln(n)+1]$$
Online-Hiring Problem
Our goal is to hire only once and maximize the probality that the best candidate is hired.
Solution2
randomly permute all the candidates
for i = k+1 to n:
if candidate i is better than the first k candidates:
hire candidate i
break
Expectation Analysis
We define $Pr[S]$ as the probability that the best candidate is hired,$Pr[A_i]$ as the probability that the best candidate is at position $i$ and $Pr[B_i]$ as the probability that the candidate $i$ is hired.
$$Pr[S]=\sum_{i=k}^n Pr[A_i\cap B_i]=\sum_{i=k}^n Pr[A_i]Pr[B_i|A_i]=\frac{1}{n}\sum_{i=k}^n Pr[B_i|A_i]=\frac{1}{n}\sum_{i=k}^n\frac{k}{i-1}$$$$\geq \frac{k}{n}ln(\frac{n}{k})$$
When $k=\frac{n}{e}$, $Pr[S]_{min}=\frac{1}{e}$.
How to Randome Permute?
Idea1
Give each candidate a unique, random ID, and permute based on the ID.
For a candidate $i$,its ID $k_i=random(1,n^3)$.$$Pr[k_i=k_j\ for\ som\ i,j]\leq\sum_{i\neq j}Pr[k_i=k_j]\leq \sum_{i\neq j}\frac{1}{n^3}\leq\frac{1}{n} $$
Idea2
Random shaffle:
for i=n to 1:
j=random(i)
swap a_i and a_j
Quick Sort:
Quicksort(A):
if |A| < = 3:
trivial sort
else:
choose a pivot p from A
A_1={a in A; a < p}
A_2={a in A; a > p}
Quicksort(A_1)
Quicksort(A_2)
A=A_1 + A_2
return A
A pivot is good if $\frac{1}{4}|A|\leq |A_1|,|A_2|\leq \frac{3}{4}|A|$.
If we choose a pivot in the head ,tail or middle, we can not ensure the pivot is good.
How to pick a good pivot?
Pick another if not good.This takes $O(n\log n)$ steps in expectation.
Theorem
As we know about the QuickSort algorithm, the total running time equals to the times of total comparisons.
Set $A=a_1<a_2<…<a_n$.
for $a_i,a_j\in A$,
$$x_{ij}=\begin{cases}1\quad if\ a_i\ and\ a_j\ is\ compared\\0\quad otherwise\end{cases}$$
$$E(X)=\sum_{i}\sum_{j>i}E(x_{ij})=\sum_{i}\sum_{j>i}Pr[a_i\ and\ q_i\ are\ compared]$$$$=\sum_{i}\sum_{j>i}\frac{2}{j-i+1}=O(n\log n)$$
MAX-3SAT Problem
Description
e.g. Given $F:(x_1\cap x_2\cap x_3)\cup (x_2\cap \bar{x_3}\cap \bar{x_5})\cup (x_1\cap x_4)$,determine if there exists a set of ${x}$, F=1.
Solution
We set $x_i=1$ for probability $\frac{1}{2}$.And we define $k$ as the number of clauses in $F$ and $Y$ as the number of clauses satisfied.
$$E[Y]=\frac{7}{8}k\quad k’=\lfloor\frac{7}{8}k\rfloor$$$$\frac{7}{8}k=E[Y]=\sum_{i=0}^{k}iPr[Y=i]\leq k’\sum_{i=0}^{k’}Pr[Y=i]+\sum_{i=k’+1}^{k}Pr[Y=i]$$$$\leq k’Pr[Y\leq K’]+kPr[Y\geq k’]\leq k’+kPr[Y\geq \frac{7}{8}k]$$$$Pr[Y\geq \frac{7}{8}k]\geq\frac{1}{8k}$$