设为首页|收藏本站|
发帖
登录 注册
西兔生活网 › 美洲华人圈 › 美国华人圈 › 随机算法：蒙特卡洛和拉斯维加斯算法
回复 发帖
返回列表 发新帖
开启左侧

[问答] 随机算法：蒙特卡洛和拉斯维加斯算法

[复制链接]
81379 0
琳琳女孩仓r5 发表于 2022-12-1 17:28:28 | 只看该作者 打印 上一主题 下一主题
 
1 随机算法

随机性在计算机科学中的最初应用之一就是随机算法。随机算法是能够获得随机性来源（比如随机数生成器）的算法，它允许在很小的概率内出错。目前已经有许多问题我们知道怎样用随机算法高效地求解，而并不知道怎样用确定性算法（即不使用随机性的算法）高效求解。事实上，计算机科学中最重要的open problems之一就是询问每个高效的随机算法是否都有其对应求解相同问题的确定性算法。
下面是个简单的随机算法例子：
import numpy as np
def f(x):
    y = np.random.binomial(1, 0.5)
    if y == 0:
        while x > 0:
            print("What up?")
            x -= 1
    return x + y对于一个确定的输入（比如x=3），其输出可能会有差异，且其运行时间也可能有差异。那么对于一个随机算法，我们如何度量其正确性（correctness）和运行时间（running time）呢？事实上，如果我们要求它输出结果总是正确的，且运行时间总是O(T(n))，则它就是时间复杂度为T(n)的确定性算法了。
因此，对于随机算法它要么不是在所有情况下总是正确的，要么就不能保证运行时间总为O(T(n))，它可以看做是在正确性和运行时间之间做赌博(gamble)。
2  蒙特卡洛算法和拉斯维加斯算法

我们来看下面这个例子，给点n个元素（n为偶数）的序列A，一半为0一半为1，我们想在想要找到一个含1的序列下标。那么我们可以写出下面两个不同的算法：

随机算法：蒙特卡洛和拉斯维加斯算法 第1张图片
我们将左边这种赌博时间但不赌博正确性的算法称为拉斯维加斯（Las Vegas）算法，右边这种赌博正确性但不赌博时间的算法为蒙特卡洛（Monte Carlo）算法。
如图所示的拉斯维加斯算法的失败概率\text{Pr}(\text{fAIlure})=0，最坏运行时间无界，期望运行时间为O(1)(2次迭代)；而如图所示的蒙特卡洛算法失败概率\text{Pr}(\text{failure})=\frac{1}{2^{300}}，最坏运行时间为O(1)。
总结一下，在我们上面这个问题中两个算法的区别如下表所示：
正确性运行时间
确定性总是正确Ω(n)
蒙特卡洛大概率正确O(1)
拉斯维加斯总是正确大概率O(1)
下面给出蒙特卡洛算法和拉斯维加斯算法的形式化定义。
蒙特卡洛算法 设f: \Sigma^* \rightarrow \Sigma^*为一个可计算问题，0 \leqslant \epsilon<1为参数，T: \mathbb{N} \rightarrow \mathbb{N}为一个函数。若A为一个随机算法，它使得

  • 对任意x\in\Sigma^*，\operatorname{Pr}\left(A(x) \neq f(x)\right) \leqslant \epsilon；
  • 对任意x\in\Sigma^*，\operatorname{Pr}\left(\text { number of steps } A(x) \text { takes is at most } T(|x|) \right)=1。
（注意此处的概率基于A做出的随机选择）
则我们声称A是一个能够以T(n)时间、\epsilon的错误概率计算问题f的蒙特卡洛算法。
拉斯维加斯算法 设f: \Sigma^* \rightarrow \Sigma^*为一个可计算问题，T: \mathbb{N} \rightarrow \mathbb{N}为一个函数。若A为一个随机算法，它使得

  • 对任意x\in\Sigma^*，\operatorname{Pr}\left(A(x) = f(x)\right)=1（这里概率基于A做出的随机选择）；
  • 对任意x\in\Sigma^*，\textbf{E}\left(\text { number of steps } A(x) \text { takes }\right) \leqslant T(|x|)。
则我们声称A是一个能够以T(n)时间计算问题f的拉斯维加斯算法。
3  蒙特卡洛算法实例：最小割（Min Cut）随机化算法

图割集是一个边的集合，当去掉这些边时将G分为两个或多个连通部分。给定一个有n个顶点的图G=(V, E)，最小割问题就是在图G中寻找一个基数最小的割集，也即找到非空子集 S\subset V 使得从 S 到 V-S 的边数最小化。

