随机算法并不是把正确性交给运气。更准确地说，它是在设计一种承诺：哪些东西必须保证，哪些东西允许带概率，概率又被限制在什么范围内。

有些随机算法把不确定性放在“答案质量”上。它会在规定时间内结束，但答案可能偶尔出错。另一些随机算法则反过来：答案一旦输出就一定正确，但具体运行多久由随机过程决定。它们被挂上两个赌城的名字：蒙特卡罗（Monte Carlo）和拉斯维加斯（Las Vegas）。两者都依赖随机数，却押注在完全不同的东西上。

粗略地说：蒙特卡罗算法说：“我会按时给你答案，但它有很小概率是错的。”拉斯维加斯算法说：“我不会给你错答案，但这次具体要等多久不完全确定。”

这两个定义看似简单，真正重要的是后面的细节：错误概率对谁取？能不能重复降低？失败算不算错误？输出有没有证书？超时之后该返回什么？这些问题决定了一个随机算法能否被放心地写进程序里。

随机性与算法

讨论随机算法时，必须先把输入和随机性分开。

给定一个固定输入 \(x\)，算法内部可能会抛硬币、选随机下标、随机抽样、随机选主元、随机生成候选解。于是运行时间和输出都可能变成随机变量。分析随机算法时，概率通常是对算法内部随机选择取的，而不是假设输入本身服从某个分布。

比如说“随机快速排序的期望时间是 \(O(n \log n)\)”，意思不是“在随机输入上很快”，而是：对任意固定输入，只要主元是随机选择，运行时间的期望都是 \(O(n \log n)\)。

再比如说“Miller-Rabin 素性测试以很高概率正确”，意思也不是“大部分整数上正确”，而是：对一个任意固定待测数，算法内部随机选取测试底数时，错误概率可以被控制住。

所以随机算法不是平均情形分析。平均情形分析通常假设输入来自某个分布；随机算法分析通常固定输入，只对算法自己的随机比特取概率。这个区别很重要，因为算法面对的输入可能是人为构造的、极端的，甚至是对抗性的。

随机性的核心价值也不只是“碰运气”。它可以打破输入结构、避免确定性最坏构造、用少量随机采样替代昂贵的全量检查，或者在可控概率下换取更低的计算成本。蒙特卡罗和拉斯维加斯的区别，就在于它们把这个“可控”放在了不同位置。

蒙特卡罗算法：时间可控，答案会出错

蒙特卡罗算法通常有明确的运行预算：固定轮数、固定采样次数，或者一个容易界定的时间上界。它会在预算内给出答案，但答案可能错。

只要错误概率被界住，比如

并且这个界限对每个输入都成立，我们就说它是有界错误的随机算法。

这里的 \(\frac 13\) 没有神秘性。换成 \(\frac 14\)、\(0.1\)，甚至其他小于 \(\frac 12\) 的常数，在双边错误的判定问题中通常都可以。复杂度理论里常写成 \(\frac 13\)，只是为了统一口径，因为只要正确概率和随机猜测之间有稳定间隔，就能通过独立重复把错误率继续压低。

之所以要求错误率“小于 \(\frac 12\)”主要是为了双边错误和多数投票。而单边错误算法的放大逻辑略有不同。如果错误或失败只出现在一边，即使不满足要求，理论上重复运行也能把它压下错误率。

单边错误和双边错误

在判定问题里，输出通常是 yes 或 no。根据错误出现在哪一边，蒙特卡罗算法可以分成两类。

单边错误算法只会在一类答案上犯错。Miller-Rabin 素性测试就是经典例子。它测试一个数是否为合数。如果返回 composite，这个结论可以信任；如果返回 probably prime，意思只是多轮随机测试没有找到合数证据。也就是说，它不会把素数误判为合数，但可能把某些合数暂时误判为“可能是素数”。这类算法在工程上很有用，因为它给了程序员一个强不变量：某些输出是确定可靠的，另一些输出只是高度可信。

双边错误算法则是 yes 和 no 都可能错，只是总体错误概率被压在某个界内。复杂度类 BPP 描述的就是多项式时间、双边有界错误的随机判定问题。它的典型形式是：

• 若正确答案是 yes，算法以至少 \(\frac 23\) 的概率输出 yes；

• 若正确答案是 no，算法以至少 \(\frac 23\) 的概率输出 no。

