计算机问题求解—论题4.9 随机算法的概念 陶先平 2017年5月15日

问题1: 卷首语是什么含义？它和随机算法有什么关联？ 对追求真理的人来说，犯错是家常便饭。 当犯错是小概率事件时，随机算法既快又准！数据库一致性验证；素数测试等； 当事务本身就是随机时，需要随机算法：随便找一个元素即可（为了防攻击，必须力争随机） 蒙特卡洛类算法可能给出不够正确、精确的解，拉斯维加斯类算法可能在有限时间内给不出解。 我们还能够用这些算法吗？ 看概率！

确定性图灵机 可以看出，转换函数决定了这么一个图灵机在每个格局(读写头位置，当前带字母，当前状态）下，其转换新状态是唯一的，计算是唯一的

非确定图灵机 唯一的区别：

问题2：什么是随机算法 问题3：这两句话是一致的吗？ In other words, a randomized algorithm may be seen as a set of deterministic algorithms, from which one algorithm is randomly chosen for the given input.

问题4：你能根据这个描述写出随机算法的图灵机模型吗？

什么意思？ 随机算法的概率空间 𝑆 𝐴,𝑥 ,𝑃𝑟𝑜𝑏 : 𝑆 𝐴,𝑥 = 𝐶 𝐶 𝑖𝑠 𝑎 𝑐𝑜𝑚𝑝𝑢𝑡𝑎𝑡𝑖𝑜𝑛 𝑜𝑓 𝐴 𝑜𝑛 𝑥 ; 𝑃𝑟𝑜𝑏 𝑖𝑠 𝑎 𝑑𝑖𝑠𝑡𝑟𝑖𝑏𝑢𝑡𝑖𝑜𝑛 𝑜𝑣𝑒𝑟 𝑆 𝐴,𝑥 , 𝑃𝑟𝑜𝑏 𝐴,𝑥 𝐶 :𝑖𝑡 𝑖𝑠 1 2 𝑡𝑜 𝑡ℎ𝑒 𝑝𝑜𝑤𝑒𝑟 𝑜𝑓 𝑡ℎ𝑒 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑟𝑎𝑛𝑑𝑜𝑚 𝑏𝑖𝑡𝑠 𝑎𝑠𝑘𝑒𝑑 𝑖𝑛 𝐶. Prob(A(x) = y), is the sum of all ProbA,x(C), where C outputs y. 什么意思？

随机算法设计目标 算法的输出是随机的 So,

随机算法的期望时间复杂度和确定 算法的平均复杂度有什么不同？ 问题5： 随机算法的期望时间复杂度和确定 算法的平均复杂度有什么不同？ 确定性算法的平均复杂度是输入数据的概率分布下的运行时间期望：平均复杂度相关的随机变量是对输入参数而言 随机算法：输入数据具有随机性，给定一个输入后，运行时间也具有随机性；时间复杂度相关的随机变量是针对给定输入x后的运行时间而言。此时，我们不再也不能称为平均复杂度。

Random(x): 针对一个输入实例x，随机算法A的每次运行都需要一个随机二进制位串。我们考察这个位串的长度。在所有可能的运行中使用的位串中，最长的位串长度记为random(x). 所有输入规模为n的实例中，random(x)最大的，记为random(n). 1)random(n)越大，产生这个序列的代价越高，我们需要评估一个随机算法的random(n)的代价； 2)我们如果想用确定算法来模拟随机算法，random(x)不能大。而用确定性算法来模拟随机算法是常见的。Random(x)如果是对数函数，模拟才能是多项式时间的 以上记号，均针对随机算法A，故省略random下标A 为什么要考察random(n):1)产生一个“随机位串”并非那么容易。特别地，我们还无法给出一个真的随机位串。2）考察random(x)的形态（界），可以明确这个随机算法是否可以去随机化。 1）如果给定一个x，其random(x)被一个对数函数（clog2n）界定(bound),那么，随机算法A针对一个规模为n的输入，考察其不同的运行的数量，这个数量是被一个多项式函数所界定。为什么是2random(n)呢？每次随机选择是2种（随机位串为2进制），产生出来的运行，构成的空间就是2的random(n)次方。 2）如果我们能够确定random(x)是界定于一个指数函数，我们可以将这种随机去随机化，也就是用确定性算法遍历所有可能的运行。但是，如果我们发现并非如此（random(x)本身就已经规模很大，比如线性甚至是多项式），则无法去随机化。

算法的运行时间也是随机的 Time(C)到底是什么意思？ 随机变量Time：是对一个运行C的观察，观察其运行时间复杂度：Time(C) Exp-TimeA{x) is the expectation E[Time] of the random variable Time in the experiment of the work of A on x.

以下两套评价体系均可用于评估随机算法时间复杂度 前者精确，较难 后者较易， 在ＬＡＳ算法第一定义（一定给出正确答案）中用前者评估复杂度；第二定义（不知道就保持沉默然后重试）中用后者评估复杂度

问题7：在随机算法分析中，为什么我们需要“output？”？ 这两个地方用词的单、复数使用，给你什么启发？ 随机算法可能不会终止，原因在于computation的数量可能无穷，而且可能某个computation也是无穷的，但是这里的无穷不等同于无限循环； 为了应对这种情况下的随机算法终止问题，我们在给定时间TimeA的情况下，规定：在TimeA时间内没有终止，输出为？，在同样输入x下，重启算法A。希望A的这个computation能够在TimeA内终止。 其实这里也正是随机算法的“使用手册”