随机算法：蒙特卡洛和拉斯维加斯算法 第2张图片
接下来我们会介绍一个求解最小割算法的简单随机算法，该算法中重要的操作为边的缩减。
该算法包括n-2次迭代（n为顶点数目）。在每次迭代中，算法从图的现有边中均匀随机地选出一条边并将它缩减掉。在缩减边(u, v)时，将两个顶点u和v合并成一个顶点，删除所有连接u和v的边，保留图中所有其他的边。新图可能有重边，但没有自环。
每一次迭代都会使图中的顶点数目减少一个，经过n-2次迭代后，图中只剩下两个顶点。算法输出连接这两个保留顶点的边的集合。
下面我们来看在最小割集大小为2的图中，两种最小割算法执行的例子。首先是成功运行的实例：

随机算法：蒙特卡洛和拉斯维加斯算法 第3张图片
然后是不成功运行的实例：

随机算法：蒙特卡洛和拉斯维加斯算法 第4张图片
现在我们来建立算法输出正确结果的概率的下界。
定理 算法至少以2/(n(n-1))的概率输出最小割集。
证明 我们设集合C为图的最小割集，除去集合C后将顶点集合分为两个集合S和V-S，使得不存在连接S中的顶点到V-S中的边。我们在算法中缩减的边是S中的顶点或V-S中顶点的边，经n-2次迭代后，算法输出的是由C中边连接的两个顶点的图。所有，我们可以得到结论：如果算法在n-2次迭代中根本不选择C中的边，那么算法输出的C就是最小割集。
设E_i表示第i次迭代时缩减的边不在C中这一事件，F_i =\bigcap_{j=1}^i E_j表示在前i次迭代中没有缩减C中边的事件。我们需要计算的算法在n-2次迭代中不选择C中的边的概率，即为\text{Pr}(F_{n-2})。
我们从计算\text{Pr}(E_1)=\text{Pr}(F_1)开始。因为最小割集有k条边，所以图中每个顶点至少连接k条边（即度至少为k），则根据握手定理图中至少有nk/2条边。第一次缩减的边是从所有边中均匀随机地选取的，故第一次迭代没有选取C中边的概率为：
\text{Pr}(E_1) = \text{Pr}(F_1)\geqslant  1 - \frac{k}{(nk)/2} = 1 - \frac{2}{n}\\
接下来，假设第一次缩减没有消去C中的边，即给定了事件F_1成立这一条件，那么我们在接下来的有n-1个顶点的新图中也没有选取到C中边的概率为：
\text{Pr}(E_2|F_1) \geqslant 1 - \frac{k}{k(n-1)/2} = 1 - \frac{2}{n-1}\\
类似地，我们有：
\text{Pr}(E_i|F_{i-1}) \geqslant 1 - \frac{k}{k(n-i+1)/2} = 1 - \frac{2}{n - i + 1}\\
则
\begin{aligned} \text{Pr}(F_{n-2}) &= \text{Pr}(F_1)\text{Pr}(E_2|F_1)\cdots\text{Pr}(E_{n-2} | F_{n-3}) \\&= \prod_{i=1}^{n-2}(1 - \frac{2}{n-i+1}) = \prod_{i=1}^{n-2}(\frac{n-i-1}{n-i+1})\\&= \left(\frac{n-2}{n}\right) \left( \frac{n-3}{n-1}\right) \left( \frac{n-4}{n-2}\right)\cdots \left(\frac{3}{5}\right) \left(\frac{2}{4}\right) \left(\frac{1}{3}\right)\\&= \frac{2}{n(n-1)}\end{aligned}\\
得证。
因为算法具有单边错误的性质，我们可以重复运行算法来减小出错率。假设运行最小割随机化算法n(n-1)\ln n次，并输出再所有迭代次中找到的最小长度割集。则输出不是一个最小割集的概率界为
\text{Pr}(\text{error}) = {\left(1 - \frac{2}{n(n-1)}\right)}^{n(n-1)\ln n}\leqslant e^{ -2\ln n} = \frac{1}{n^2}\\
在第一个不等式中，我们用到了经典不等式：\forall x\in \mathbb{R}: 1 + x \leqslant e^x。

随机算法：蒙特卡洛和拉斯维加斯算法 第5张图片
4  拉斯维加斯算法实例：随机快速排序算法

快速排序是一种简单且实际上非常有效的排序算法。给定输入列表S=\{ x_1, x_2,\cdots x_n\}，随机快速排序算法可描述如下：

  • 如果n\leqslant 1，返回S；
  • 均匀随机地选择基准（pivot）x_m；
  • 将S中每个其它元素与x_m做比较，以将S划分为两个子列表：S_1=\{x_i: x<x_m\}, S_2=\{x_i: x_i>x_m\}。
  • 递归地对S_1和S_2排序。