单边错误也有对应的复杂度类。通常定义下，RP 对 yes 实例有至少一半概率接受，对 no 实例永不接受。也就是说，RP 可能把 yes 错成 no，但不会把 no 错成 yes。coRP 则反过来。

两者的交集是 ZPP。ZPP 可以理解为零错误、期望多项式时间的随机判定计算，也就是复杂度理论中的拉斯维加斯式计算。

重复运行为什么能降错

蒙特卡罗算法最舒服的地方，是可以做概率放大。

假设一次运行的错误概率最多是 \(\frac 13\)，并且每次运行使用独立随机数。对单边错误算法，重复 \(t\) 次之后，只要出现一次确定性证据就停，错误概率往往可以降到类似

的形式。

对双边错误算法，常见做法是重复多次后取多数票。直觉很简单：一次运行可能偏离正确答案，但只要单次正确概率大于 \(0.5\)，独立重复之后，多数结果偏离真实答案的概率会指数下降。

如果 \(p < 0.5\) 是单次错误概率，重复 \(t\) 次并取多数票，那么可以用 Hoeffding 或 Chernoff 类型的不等式得到类似下面的上界：

于是想把错误率降到 \(\delta\)，通常只需要 \(O(\log 1/\delta)\) 次重复。这个代价很温和，所以“有界错误”在算法设计里是一个非常实用的概念。

但这里有一个隐藏前提：重复运行之间的随机性要足够独立。如果伪随机数种子处理得很差，或者多个任务共享了相关性很强的随机源，上面的放大结论就不能直接套用。

拉斯维加斯算法：答案可靠，时间随机

拉斯维加斯算法不允许输出错误答案。随机性影响的是运行时间，或者影响某一轮是否能成功找到可验证结果。典型表述是：算法总是正确，且期望运行时间有限；在复杂度理论里，常见目标是期望多项式时间。

随机快速排序是最常见的例子。它随机选择主元，然后递归排序。无论主元怎么选，只要比较和划分逻辑正确，最后输出的序列一定是有序的。随机性只影响递归树的形状，从而影响运行时间。最坏情况下它仍然可能退化到 \(O(n^2)\)，但对任意固定输入，随机选主元带来的期望时间是 \(O(n \log n)\)。

这和蒙特卡罗算法的气质很不一样。蒙特卡罗算法像是在说：“我很快给你一个大概率正确的答案。”拉斯维加斯算法则像是在说：“我不会骗你，但我不保证这次具体要等多久。”

成功、失败和错误不是一回事

拉斯维加斯算法里有时会出现“失败”这个词，但失败不等于错误。

比如某个随机构造算法一轮尝试可能找不到满足条件的对象，于是返回 retry，重新采样。只要它不会把错误对象当成正确对象输出，它仍然是拉斯维加斯风格。这类算法经常依赖一个结构：随机过程负责“找候选”，确定性检查负责“验真”。找到合格候选就输出；找不到就继续。

伪代码大致是：

while true:
    candidate = randomized_generate()
    if verify(candidate):
        return candidate

如果每一轮成功概率至少是某个常数 \(q > 0\)，那么期望轮数就是 \(1/q\)，也就是 \(O(1)\) 次。

期望时间不等于高概率时间

说一个拉斯维加斯算法期望运行时间为 \(O(n \log n)\)，并不表示每次运行都接近这个时间。期望只是平均意义上的保证，尾部还需要额外分析。

工程上如果要设置超时，不能只看期望复杂度，还要看尾界。一个简单但粗糙的工具是 Markov 不等式。若运行时间随机变量为 \(T\)，则

所以，如果某个拉斯维加斯算法的期望时间是 \(E\)，运行超过 \(3E\) 的概率最多是 \(\frac 13\)。这个界通常不够紧，但它至少说明一件事：从期望时间可以得到某种超时概率控制，只是这个控制未必漂亮。

很多实际算法还会使用重启策略。对于尾部很重的随机搜索，长时间卡在一次坏运行里未必划算；定期重启，反而可能改善整体表现。但重启策略本身也需要分析，不能只凭直觉。

两类算法的相互转化

蒙特卡罗和拉斯维加斯不是两个互不相干的盒子。很多时候，经过简单封装，一类算法可以呈现出另一类算法的接口；也有很多时候不能。

拉斯维加斯到蒙特卡罗：加一个超时

从拉斯维加斯到蒙特卡罗很容易：给算法加一个时间上限。

