1、第第9章章 随机算法随机算法9.1 概率论预备知识概率论预备知识9.2 对随机快速排序算法的分析对随机快速排序算法的分析9.3 随机算法的分类及其局限性随机算法的分类及其局限性 9.3.1 拉斯维加斯型拉斯维加斯型随机算法随机算法 9.3.2 蒙特卡洛蒙特卡洛型型随机算法随机算法 9.3.3 随机算法的局限性随机算法的局限性9.4 素数检验和多项式恒等检验素数检验和多项式恒等检验 9.4.1 素数检验素数检验 9.4.2 多项式恒等检验多项式恒等检验9.5 随机游动算法随机游动算法 9.5.1 有限有限马氏链及其表示马氏链及其表示 9.5.2 求解二元布尔可满足问题的随机游动算法求解二元布尔可
2、满足问题的随机游动算法 9.1 概率论预备知识概率论预备知识 事件、概率、分布事件、概率、分布 独立、条件概率独立、条件概率 期望、方差期望、方差 马尔科夫、詹森、契比雪夫不等式马尔科夫、詹森、契比雪夫不等式 并的界、切诺夫界并的界、切诺夫界.有限概率空间有限概率空间 有限概率空间有限概率空间 存在着有穷个存在着有穷个基本事件基本事件 每个基本事件发生的每个基本事件发生的概率概率是是0,1中的数中的数 所有基本事件的概率之和等于所有基本事件的概率之和等于1 例例子子 抛掷一枚均匀硬币抛掷一枚均匀硬币 基本事件基本事件：正面正面向上向上，反面反面向上向上 各自概率都为各自概率都为 1/2 抛掷一
3、枚均匀的六面抛掷一枚均匀的六面骰子骰子 基本事件基本事件：得到得到 1、2、3、4、5、6点之一点之一 概率各为概率各为 1/6事件与概率事件与概率 事件及其概率事件及其概率 一些基本事件的组合称为一些基本事件的组合称为事件事件 事件发生的事件发生的概率概率等于其中基本事件的概率之和等于其中基本事件的概率之和 例例子子 抛掷一枚均匀的六面抛掷一枚均匀的六面骰子，骰子，掷掷骰子骰子得到得到偶数偶数这一事件，这一事件，由由2、4、6点这三个基本事件组成点这三个基本事件组成，概率为概率为 1/6+1/6+1/6=1/2 通常把事件通常把事件A的概率记为的概率记为 PrA.设设A1,A2,An都是事件
4、，事件都是事件，事件Ai的概率为的概率为PrAi，则则 这个不等式称为这个不等式称为并的界并的界 niiniiAA11PrPr随机变量随机变量与分布与分布 随机变量随机变量是从概率空间到实数的映射是从概率空间到实数的映射.随机变量取各种值的概率就是随机变量取各种值的概率就是分布分布.例如，抛掷一枚均匀硬币例如，抛掷一枚均匀硬币n次，记录正面向上的次，记录正面向上的次数，就得到一个随机变量次数，就得到一个随机变量X，其取值范围是，其取值范围是 0,1,2,n,X 的分布可以描述为的分布可以描述为 称为称为二项分布二项分布.在涉及二项分布的计算中，常常在涉及二项分布的计算中，常常 需要估计需要估计
5、 的阶，常用的公式为的阶，常用的公式为niniX 2Pr knkkkenknkn 随机变量的随机变量的期望期望及运算及运算 随机变量的加权平均值称为随机变量的加权平均值称为期望期望，通常把随机变通常把随机变量量 X 的期望记作的期望记作 EX 例如，例如，前前述二项式分布随机变量述二项式分布随机变量X的期望为的期望为 随机变量随机变量 X+Y 与与 aX 设设X,Y 是同一个概率空间上的两个随机变量是同一个概率空间上的两个随机变量，可以定义可以定义新的随机变量新的随机变量 X+Y 和和 aX(a为常数为常数),X+Y 在某个基本事件上的取值就是在某个基本事件上的取值就是 X 与与 Y 的取值之
6、和的取值之和 aX 的的取值是取值是 X 取值的取值的 a 倍倍 nniiniX 2E0期望的线性性质期望的线性性质 随机变量期望有随机变量期望有线性性质线性性质：EaX+bY=aEX+bEY 特别当特别当 时，有时，有 例例如如设设 Xi 表示第表示第 i 次抛掷硬币的结果次抛掷硬币的结果，1表示正面表示正面向上，向上，0表示反面向上表示反面向上，则，则上述上述 X 的期望值的期望值 niiXX1 niiXX1EE21210211E iX niniinXX11221EE马尔科夫不等式马尔科夫不等式、条件概率、条件概率 马尔可夫不等式马尔可夫不等式X是是取值非负的随机变量取值非负的随机变量 来
7、说，来说，则有则有 Pr X kEX 1/k 或者或者 Pr X k EX/k 条件概率条件概率 在事件在事件B发生的条件下，事件发生的条件下，事件A发生的概率称为发生的概率称为条件概率条件概率，记作记作 PrA|B，计算公式为计算公式为 PrA|B=PrA B/PrB独立随机变量独立随机变量 若若PrA|B=PrA，或者等价地，或者等价地PrA B=PrAPrB，则说事件则说事件A,B是是独立事件独立事件.对于随机变量对于随机变量 X,Y 来说，若对所有可能的取值来说，若对所有可能的取值 x,y，事件，事件X=x和和Y=y都是独立的，则说都是独立的，则说 X,Y 是是独独立随机变量立随机变量
8、.对于独立随机变量，有对于独立随机变量，有EXY=EXEY.完全独立完全独立 一组随机变量一组随机变量X1,X2,Xn称为称为完全独立完全独立，如果，如果对于任何对于任何S 1,2,n，有，有 对于完全独立的随机变量对于完全独立的随机变量 X1,X2,Xn，有，有 SiiSiiXXPrPr niiniiXX11EE方差方差 随机变量与期望之差的平方加权平均值称为随机变量与期望之差的平方加权平均值称为方差方差，记作，记作 VarX 计算公式为计算公式为VarX=E(X Ex)2=EX2(EX)2.注意注意总是有总是有EX2 (EX)2，这称为这称为詹森不等式詹森不等式 若若随机变量随机变量X1,
9、X2,Xn是两两独立的，则是两两独立的，则VarVar11ininiiXX 标准差标准差 方差的平方根叫做方差的平方根叫做标准差标准差，记作，记作，即，即 如果如果随机变量随机变量 X 的方差为的方差为 2，则对于任意，则对于任意的的 k0,有有Pr|X EX|k 1/k2 这称为这称为契比雪夫不等式契比雪夫不等式 VarX 切诺夫界切诺夫界 如果随机变量如果随机变量X1,X2,Xn是完全独立的，并且每是完全独立的，并且每个个Xi取值在取值在0,1中，设中，设 ，则对于任何，则对于任何 0，有，有 以及对任何以及对任何c 0，有，有 三个三个不等式统称不等式统称为为切诺夫界切诺夫界.niiX1
10、EniiX )(11)(1e)1(PrniiX )(11)(1e)1(PrPrccniicX2/,4/min12e2|Pr|算法算法9.1输入：输入：包含包含n个元素的数组个元素的数组输出：经过排序的输出：经过排序的n个元素的数组个元素的数组1.若数组包含若数组包含0或或1个元素则返回个元素则返回 2从数组中随机选择一个元素作为从数组中随机选择一个元素作为枢轴枢轴元素元素 3把数组元素分为三个子数组，按照把数组元素分为三个子数组，按照A,B,C顺序排顺序排列列 A：包含比枢轴元素小的元素；：包含比枢轴元素小的元素；B：包含与枢轴元素相等的元素；：包含与枢轴元素相等的元素；C：包含比枢轴元素大的
11、元素：包含比枢轴元素大的元素.4对对A和和C递归地执行上述步骤递归地执行上述步骤.9.2 对随机快速排序算法的分析对随机快速排序算法的分析随机快速排序举例随机快速排序举例 6,2,7,0,5,8,1,3,4,9 6,2,7,0,5,8,1,3,4,9 2,0,5,1,3,4,6,7,8,9 2,0,5,1,3,4,6,7,8,9 0,1,2,5,3,4,6,7,8,9 0,1,2,5,3,4,6,7,8,9 0,1,2,3,4,5,6,7,8,9 说明说明:总是选每段第一个元素作总是选每段第一个元素作枢轴枢轴元素元素定理定理9.1 定理定理9.1 设数组含设数组含n个不同元素，对任意常数个不同
12、元素，对任意常数 0，随机快速排序算法的期望比较次数，随机快速排序算法的期望比较次数T(n)2 n ln n.证明证明：两种不同的证法。：两种不同的证法。证明一：求解证明一：求解递推式递推式 证明二：利用期望的证明二：利用期望的线性性质线性性质证明一证明一 证明一证明一选定枢轴元素后，其余选定枢轴元素后，其余n-1个元素每个都个元素每个都要与枢轴元素比较一次，要与枢轴元素比较一次，以以决定在子数组决定在子数组A,B,C 中的归属中的归属。枢轴元素在排序后的数组中枢轴元素在排序后的数组中可能可能位于第位于第i个位置个位置上上(i=1,2,n)，A和和C中的元素个数分别可能是中的元素个数分别可能是
13、i个和个和n-i-1个。个。由于枢轴元素是随机选取的，枢轴元素在排序由于枢轴元素是随机选取的，枢轴元素在排序后的数组中位于第后的数组中位于第i个位置上个位置上(i=1,2,n)的概率的概率都是都是1/n，所以有递推式，所以有递推式)1()(1)1()(10 niinTiTnnnT证明一证明一(续续)由由例例1.14知知这个递推式的解是这个递推式的解是(nlogn)，可用数学归纳法证明这个递推式更精确的上界，可用数学归纳法证明这个递推式更精确的上界，即即T(n)2n ln n.nnnnnnndiiinniinnnTnniln2)2/12/ln(2)1()ln2(2)1()ln2(2)1()(22
14、110 证明二证明二 首先定义随机变量首先定义随机变量Xij：其中第其中第i小和第小和第j小指排序后的数组中的位置小指排序后的数组中的位置.算法的总共的比较次数为算法的总共的比较次数为 期望运行时间为期望运行时间为 否否则则小小元元素素小小元元素素和和第第若若算算法法比比较较第第01jiXij 111ninijijX 111111EE)(ninijijninijijXXnT1Pr0Pr01Pr1E ijijijijXXXX证明二证明二(续续)在排好序的数组上进行投标游戏：在排好序的数组上进行投标游戏：若若标投在第标投在第i小和第小和第j小元素之外，则继续投标小元素之外，则继续投标 若若标投在第
15、标投在第i小和第小和第j小元素之间，或投在这两个元素之小元素之间，或投在这两个元素之上，则游戏结束上，则游戏结束.游戏结束时游戏结束时Xij1当且仅当把标投在第当且仅当把标投在第i小和第小和第j小元素小元素之上之上 12)(2)(Pr 1Pr ijjijiXij的的元元素素个个数数含含小小之之间间和和第第在在第第把把标标投投在在这这两两个个元元素素含含小小元元素素之之间间和和第第在在第第证明二证明二(续完续完)其中调和级数其中调和级数 满足满足 ln n Hn 1 或或 则宣布则宣布“n是合数是合数”3.否则宣布否则宣布“n是素数是素数”)(mod2/)1(nanan 定理定理9.2 定理定理
16、9.2 素数检验算法在多项式时间内运行素数检验算法在多项式时间内运行.当当n是是素数时，素数检验算法总是输出正确结果；当素数时，素数检验算法总是输出正确结果；当n不是素数时，素数检验算法至少以概率不是素数时，素数检验算法至少以概率1/2输出正输出正确结果确结果.证明证明 由于最大公因数和雅各比符号都是多项式时由于最大公因数和雅各比符号都是多项式时间可计算的，而利用反复平方法，求幂也是多项间可计算的，而利用反复平方法，求幂也是多项式时间可计算的，显然素数检验算法在多项式时式时间可计算的，显然素数检验算法在多项式时间内运行间内运行.定理定理9.2证明证明(续续)如前所述，由初等数论中的结论可知，对
17、于如前所述，由初等数论中的结论可知，对于每个每个奇奇素数素数 n 和所有和所有1 a n 1，都有，都有QRn(a)=a(n 1)/2(mod n)；当当n是素数时，算法总是正确检验出是素数时，算法总是正确检验出“n是素数是素数”；对每个对每个合数合数n 和所有满足和所有满足 gcd(n,a)=1的的a,1 a n 1,至多有一半至多有一半的的a满足满足 算法至少以算法至少以1/2概率检验出概率检验出“N是合数是合数”.说明：这是个说明：这是个coRP算法算法)(mod2/)1(nanan 算法算法9.3 多项式恒等检验算法多项式恒等检验算法输入输入：用规模为：用规模为m的代数电路的代数电路C
18、(x1,xn)表示的多项表示的多项 式式r(x1,xn)输出输出：r(x1,xn)是否恒等于是否恒等于01.从从1,10 2m中随机选择中随机选择n个自然数个自然数a1,an(可可重复重复)；2.从从1,22m中随机选择自然数中随机选择自然数k；3.在模在模k算术下，计算算术下，计算 y=C(a1,an)(mod k)=r(a1,an)(mod k)；4.若若y=0，则输出，则输出“r(x1,xn)恒等于恒等于0”；5.否则，输出否则，输出“r(x1,xn)不恒等于不恒等于0”.定理定理9.3定理定理9.3 算法算法9.3在多项式时间内运行在多项式时间内运行.当当r(x1,xn)恒等于恒等于0
19、时，算法输出正确结果；当时，算法输出正确结果；当r(x1,xn)不恒不恒等于等于0时，算法至少以时，算法至少以9/(40m)概率输出正确结果概率输出正确结果.证明证明 每个每个ai的长度为的长度为O(m)位，位，a1,an的总长度为的总长度为O(n m)位，位，k的长度为的长度为O(m)位，所有运算的中间结位，所有运算的中间结果的长度也都为果的长度也都为O(m)位位.同余算术中加法、减法、同余算术中加法、减法、乘法都是多项式时间的，所以上述算法在多项式时乘法都是多项式时间的，所以上述算法在多项式时间内运行间内运行.定理定理9.3证明证明(续续)当当 r(x1,xn)恒等于恒等于0时，无论什么值
20、代入后都等时，无论什么值代入后都等于零，所以算法总是输出正确结果于零，所以算法总是输出正确结果.当当 r(x1,xn)不恒等于不恒等于0时，时，Pr r(a1,an)0 9/10.若电路若电路C的规模为的规模为m，当这，当这m个门都是乘法个门都是乘法时时，则则 r的次数的次数 deg(r)最多可到最多可到2m，根据，根据施华兹施华兹-齐普尔齐普尔引理引理，设，设ai都从都从S=1,2m 中随机取值中随机取值,Pr r(a1,an)=0 deg(r)/|S|2m/(10 2m)=1/10.定理定理9.3证明证明(续完续完)当当 y=r(a1,an)0时，时，Pr y 0(mod k)1/(4m)
21、.由由素数定理素数定理，1,22m 中素数至少有中素数至少有22m/(2m)个个.y的素数因子至多有的素数因子至多有log y 5m2m=o(22m/(2m)个个.当当m 11时，时，22m/(2m)5m2m 1/(4m)1,22m 中的素数至少有中的素数至少有22m/(4m)个都不是个都不是y的素的素因因 子，当子，当k取这些值时，取这些值时，y 0(mod k).所以所以 Pr y 0(mod k)(22m/(4m)/22m=1/(4m).算法至少以算法至少以(9/10)(1/4m)=9/(40m)的概率正确输出的概率正确输出r不不 恒恒等于零等于零.独立重复执行独立重复执行O(m)次，把
22、出错概率降到次，把出错概率降到1/3以下以下.离散随机过程离散随机过程 一个一个离散随机过程离散随机过程就是一组随机变量就是一组随机变量X=Xt|t T,T是可数集是可数集 通常通常 t 代表时间，代表时间，Xt 就是就是 X 在时刻在时刻 t 的状态。的状态。例如，赌徒每次抛一枚均匀硬币来赌博例如，赌徒每次抛一枚均匀硬币来赌博 若若正面向上正面向上，赢赢1元钱元钱；反面向上反面向上，就，就输输1元钱元钱 假设初始赌本为假设初始赌本为X0，在时刻，在时刻 t 的赌本为的赌本为Xt，则则 Xt|t=0,1,2,就是一个离散随机过程。就是一个离散随机过程。有限马氏链有限马氏链 一个一个有限马氏链有
23、限马氏链是满足下列条件的离散随机过程是满足下列条件的离散随机过程 X0,X1,X2,，其中每个，其中每个Xt都从一个有限集中取值都从一个有限集中取值 PrXt=a|Xt-1=b,Xt-2=at-2,X0=a0 =PrXt=a|Xt-1=b=pb,a 即即Xt的值依赖于的值依赖于Xt-1的值，而不依赖之前的历史的值，而不依赖之前的历史.在上述赌徒的例子中，在上述赌徒的例子中，当当b 0或或n时，时，PrXt=b+1|Xt-1=b,Xt-2=a t-2,X0=a0 =PrXt=b+1|Xt-1=b=1/2 PrXt=b1|Xt-1=b,Xt-2=a t-2,X0=a0 =PrXt=b1|Xt-1=
24、b=1/2 即即 pb,b+1 =pb,b-1 =1/2一步转移矩阵一步转移矩阵 对于有限马氏链，不妨设对于有限马氏链，不妨设Xt取值的状态空间为取值的状态空间为0,1,2,n.于是于是pi,j可组成一个可组成一个n+1阶方阵阶方阵P=pi,j(n+1)(n+1)，叫做叫做一步转移矩阵一步转移矩阵.其每一行元素之和等于其每一行元素之和等于1，即对，即对任意任意 i，有，有 j pi,j=1.m步转移矩阵步转移矩阵 设设pi(t)表示在时刻表示在时刻 t 处在状态处在状态 i 的概率，则的概率，则 pi(t)=p0(t 1)p0,i+p1(t 1)p1,i+pn-1(t 1)pn-1,i+pn(
25、t 1)pn,i 设设p(t)表示向量表示向量(p0(t),p1(t),pn-1(t),pn(t)，则，则 p(t)=p(t 1)P.对任意对任意m，定义，定义m步转移矩阵步转移矩阵 其中其中 于是于是 P(m)=Pm p(t+m)=p(t)Pm）1()1()(,)(nnmjimpPPr)(iX|jXptmtmi,j 有限马氏链有限马氏链的的图示图示 有限马氏链还可以用有限马氏链还可以用有向带权图有向带权图来表示来表示 每个状态作为一个顶点每个状态作为一个顶点 两个状态两个状态 i,j之间的有向边所带的权就是这两个之间的有向边所带的权就是这两个状态之间的转移概率状态之间的转移概率 pi,j 如
26、图所示就是一个三状态马氏链如图所示就是一个三状态马氏链.算法算法9.4 2SAT的的随机游动算法随机游动算法输入输入：一个有：一个有n个变元和个变元和m个子句的合取范式，每个个子句的合取范式，每个 子句至多有两个文字子句至多有两个文字输出输出：一个满足赋值，或宣布没有满足赋值：一个满足赋值，或宣布没有满足赋值1.任意给所有变量赋值；任意给所有变量赋值；2.若若当前赋值是满足赋值，则输出这个赋值，算当前赋值是满足赋值，则输出这个赋值，算法结束；法结束；3.均匀随机选一个不满足子句，从中均匀随机选均匀随机选一个不满足子句，从中均匀随机选一个文字，改变该文字的赋值；一个文字，改变该文字的赋值；4.重
27、复第重复第2-3步步2mn2次，若一直没有找到满足赋次，若一直没有找到满足赋值，则宣布没有满足赋值值，则宣布没有满足赋值.定理定理9.4 定理定理9.4 若输入公式是不可满足的，则上述随机游若输入公式是不可满足的，则上述随机游动算法正确宣布其不可满足动算法正确宣布其不可满足.若输入公式是若输入公式是可可满足满足的，则上述算法以的，则上述算法以1-1/2m概率找到满足赋值概率找到满足赋值.证明证明 显然，当输入公式是不可满足的，算法无显然，当输入公式是不可满足的，算法无法找到满足赋值，因此将宣布不可满足法找到满足赋值，因此将宣布不可满足.当输入当输入公式可满足时，算法有可能找不到满足赋值而出公式
28、可满足时，算法有可能找不到满足赋值而出错错.我们证明算法出错的概率为我们证明算法出错的概率为1/2m.定理定理9.4证明证明(续续)假设输入公式可满足，假设输入公式可满足，设设a*是某个可满足赋值，是某个可满足赋值，设设at是算法在执行是算法在执行 t 遍第遍第3步以后的赋值，步以后的赋值，设设 Xt 等于等于a*和和 at 赋值相同的变量个数赋值相同的变量个数.令变量数为令变量数为n，则当则当 Xt=n 时时at=a*，算法将找到满足赋值，算法将找到满足赋值a*而而停止停止.注意在注意在 Xt=n之前，算法也可能找到别的满足赋之前，算法也可能找到别的满足赋值而停止值而停止.定理定理9.4证明证明(续一续一)考虑考虑 Xt 和和 Xt+1的关系的关系当当 Xt=0时，时，显然有显然有Xt+1=1，所以所以 PrXt+1=1|Xt=0=1.当当Xt=j且且02n2 1/2即若以即若以2n2步为一个阶段，则在一个阶段中算法找不步为一个阶段，则在一个阶段中算法找不到满足赋值的出错概率不超过到满足赋值的出错概率不超过1/2.当重复执行每个阶当重复执行每个阶段段m次，即总共执行次，即总共执行2mn2步时，算法仍然找不到步时，算法仍然找不到满满足赋值的出错概率小于足赋值的出错概率小于1/2m.