对于随机快速排序算法，我们有以下定理：
定理 假设在随机快速排序算法中，每一次都是从所有可能中独立且随机地选取基准，那么对于任意的输入，随机快速排序算法所做比较的期望次数为2n\ln n + \Theta(n)（这里的期望是关于基准的随机选取）。
证明 设y_1, y_2, \cdots, y_n与输入值x_1,x_2, \cdots, x_n有相同的值，但是按照升序排列。对i<j，记X_{ij}为一随机变量，如果在算法执行过程的任何时候y_i和y_j进行了比较，则X_{ij}的值为1，否则取0。那么比较的总次数满足
X = \sum_{i=1}^{n-1}\sum_{j=i+1}^n X_{ij}\\
且根据期望的线性性得
\mathbf{E}(X) = \mathbf{E}(\sum_{i=1}^{n-1}\sum_{j=i+1}^n X_{ij})=\sum_{i=1}^{n-1}\sum_{j=i+1}^n \mathbf{E}(X_{ij})\\
由于X_{ij}只是取0和1的示性随机变量，\mathbf{E}(X_{ij})等于X_{ij}为1的概率。因此，我们接下来只需计算两个元素y_i和y_j相比较的概率即可。
现在，y_i和y_j相比较，当且仅当y_i或y_j是从集合Y^{ij}=\{y_i,y_{i+1},\cdots, y_{j-1}, y_{j}\}中由随机快速排序算法选取的第一个基准。这是因为如果y_i（或y_j）是从这个集合选取的第一个基准，y_i和y_j必仍在同一个子列表中，因此它们将会进行比较。反之，如果两者都不是从这个集合中选取的第一个基准，那么y_i和y_j将会被分在不同的子列表中，所以不会进行比较。
因为我们的基准都是从每个子列表中独立且随机地选取的，也就是第一次从Y^{ij}中选取的一个基准等可能地是这个集合中的任一元素。因此y_i或y_j是从Y^{ij}中选取的第一个基准的概率（即X_{ij}取1的概率）是\frac{2}{j-i+1}。利用替换k=j-i+1，得
\begin{aligned} \mathbf{E}(X) &=\sum_{i=1}^{n-1}\sum_{j=i+1}^n \frac{2}{j-i+1}=  \sum_{i=1}^{n-1}\sum_{k=2}^{n-i+1}\frac{2}{k} = \sum_{k=2}^{n}\sum_{i=1}^{n+1-k} \frac{2}{k} \\  &= \sum_{k=2}^n(n+1-k)\frac{2}{k} = \left( (n+1) \sum_{k=2}^n \frac{2}{k}\right) - 2(n-1) = (2n+2)\sum_{k=1}^n\frac{1}{k} - 4n\end{aligned}\\
注意第3个等式交换了双重求和的次序，这样就可以将内层求和直接用乘法表达出来，从而得到了期望的简洁形式。交换求和顺序的示意图如下所示：

随机算法：蒙特卡洛和拉斯维加斯算法 第6张图片
又因为调和级数H(n) = \sum_{k=1}^n\frac{1}{k}满足H(n) = \ln n+ \Theta(1)，因此，\mathbf{E}(X) = 2n \ln (x) + \Theta(n)，得证。
参考


  • [1] CMU 15-251:  Great Ideas in Theoretical Computer Science: Lecture 19: Randomized Algorithms
  • [2] Mitzenmacher M, Upfal E. Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis(M). Cambridge university press, 2017.
本文使用 Zhihu On VSCode 创作并发布



上一篇：2022 年卡塔尔世界杯小组赛伊朗 vs 美国，本场比赛有哪些 ...
下一篇：欧洲移民VS北美移民，要注意哪些问题？看完再来做决定！
标签：随机数生成器拉斯维加斯计算机科学确定性算法蒙特卡洛
@
免
责
声
明
1.西兔生活网 CTLIVES 内容全部来自网络;
2.版权归原网站或原作者所有;
3.内容与本站立场无关;
4.若涉及侵权或有疑义，请点击“举报”按钮，其他联系方式或无法及时处理。
举报

关联主题
回复

使用道具 举报

 
返回列表
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

琳琳女孩仓r5白金会员

0关注

6粉丝

422帖子

热门图文
热门帖子
排行榜
  • 日
  • 周
  • 月
活跃网友
返回顶部快速回复上一主题下一主题返回列表APP下载手机访问
Copyright © 2016-2028 CTLIVES.COM All Rights Reserved.  西兔生活网  小黑屋| GMT+8, 2024-4-29 06:00