若在时间内完成，就输出正确答案；若超时，就返回某个默认答案，或者在判定问题里按某种约定处理。

由于超时可能导致错误或不可用，这个包装后的算法就有了蒙特卡罗味道。

假设原算法的运行时间为随机变量 \(T\)，并且期望运行时间为 \(\mathbb{E}[T]\)。如果运行到 \(3\mathbb{E}[T]\) 还没结束就强行停止，那么根据 Markov 不等式，超时概率至多是 \(\frac 13\)。如果超时后随便猜一个答案，错误概率也至多增加这个超时概率。通过更长的时间预算，比如 \(k\mathbb{E}[T]\)，超时概率可以降到 \(\frac 1k\)。

这是一种很朴素的转化：牺牲“永远正确”，换来“固定预算内结束”。

蒙特卡罗到拉斯维加斯：除非错误能被发现

反方向更微妙。

一个蒙特卡罗算法如果只是给出答案，而我们没有办法验证答案对错，那就不能简单地变成拉斯维加斯算法。重复运行可以降低错误概率，却不能把错误概率降成零。哪怕运行一百万次取多数票，仍然只是“极高概率正确”，不是“必然正确”。

真正能转化的情况，通常需要可验证证书。也就是说，随机过程可以负责生成候选答案，但候选答案一旦出现，我们必须能用确定性方法快速检查它是否真的正确。检查通过才输出，检查不通过就重试。

一个典型例子是随机化因数分解。比如某个随机过程试图为合数 \(N\) 找一个非平凡因子 \(d\)。它可能很多轮都找不到，也可能生成一些没用的候选数；但一旦它给出 \(d\)，我们只需要检查

就能确认 \(d\) 是否真的是 \(N\) 的非平凡因子。只要算法规定“验证通过才输出，否则继续随机尝试”，它就不会输出假因子。随机性影响的是等待时间，而不是答案正确性。这就是拉斯维加斯式的包装。

这也是很多随机算法设计里的黄金结构：随机性负责扩大搜索空间，确定性验证负责守住正确性边界。

但并不是所有蒙特卡罗算法都能这样处理。关键区别在于：验证一个候选对象是否合法，和验证它是不是全局最优，往往不是一回事。

Karger 最小割算法就是反例。它随机收缩边，最后输出一个割。这个割是否合法很容易检查，割的大小也很容易计算；但它是不是整张图的全局最小割，就不能靠这个候选割本身快速确认。也就是说，算法每次都能给出一个“合法的割”，但我们无法仅凭局部检查知道它是不是“最小割”。如果再运行一个确定性最小割算法去验证最优性，当然可以确认，但那就相当于重新解决了原问题，失去了用随机算法快速求解的意义。

所以，蒙特卡罗能否改装成拉斯维加斯，关键不在于“能不能重复运行”，而在于“错误能不能被发现”。如果错误候选会被验证器挡住，就可以失败后重试；如果错误答案和正确答案在验证层面无法区分，重复再多次也只能提高置信度，不能得到零错误保证。

经典案例

Miller-Rabin：典型的蒙特卡罗素性测试

Miller-Rabin 用随机底数测试一个整数是否为合数。如果它返回 composite，可以信任：这个数确实是合数。如果它返回 probably prime，则只是说明这几轮随机测试没有找到反证。

对奇合数而言，随机底数骗过测试的概率有良好上界。重复 \(t\) 轮后，误把合数当成 probably prime 的概率会指数下降。

它不是拉斯维加斯算法，因为当它说 probably prime 时，并没有给出一个可快速验证的“素数证书”。当然，现代算法里确实存在确定性多项式时间素性测试 AKS，也存在不同形式的素性证书。但那已经不是“把 Miller-Rabin 简单重复直到必然正确”的故事。

工程上使用 Miller-Rabin 时，通常会先做小素数试除，再做若干轮随机测试。对固定机器字长的整数，还可以使用一组已知底数得到确定性结果。这里可以看到理论和工程之间的分界：教材常分析随机底数下的错误概率，实际库函数则可能利用输入范围把随机性消掉。

随机快速排序：典型的拉斯维加斯排序算法

随机快速排序不会输出“差不多排好”的数组。只要比较器满足一致性，划分过程正确，它最终输出的就是完全有序数组。随机性只决定每次选哪个主元，从而影响递归是否平衡。

