随机算法

而且出现错误的概率随着实验次数的增多而显著地减少， 即可以用时间来换取求解正确性的提高。

但Monte Carlo方法很长时间没有引入到非数值算法中来。 74年，Michael Rabin(76年Turing奖获得者, 哈佛教授, 以色列人) 在瑞典讲演时指出：有些问题，如果不用随机化的方法， 而用确定性的算法，在可以忍受的时间内得不到所需要的结果。 e.g. Presburge算术系统（其中只有加法）中的计算程序， 即使只有100个符号，用每秒1万亿次运算的机器1万亿台、 进行并行计算也需做1万亿年。但如果使用随机性的概念， 可以很快得出结果，而出错率则微乎其微。

74年Rabin关于随机化算法的思想还不太成熟，到76年，

Rabin设计了一个判定素数的随机算法，该算法至今仍是一个典范。 随机算法在分布式计算、通信、信息检索、计算几何、密码学 等许多领域都有着广泛的应用。

最著名的是在公开密钥体系、RSA算法方面的应用。 用随机化方法解决问题之例：设有一函数表达式f（x1,x2,„xn）， 要判断f在某一区域D中是否恒为0。 如果f不能用数学方法进行形式上的化简

（这在工程中是经常出现的），如何判断就很麻烦。

如果我们随机地产生一个n维的坐标（r1，r2，„ rn）D， 代入f得f（r1，r2，„ rn）≠0，则可断定在区域D内f≢0。 如果f（r1，r2，„ rn）＝0，则有两种可能：

1. 在区域D内f≡0；2. 在区域D内f≢0，得到上述结果只是巧合。 如果我们对很多个随机产生的坐标进行测试，结果次次均为0， 我们就可以断言f≢0的概率是非常之小的。 如上例所示，在随机算法中，

我们不要求算法对所有可能的输入均正确计算， 只要求出现错误的可能性小到可以忽略的程度；

另外我们也不要求对同一输入算法每次执行时给出相同的结果。 我们所关心的是算法在执行时，是否能够产生真正随机的结果。 有不少问题，目前只有效率很差的确定性求解算法，

但用随机算法去求解，可以（很快地）获得相当可信的结果。 随机算法通常分为两大类：Las Vegas算法、Monte Carlo算法。 LasVegas算法总是给出正确的结果，

但在少数应用中，可能出现求不出解的情况。 此时需再次调用算法进行计算，直到获得解为止。 对于此类算法，主要是分析算法的时间复杂度的期望值， 以及调用一次产生失败（求不出解）的概率。

Mont Carlo算法通常不能保证计算出来的结果总是正确的， 一般只能断定所给解的正确性不小于p（1＜p＜1）。

2通过算法的反复执行（即以增大算法的执行时间为代价）， 能够使发生错误的概率小到可以忽略的程度。 由于每次执行的算法是的， 故k次执行均发生错误的概率为(1-p)k。

对于判定问题（回答只能是“Yes”或“No”）， Monte Carlo法又分为两类：

1. 带双错的（two-sided error）: 回答”Yes”或”No”都有可能错。 2. 带单错的（one-sided error）：只有一种回答可能错。 Las Vegas算法可以看成是单错概率为0的Monte Carlo算法。 到底哪一种随机算法好？――依赖于应用。

在不允许发生错误的应用中（e.g. 人造飞船、电网控制等）， Monte Carlo算法不可以使用；

若小概率的出错允许的话，Monte Carlo算法比Las Vegas算法 要节省许多时间，是人们常常采用的方法。 随机算法的优点：

1. 对于某一给定的问题，随机算法所需的时间与空间复杂性，

往往比当前已知的、最好的确定性算法要好。 2. 到目前为止设计出来的各种随机算法，

无论是从理解上还是实现上，都是极为简单的。 3. 随机算法避免了去构造最坏情况的例子。

最坏情况虽有可能发生，但是它不依赖于某种固定的模式， 只是由于“运气不好”才出现此种情况。

Random Sampling问题（Las Vegas算法）

设给定n个元素（为简单起见，设为1，2，„n）， 要求从n个数中随机地选取m个数（m≢n）。 可以用一个长为n的布尔数组B来标识i是否被选中，

