下界定理 2 蒙特卡罗算法和拉斯维加斯算法

1 随机算法

随机性在计算机科学中的最早应用之一是随机算法。 随机算法是一种可以访问随机源（例如随机数生成器）的算法，该随机源允许以小概率发生错误。 已经有很多问题我们知道如何用随机算法高效解决，但我们不知道如何用确定性算法（即不使用随机性的算法）高效解决。 事实上，计算机科学中最重要的开放问题之一是询问是否每个有效的随机算法都有解决相同问题的相应确定性算法。

这是一个简单的随机算法示例：

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），它的输出可能不同，运行时间也可能不同。 那么对于一个随机算法，我们如何衡量它的正确性（）和运行时间（时间）呢？ 事实上，如果我们要求它的输出结果始终正确且运行时间始终为O(T(n))，那么它就是一个时间复杂度为T(n)的确定性算法。

因此，对于随机算法来说，它要么并不总是在所有情况下都正确，要么不能保证运行时间始终为 O(T(n))。 可以看作是正确性和运行时间之间的 *** ()。

2 蒙特卡罗算法和拉斯维加斯算法

让我们看下面的例子。 给定一个有n个元素（n为偶数）的序列A，其中一半是0，一半是1，我们想要找到一个包含1的序列索引。那么我们可以编写以下两种不同的算法：

我们把左边赌时间但不赌正确性的算法称为拉斯维加斯算法，把右边赌正确性但不赌时间的算法称为蒙特卡罗算法。

如图所示，Las Vegas算法的失败概率\text{Pr}(\text{})=0，最坏运行时间无界，期望运行时间为O(1)（2次迭代）； 而如果蒙特卡洛算法的失败概率如图 \text{Pr}(\text{})=\frac{1}{2^{300}} 所示，最差运行时间为 O(1)。

总结一下，我们上面的问题中两种算法的区别如下表所示：

正确性运行时间

肯定

总是正确的

Ω(n)

蒙特卡洛

最有可能是正确的

复杂度(1)

拉斯维加斯

总是正确的

高概率 O(1)

下面给出蒙特卡洛算法和拉斯维加斯算法的正式定义。

蒙特卡洛算法假设 f: \Sigma^* \Sigma^* 为可计算问题，0 \ \ 为参数，T: \{N} \ \{N} 为函数。如果 A 是随机算法，则使

（注意下界定理，这里的概率是基于 A 的随机选择）

然后我们声称 A 是一个蒙特卡洛算法，可以在 T(n) 时间内以 \error 概率计算问题 f。

拉斯维加斯算法 设 f: \Sigma^* \ \Sigma^* 是一个可计算问题，T: \{N} \ \{N} 是一个函数。如果 A 是随机算法，则使得

然后我们声称 A 是一个拉斯维加斯算法，可以在 T(n) 时间内计算问题 f。

3 蒙特卡洛算法示例：Min Cut随机化算法

图割集是一组边，当删除该边时，将 G 分为两个或多个连接的部分。 给定一个有n个顶点的图G=(V,E)，最小割问题就是找到图G中基数最小的割集，即找到非空子集S\V使得数从 S 到 VS 的边数最小化。

接下来，我们将介绍一种简单的随机算法来求​​解最小割算法。 该算法中的重要操作是边缘缩减。

该算法包括n-2次迭代（n是顶点数）。 在每次迭代中，算法从图的现有边中均匀随机选择一条边并减少它。 减少边(u,v)时，将两个顶点u和v合并为一个顶点，删除连接u和v的所有边，保留图中的所有其他边。 新图可能有多个边，但没有自环。

每次迭代都会将图中的顶点数减少 1。 经过 n-2 次迭代后，图中将只剩下两个顶点。 该算法输出连接这两个保留顶点的边集。

下面我们看一下在最小割集大小为 2 的图中执行两种最小割算法的示例。首先是一个成功运行的示例：

然后还有运行不成功的情况：

现在让我们为算法输出正确结果的概率建立一个下限。

该定理算法以至少 2/(n(n-1)) 概率输出最小割集。

证明我们将 *** C设置为图的最小割集。 去除 *** C后，顶点 *** 被分为两个 *** S和VS，使得S中的顶点到VS中不存在连接的边。 如果算法每次迭代都不选择C中的边，则每次减少的边都是V或VS的边，而不是连接S和VS的边。 这样，经过n-2次迭代后，只剩下C中连接两个顶点的边组成的图。 因此，我们可以得出结论，如果算法在n-2次迭代中根本没有选择C中的任何边，那么算法输出的C就是最小割集。

设E_i表示第i次迭代中C中没有减少的边的事件，F_i =\{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​​)\ 1 - \frac{k}{(nk)/2} = 1 - \frac{2}{n}\\

接下来，假设之一次约简没有消除C中的边，即给定事件F_1成立的条件，那么我们将不会在下一个具有n-1个顶点的新图中选择C中的任何边。 概率为：

\text{Pr}(E_2|F_1) \ 1 - \frac{k}{k(n-1)/2} = 1 - \frac{2}{n-1}\\

同样，我们有：

\text{Pr}(E_i|F_{i-1}) \ 1 - \frac{k}{k(n-i+1)/2} = 1 - \frac{2}{n - i + 1} \\

但

\begin{} \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{ni-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{}\\

获得认证。

由于该算法存在单方面错误，我们可以反复运行该算法来降低错误率。 假设运行最小割随机算法 n(n-1)\ln n 次并输出在所有迭代中找到的最小长度割集。那么输出不是最小割集的概率界限为

\text{Pr}(\text{错误}) = {\left(1 - \frac{2}{n(n-1)}\right)}^{n(n-1)\ln n}\ e ^{ -2\ln n} = \frac{1}{n^2}\\

在之一个不等式中，我们使用经典不等式：\x\in \{R}: 1 + x \ e^x。

4 拉斯维加斯算法示例：随机快速排序算法

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

对于随机快速排序算法，我们有以下定理：

该定理假设在随机快速排序算法中，每次从所有可能性中独立、随机地选择基准，那么对于任意输入，随机快速排序算法期望的比较次数为 2n\ln n + \Theta( n ）（此处的期望是相对于基准的随机选择）。

证明 y_1, y_2, \cdots, y_n 与输入值 x_1, x_2, \cdots, x_n 具有相同的值，但按升序排列。 对于 i，令 X_{ij} 为随机变量。 如果在算法执行过程中的任何时刻对y_i和y_j进行比较，则X_{ij}的值为1，否则为0。则比较总数满足

X = \sum_{i=1}^{n-1}\sum_{j=i+1}^n X_{ij}\\

根据预期的线性，我们得到

\{E}(X) = \{E}(\sum_{i=1}^{n-1}\sum_{j=i+1}^n X_{ij})=\sum_{i=1} ^{n-1}\sum_{j=i+1}^n \{E}(X_{ij})\\

由于 X_{ij} 只是取 0 和 1 的代表性随机变量，\{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{} \{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{}\\

请注意，第三个方程交换了双重求和的顺序，以便内部求和可以直接表示为乘法，从而获得所需的简洁形式。 交换求和顺序的示意图如下所示：

又因为调和级数 H(n) = \sum_{k=1}^n\frac{1}{k} 满足 H(n) = \ln n+ \Theta(1)，因此， \{E}(X ) = 2n \ln (x) + \Theta(n)，已证明。

参考这篇文章使用知乎进行创作和发布