如果输入已经有序，固定选第一个元素当主元的快速排序会退化；随机选主元则让这种结构性坏输入失效。对每一对元素，它们被比较的概率可以分析出来，最后得到期望比较次数为 \(O(n \log n)\)。

这是一个很干净的拉斯维加斯例子：正确性来自确定性排序逻辑，效率来自随机化避免坏结构。

不过它并不是“没有最坏情况”。某次运行如果连续选到极差主元，仍然可能接近 \(O(n^2)\)。只是这种运行路径概率很低。实际实现中还会配合三数取中、小数组切换插入排序、递归深度保护等策略。C++ 标准库中常见的 introsort 思路甚至会在递归太深时切换到堆排序，用确定性 fallback 兜住最坏复杂度。

Freivalds 算法：用随机向量检查矩阵乘法

给定三个矩阵 \(A\)、\(B\)、\(C\)，想检查 \(AB = C\)。直接计算 \(AB\) 通常需要 \(O(n^3)\)。Freivalds 算法随机选一个向量 \(r\)，检查

是否成立。一次检查只需要矩阵向量乘法，复杂度是 \(O(n^2)\)。

如果 \(AB = C\)，算法一定接受。如果 \(AB \ne C\)，算法仍有一定概率被随机向量骗过。因此它是单边错误的蒙特卡罗算法。重复多次可以把错误概率降得很低。

这个例子很适合说明随机算法的味道：它不试图完整重算矩阵乘法，而是用随机投影去捕捉差异。

这里也能看到“验证”的边界。Freivalds 验证的是一个等式命题，不是构造 \(AB\) 本身。它能快速判断一个给定结果大概率对不对，但不能直接产出正确乘积。随机化有时不是替代计算，而是替代昂贵的全量校验。

Karger 最小割：成功概率可放大，但不是每次都对

Karger 的随机收缩算法用于无向图最小割。它反复随机收缩边，直到只剩两个超级点，此时跨越两部分的边形成一个割。单次运行有一定概率得到全局最小割，但也可能在早期收缩掉最小割中的边，从而失败。

这是蒙特卡罗算法的另一个典型样子：运行时间很好控制，输出是一个候选答案，正确性带概率。候选割的大小当然可以计算，候选割是否合法也很容易检查；但它是不是全局最小割，并不能靠一个局部检查快速确认。除非再运行一个确定性的全局最小割算法，否则无法直接验证最优性，而那通常就失去了随机算法本来的意义。

常见做法是重复运行很多次，取最小的候选割。重复次数足够多时，得到真最小割的概率很高。

这个例子提醒我们，能检查“候选对象是否合法”和能检查“候选对象是否最优”是两回事。一个割当然合法，但它是否为最小割，需要解决原问题级别的全局判断。很多优化问题的随机算法都卡在这里。

Bounded-error 到底 bounded 在哪里

Bounded-error 直译是“有界错误”，但在随机算法语境里，它通常指错误概率有界，而不是数值误差大小有界。

对于判定问题，错误就是 yes/no 答错。对于搜索或优化问题，错误可能是输出不满足条件，或者没有达到承诺的近似比。

复杂度类 BPP 里的 bounded-error 指的是：存在一个多项式时间随机算法，对任意输入都以至少 \(\frac 23\) 的概率给出正确答案。这个常数可以通过放大换成 \(1 - 2^{-100}\)，所以 BPP 的本质不是 \(\frac 23\) 这个数字，而是“正确概率和随机猜测之间有稳定间隔”。

RP 和 coRP 则是单边 bounded-error。RP 里，no 实例永远不被接受；yes 实例以至少某个常数概率被接受。coRP 反过来。

ZPP 可以从两个角度理解。

一方面，

另一方面，ZPP 对应期望多项式时间的拉斯维加斯判定算法。

这个等价很有启发性：如果 yes 和 no 两边都能通过单边错误算法找到确定证据，那么可以交替运行它们。RP 算法一旦接受，就可以确认 yes；coRP 算法一旦拒绝，就可以确认 no。谁先给出确定证据就停。由于正确一边会以足够概率给出证据，期望时间是多项式的；由于停下时拿到的是确定证据，答案不会错。

这段关系在概念上很漂亮，但写程序时不要过度套用。实际问题里你未必同时拥有 RP 和 coRP 两个方向的算法，也未必有能快速检查的证据结构。复杂度类告诉我们“在抽象模型里什么等价”，工程实现还要看证书、数据规模、随机源、超时策略和失败处理。