跳转至

Randomized Algorithms

Intro

  • Deterministic Algorithms: 确定输入输出

  • Randomized Algorithms: 给定固定输入 随机输出

Example

Hiring Problem

Hiring condition

有n个候选人,在结束每一次面试的时候必须立即决定是否录用并且不能反悔

  1. 选择最好的candidate
  2. 在能够保证选出最好的candidate的情况下,尽可能介绍雇佣的次数

很简单直接的思路就是每次面试到了一个在已经面试结束的candidate中最好的,然后录用,也就是一个deterministic算法。

  • 但是显然可以发现,如果candidate评估是递增的,那么这个算法会录用所有candidate,显然不是最优的。

Randomly Permute

对candidate进行随机排列后再采用确定算法,这样在期望下可以保证hire不超过lnn

Prove

设定一个事件Ai,表示第i个candidate是前i个candi中最好的,那么显然P(Ai)=1i

对每个候选者Xi,如果满足事件Ai,那么就录用,Xi=1,否则Xi=0

Xi求期望,有 $$ E[X_i] = P(A_i) \cdot 1 + (1-P(A_i)) \cdot 0 = \frac{1}{i} $$

对所有i求和,有 $$ E[\sum_{i=1}^{n} X_i] = \sum_{i=1}^{n} E[X_i] = \sum_{i=1}^{n} \frac{1}{i} \leq \ln{n}+1 $$

Variant

现在问题的变体是,如果成本有限,我们只能雇佣一个candi,这时怎样做才能最大化选到最好candi的概率

解决:

  1. Randomly Permute
  2. 面试前k个candidate,但是不雇佣
  3. for i = k+1 to n:

    如果第i个candidate比前k个candidate中最好的还要好,那么就雇佣

我们要计算选到最好candi的概率:

P(hire the best)=i=k+1nP(best is at i hire him)

我们记等号右侧前面的事件为Ai,后面的事件为Bi,那么有

=i=k+1nP(Ai)P(Bi|Ai)

A事件的概率比较好计算,对于A发生时B的概率,就是指第i个candi出现时,他是在第k到第i1个candi中最好的,也即是说在前i1个candi中,最好的那个在1k之间,那么有

=i=k+1n1iki1
=kni=kn11iknlnnk

求导可以得到当k=ne时,概率最大,为1e

3SAT Problem

对于一个给定的布尔公式是否存在一种赋值,使得该公式为真,例如:

(x1x2x4)(¬x1¬x2x4)(x1¬x2¬x3)

其中n是变量个数,k是子句clause个数

Monte Carlo

对于一个变量xi,我们令其为真的概率或者为假的概率都为0.5,那么每一个clause为真的概率为78

可以计算出在期望下,随机赋值使得3SAT问题为真的概率为78k

定义:Y为满足条件的子句个数,则E[Y]=78k

我们知道Y的期望值是这个数,那么一定有P(Y78k)0(可以反证得到)

这个算法在时间复杂度上可以保证在O(n)内解决问题,但是对于解的质量,我们只能保证在期望下有78k个是正确的

这种算法称为Monte Carlo算法

Las Vegas

我们现在想知道一个概率,就是每跑一次算法,满足条件的子句个数大于等于78k的概率是多少

大体的思路是:

取整数k,是式子78k的取整,这样我们就能将期望拆分:

78k=E[Y]=i=0kiP(Y=i)=i=0kiP(Y=i)+i=k+1kiP(Y=i)ki=0kP(Y=i)+ki=k+1kP(Y=i)=kP(Y78k)+kP(Y78k)k+kP(Y78k)

所以

kP(Y78k)78kk

k=78k,则有

P(Y78k)18k

所以也就是说在期望下,我们需要跑8k次算法,才能保证满足条件子句个数大于等于78k,也就是说解的质量是可以保证的,但是running time只能在期望下求算

这种算法称为Las Vegas算法

QuickSort

A Pivot is good if: 能均使得分出的两个子集大小大于原数组的14

  • Idea 1:randomly pick pivot,如果是好的就用,不是就重选

    P(good)=12,期望下每一层递归需要O(n)时间,所以总时间复杂度为O(nlogn)

  • Idea 2:randomly pick pivot,use it anyway

    同样有时间复杂度是O(nlogn)

Implementation

程序中的random permutation方法:

  • 设置随机键值

a1,a2,,an中,设置ai的键值为kiki1n3的随机数

键值相同的概率不会超过$\frac{1}{n}

  • Random Shuffle
for i in range(n):
    j = random.randint(1, i)
    swap(a[i], a[j])

留言

欢迎在下方交流~