LAS VEGAS算法第一种定义:永远正确 不以worst case为代表来讨论时间开销

Las Vegas算法第二种定义：永不犯错 多数情况下正确，且：可以保持沉默但永不犯错 拉斯维加斯算法找到正确解的概率随着它所用的计算时间的增加而提高。 对于所求解问题的任一实例，用同一拉斯维加斯算法反复对该实例求解足够多次，可使求解失败的概率任意小。

随便问个问题：一般情况下，第一种LAS VEGAS算法的定义适合于计算一个函数，而第二种定义方法适合于判定问题。为什么？ Best known Las Vegas algorithm： 函数计算：相对而言计算复杂度“不大”，我们需要随机特性进行优化或者避免什么 判定问题：相对而言计算复杂度“很大”，我们需要随机特性进行降阶 随便问个问题：一般情况下，第一种LAS VEGAS算法的定义适合于计算一个函数，而第二种定义方法适合于判定问题。为什么？

Random select：比较数期望值的上限 E[Ts,k]: 在给定集合S和序号k时，随机算法A进行比 较的次数的期望值 记号Tn,k: |S|=n; 在忽略S的具体意义之后，用于表示 Ts,k Tn: max{Tn,k |1<=k<=n} 期望运行时间是多少？转成给定S和k时，A进行比较的次数的期望值 期望值的上限可以代表这个算法的性能 期望值的上限：E[Tn]的上限

E[Tn]的上限： 算法的第一、二、三步的比较次数 如果第k个数落在S<中，递归中比较次数

E[Tn]的上限： 算法第一步的ai选择为第j个小的数的概率是1/n 注意Tn和Tn,k的区别：Let Tn = max{Tn,k| 1 < k < n)}. 注意最后一个<=的含义：将Tmax放大到极限

上限：

会犯错的算法，会是什么样子的呢？ Las Vegas算法会犯错吗？ 素数判定算法 有错误的算法，我们也能用？ 永远正确 决不犯错 多次随机后，正确的概率可极高 素数判定算法 2的n-1次幂模n如果等于1：算法认定n是素数 有错误的算法，我们也能用？

问题9：为什么说单边Monte Carlo算法非常实用? 问题8：何谓one side error? 对判定问题而言，如果一个文字w能够被判定（具有某个性质，属于L这个语言），就应该能够无条件被算法接受。单边错算法接受w的概率超过一半；有错！ 如果一个文字不属于语言L（不具有某个性质），单边错算法一定能够拒绝这个文字，不犯错 问题9：为什么说单边Monte Carlo算法非常实用?

两个数据库一致性判断方法：

单边错误证明： 首先，有一边不会犯错： 其次，另一边犯错的概率小于1/2： 坏素数一定是x和y的差值的因子！ 差值可以写成若干素数的乘积（素数可重复出现）。假设不同的素因子数量为k，差值大于等于这k个素数的简单连乘，大于k!。同时，差值一定比2的n次幂小，因此，k!<=2的n次幂。 因此，k必须小于n

双边错Monte Carla算法 多做几次，比如t次，看结果重复率：如果有一半以上的结果是相同的，认定这个结果就是问题的解。如果没有出现一半以上结果重复，继续做下去

重复出现的事情往往反映了真理的存在 直观上：不断重复执行，直到输出有意义的yi

实际上，当我们需要控制双边错算法的正确率时，我们可以预估执行次数： 某次成功的概率： 在t次运行中，恰好成功i次的概率： 此处的成功：A算法结束并得到A(x)=F(x) 第二个公式：独立t次试验成功i次的概率 第三个公司：1-这个值的0到t/2的累和，就是t次A算法运行，成功一半以上的概率 在t次运行中，恰好成功i次( )的概率：

实际上，当我们需要控制双边错算法的正确率时，我们可以预估执行次数： 当算法停止时，在t次运行中，成功的次数一定大于了t/2: 如何解读第一个公式：A算法运行t次完成任务的概率大于这个取决于t和epsilon 显然，t越大，A解出正确解的概率越高。 当我们需要控制这种“精确度”时，我们可以选定一个delta，计算出需要重复的次数k。 当我们重复执行k次A算法后，双边错Monte算法A能够保证得到足够“准” 的正确解。 意味着：当我们得到一个双边错算法后，如果我们想控制算法求解的“准确度” 必须达到1-δ时：

无界错Monte Carlo算法： 在双边错算法定义中，如果ε不存在，我们该如何看待这种情况？ 随着x的规模的增大，成功的概率和0.5之间的差距趋近于0！ 我们针对一个特定的输入，这种算法的重复执行次数（效率）将不再实际可控:

Open Topics 请讲解例题5.2.2.5，并说明，为什么这个随机算法代价好于“任 何”确定性算法。

确定性算法的通信开销是n：每次传送出去的必须是n位的01位串。针对不同的u,v，其CI计算的结果：1）互相不为前缀；2）一定不相同

作业： PAGE 352：5.2.2.7 PAGE 364：5.2.2.8