初始时均表为“未选中”。然后随机产生〔1，n〕之间的一个整数i，若B[i]为“未选中”，则将i加入被选中队列， 同时把B[i]标识为“已选中”，

反复执行直到m个不同的数全部被选出为止。 该算法有两个问题：

1. 当n和m很接近时(例n＝1000，m＝990)， 产生最后几个随机数的时间可能很长 （有95％以上的可能性是已选中的数）。 改进：当

nm﹥2n2时，先去产生n-m（< ）个随机数，

然后再取剩下的m个数作为选出的数。 2．当n与m相比大很多时（例：n﹥m2）， 布尔数组B对空间浪费很多。

改进：用一个允许冲突的、长为m的散列表，

来存放产生的随机数。产生一个数后，看其是否在散列表中： 若不在则将其加入，若已在则抛弃该数，再去产生下一个数。 作业：设n﹥m2，用散列表以外的数据结构来代替布尔数组B。 上述随机算法的分析：

设随机变量X表示扔硬币时，第一次碰到“正面朝上”的情况时， 已经试过的次数。X=k意味着前k-1次均向下，第k次向上。 概率表示为（p为正面朝上概率，q=1-p为背面朝上概率）：

pqk1Pr[X=k]=0k1(前k1k-1次均向下，第k次向上（)几何分布）

k1kpq按求离散期望值的方法E(X)=kPr[Xk]=（连续情况积分）

k1k1令s=kqk1k1i1q s-sq==1q

i01 s=(1q)2=

1p2

故

1E(X)=p*s=p。

（另：考虑离散与连续情况之间的关系）

设pj是这样的概率：在j-1个数已经选出的前提下，当前随机

n(j1)nj1产生的数是以前尚未选过的数的概率，则pj==n。 nj1于是qj=1-pj=n，即为： 当前随机产生的数是以前选过的j-1个数之一的概率。 设随机变量Xj（1≢j≢m）表示：在j-1个数已经选出后， 再去找出第j个不同的数时，所需要产生的整数个数。 则与前述的X类似，Xj服从几何分布： Pr[Xj=k]=pjqj

k-1

n1（k≣1,qj=1-pj）， 于是E(Xj)=p=nj1。

j2设Y表示从n个数中选出m个数时（m≢n）， 所需产生的整数个数的总和的随机变量， 则有Y=X1＋X2＋X3＋„＋Xm。 由于随机变量的线性可加性有E(Y)=

nnn11E(X1)＋E(X2)＋„＋E(Xm)=nj1 =n（nj1-nj1）

j1j1jm1m1111111）1=n（（nn1）-（） nmnm122AB在数学基础部分曾证明用积分法可得

nlogn1log(n1)≢j≢loge＋1 logej1故有A≢㏑n＋1 ，及 B≣㏑（n－m＋1）， 于是E(Y)≢n（㏑n + 1 - ㏑（n-m+1）） ≢n（㏑n + 1 - ㏑（n-m）） ≢n（㏑n + 1 - ㏑（n））（∵m≢n）

22 = n（㏑n + 1 - ㏑n + ㏑2）= n㏑2e≈1.69n 由于算法的时间复杂度T(n)正比于算法产生整数的个数总和Y， 所以，T(n)的期望值与E(Y)成常数比，即有T(n)=(n)（期望值）。

找第k小元素的随机算法（Las Vegas算法）： 在n个数中随机的找一个数A[i]=x,

然后将其余n-1个数与x比较，分别放入三个数组中： S1(元素均若（|S1|+|S2|）≣k，则第k小元素就是x；

否则就有（|S1|+|S2|）＜ k，此时调用Select(k-|S1|-|S2|,S3)。 定理：若以等概率方法在n个数中随机取数， 则该算法用到的比较数的期望值不超过4n。 （假定n个数互不相同，如果有相同的数的话，

落在S2中的可能性会更大，比较数的期望值会更小一些。） 证：设C(n)是输入规模为n时，算法中所用到的比较次数的期望值。 并设取到任一个数的概率相同。

假定用上述算法取到的数x是第j小的数（j = 1，2，„，n）。 若j＞k，则需要调用Select(k,S1)。 ∵|S1|= j-1(因为取到的x是第j小的数)，

∴调用Select(k,S1)的比较次数的期望值为C(j-1)。 若j＜k，则需要调用Select(k-j,S3) (j=|S1|+|S2|)。

∵|S3| = n-j，∴本次调用的比较次数的期望值是C(n-j)。 若j=k，则直接返回第j个元素，无需继续进行比较。 由于取j为1，2，„，n的概率相同，故有

k11nC(n) = n+nC(j1)C(nj) j1jk1(其中的n是：获得S1, S2, S3所需比较次数)

11n1C(i)C(i) =n+nC(i)C(n1)C(n2)C(nk1)=n+nikink1ikn1n1由于C(i)是非减函数（在i＜j 时，总有C(i)≢C(j) ） ∴（

ink1（证明留作作业） CiCi） 在k=n/2 时取得最大值。

ikn1n1归纳法基础：n’=1时无需比较，显然有C(n’)≢4n’。 归纳法假设：设n’＜n时，有C(n’)≢4n’。 由于C(n)是在k= n/2 时取得最大值，于是有

n11n1c(i)c(i))（注意式中的n均应为n/2，下同） C(n)≢n+n(nn2in1i22

n11n14i4i)（由归纳法假设，n’＜n≢n+n(nnin1i时，有C(n’)≢4n’）

1i（)n≢n+n(8ni22n12为奇数时n- n/2+1= n/2，故此时两和式相等）

8n1 =n+n(ii)= n+8(n*(n-1)/2 - n/2*( n/2-1)/2)

ni1i1n12≢

nn(1)n8n(n1)22n+()(本式中的2n22不向上取整)= 4n-2

由于每个元素至少被比较一次，所以C(n)≣n，

∴随机化Select算法的比较次数期望值有：n≢C(n) < 4n。 Sherwood随机化方法（属Las Vegas算法）

如果某个问题已经有了一个平均性质较好的确定性算法， 但是该算法在最坏情况下效率不高，此时引入一个随机数发生器 （通常是服从均匀分布，根据问题需要也可以产生其他的分布），将一个确定性算法改成一个随机算法，使得对于任何输入实例， 该算法在概率意义下都有很好的性能（e.g. Select, Quicksort等）。 如果算法（所给的确定性算法）无法直接使用Sherwood方法， 则可以采用随机预处理的方法，使得输入对象服从均匀分布 （或其他分布），然后再用确定性算法对其进行处理。 所得效果在概率意义下与Sherwood型算法相同。

Testing String Equality（Monte Carlo算法） 设A处有一个长字符串x（e.g. 长度为106），

B处也有一个长字符串y，A将x发给B，由B判断是否有x=y。 算法：首先由A发一个x的长度给B，若长度不等，则x≠y。 若长度相等，则采用“取指纹”的方法：

A对x进行处理，取出x的“指纹”，然后将x的“指纹” 发给B， 由B检查x的“指纹”是否等于y 的“指纹”。

若取k次“指纹”（每次取法不同），每次两者结果均相同， 则认为x与y是相等的。随着k的增大，误判率可趋于0。 常用的指纹：令I(x)是x的编码，取Ip(x)  I(x) (mod p)作为x的指纹。 这里的p是一个小于M的素数，M可根据具体需要调整， 本例中取M=2n2。由于0≢Ip(x)＜p， ∴Ip(x)的二进制传输长度不超过log2 p位。 设n是I(x)的二进制表示的长度，则有I(x)＜2n。 由于p＜M=2n2，故有log2p≢log(2n2)+1=O(log2n)。 ∴传输的长度可以大大的缩短。

例：设I(x)是106位二进制的数，即n=106，则M=2×1012≈240.8631 ∴Ip(x)的位数不超过41位，传输一次可节省约2.5万倍。 根据下面所做的分析，可知错判率小于

1106。

11030如果取5种不同的p（即k=5）求出“指纹”再传输、检查5次， 则传输量可节省5,000倍。此时错判率小于错判率分析：

B接到指纹Ip(x)后与Ip(y)比较，如果Ip(x)≠Ip(y)，当然有x≠y。 如果Ip(x)=Ip(y)而xy，则称此种情况为一个误匹配。 问题是：误匹配的概率有多大？

。

若我们总是随机地去取一个小于M的素数p，则对于给定的x和y， Pr[failure] =（使得Ip(x)=Ip(y)但xy的素数p(p＜M)的个数）／

（小于M的素数的总个数）。

n数论定理1：设(n)是小于n的素数个数，则(n)≈logn，

e误差率不超过6%。

例: n=500 1000 104 105 106 107 108 109

(n)=95 168 1229 9592 78498 6579 5761445 50847478 ∵M=2n2，Pr[failure]的分母

n2n22n22n2M(M)≈logM=log(2n2)=log22logn≈2logn=logn

eeeeee2Pr[failure]的分子 ≢ 使得Ip(x)=Ip(y)的素数p(p＜M)的个数

=能够整除︱I(x)-I(y)︱的素数p(p＜M)的个数

（∵a≡b (mod p) iff p整除︱a-b︱）

数论定理2：如果a＜2n，则能够整除a的素数个数不超过(n)个。 （只要n不是太小）

∵︱I(x)-I(y)︱＜max｛I(x),I(y)｝≢2n-1， ∴能够整除︱I(x)-I(y)︱的素数个数不超过(n)。 而满足p＜M的素数则更少，∵当n≣7时，有2n2＜2n。

1n/logen1∴Pr[failure]≢(n) / (M)≈n2/logn=n。即误匹配的概率小于n。

e ∴当n很大时，误匹配的概率很小。

设xy，如果取k个不同的小于2n2的素数来求Ip(x)和Ip(y)， 由于事件的性，因此事件均发生的概率满足乘法规则，

1即k次试验均有Ip(x)=Ip(y)但xy（误匹配）的概率小于nk。 ∴当n较大、且重复了k次试验时，误匹配的概率趋于0。

Pattern Matching（Monte Carlo算法）

给定两个字符串：X=x1,„,xn，Y=y1,„,ym，看Y是否为X的子串？ （即Y是否为X中的一段。）

该问题可用KMP算法在 O(m+n)时间里获得正确结果， 但算法比较繁琐，函数计算比较复杂。

（此问题还可用Rabin-Karp算法、Boyer-Moore算法等） 考虑随机算法（用brute-force 思想）

记X(j)=xjxj＋1„xj+m-1（从X的第j位开始、长度与Y一样的子串）， 从起始位置j=1开始到j=n-m+1，我们不去逐一比较X(j)与Y， 而仅逐一比较X(j)的指纹Ip（X(j)）与Y的指纹Ip（Y）。 由于Ip（X(j+1)）可以很方便地根据Ip（X(j)）计算出来， 故算法可以很快完成。

不失一般性,设xi(1≢i≢n) 和yj(1≢j≢m)∈{0,1}，即X, Y都是0-1串。 Ip(X(j+1)) = (xj+1„xj+m)(mod p)

=(2(xj+1„xj+m-1)+xj+m)(mod p)

=(2(xj+1„xj+m-1)+2mxj-2mxj+xj+m)(mod p) =(2(xjxj+1„xj+m-1)-2mxj+xj+m)(mod p)

（∵(xy+z)(mod p)=(x(y mod p)+z)(mod p)）

=(2 ( (xjxj+1„xj+m-1)mod p )-2mxj+xj+m)(mod p)

m(2modp)x+x)(mod p) (﹡) =(2*Ip(X(j))-jj+m

Wp∴Ip(X(j+1))可以利用Ip(X(j))及(﹡)式计算出来。 算法

1、 随机取一个小于M的素数p，置j←1； 2、 计算Ip(Y)、Ip(X(1))及Wp(=2m mod p)； 3、 While j≢n-m+1 do

{if Ip(X(j))=Ip(Y) then return j /﹡X(j)极有可能等于Y﹡/ else{使用(﹡)式计算出Ip(X(j+1))；j增1} }

4、 return 0; /﹡X肯定没有子串等于Y﹡/ 时间复杂度：

Y、X(1)、2m均只有m位（二进制数），

故计算Ip(Y)、Ip(X(1))及2m mod p的时间不超过O(m)次运算。 Ip(X(j+1))的计算：由于2*Ip(X(j))只需要在Ip(X(j))后加个0； 当xj为1时，第二部分Wp*xj就是Wp，当xj为0时该部分为0； xj+m或为0或为1，然后进行加减法（O(1)时间）就可得到

m(2modp)x+x。但此式还要对p取模。 2*Ip(X(j))-jj+m

Wpm(2modp)x≢p-1，0≢x≢1， 由于0≢2*Ip(X(j))≢2p-2，0≢jj+m

Wpm(2modp)x+x的值在[-(p-1), 2p-1]之间。 因此2*Ip(X(j))-jj+m

Wp故实际计算时，若上式是负值，则加上p后即得Ip(X(j+1))； 若为非负，则看其是否小于p，小于p则已得Ip(X(j+1))； 若大于等于p，则减去p后即得Ip(X(j+1))。 故Ip(X(j+1))的计算只需用O(1)时间。

由于循环最多执行n-m+1次，故这部分的时间复杂度为O(n)。 于是，总的时间复杂性为O(m+n)。

失败的概率：当Y≠X(j)，但Ip(Y)=Ip(X(j))时产生失败。 Ip(Y)=Ip(X(j)) 当且仅当p能整除|Y-X(j)|。 当p能整除|Y-X(j)|时，p当然也能整除

|Y-X(1)| |Y-X(2)|„|Y-X(j)|„|Y-X(n-m+1)|（∵p素数，反之也成立），

由于|Y-X(j)|不超过m个二进制位，∴|Y-X(j)|<2m。 ∴|Y-X(1)| |Y-X(2)|„|Y-X(n-m+1)| < (2m)n-m+1≢2mn。

由数论定理2(如果a＜2n，则能够整除a的素数个数不超过(n)个）， 能整除|Y-X(1)| |Y-X(2)|„|Y-X(n-m+1)|的素数个数不超过(mn)个。 于是

Pr[failure]=(Y不含在X中、但p(p＜M）能够整除|Y-X(1)| |Y-X(2)|„|Y-X(j)|„|Y-X(n-m+1)|的素数的个数）/小于M的素数的个数 ≢(mn)/ (M) = (mn)/ (2mn2) （取M=2mn2） ≈(mn/loge(mn))/(2mn2/loge(2mn2))= loge(2mn2)/2n loge(mn) (m≣2时有)≢loge((mn)2)/2n loge(mn)=1/n

即失败的概率只与X的长度有关，与Y的长度无关。 当m=n时，问题退化为判定两个字符串是否相等的问题。 本算法可以转成Las Vegas算法：

当Ip(Y)=Ip(X(j))时，不直接return j，而去比较Y和X(j), 即在return j之前加一个判断看Y和X(j)是否相等， 相等则return j ，否则继续执行循环。这样，

如果有子串X(j)与Y相匹配，该算法总能给出正确的位置 （即算法出错的概率为0）。

∵在最坏情况下算法执行O(mn)时间，

1而p能整除|I(Y)-I(X(j))|概率的不超过n，故

11O(mn)(1)＋O(mn)＝O(mn)。 算法的时间复杂性的期望值不超过nn不能整除时能够整除时作业：分别用KMP、Monte Carlo和Las Vegas算法编制3个程序， 随机生成不小于5000对的、长度不等的01串X和Y（三个程序生成相同的串），然后统计算法的执行时间、Monte Carlo算法出错的比率，并根据运行结果对三种算法进行深入的比较。注意，

先利用本题下方所给素数实现上述算法，学完素数判定算法之后， 将该算法编程，产生少量的大素数并用数组保存起来，

以供上述随机算法使用（素数判定算法写在上述随机算法之外）。 素数（每种情况给7个数）

（250以内 ） 211 223 227 229 233 239 241 （500以内 ）461 463 467 479 487 491 499 （1000以内）953 967 971 977 983 991 997 （5000以内）4957 4967 4969 4973 4987 4993 4999 （10000以内）9923 9929 9931 9941 9949 9967 9973 （100000以上）100003 100019 100043 100049 100057 100069 100103