蒙特卡洛算法是一种随机化算法,可能返回错误结果,但在给定假设下,其错误概率有界。它通常保证运行时间不超过指定上界,以牺牲正确性的确定保证来换取计算效率。这些保证针对每一个固定输入:概率是相对于算法内部的随机选择而言的,不一定涉及输入的概率分布。该术语在数值计算中还有更广泛的含义,涵盖通过随机抽样估计数值的方法。
定义与范围
普通的确定性算法在接收到相同输入时,总会沿着相同的计算路径执行。随机化算法则还会进行随机选择,因此不同次执行的输出、运行时间,或两者都可能不同。
在标准的判定问题框架中,若蒙特卡洛算法 计算布尔函数 ,且对于每个有效输入 ,都有
则称其错误概率上界为 。其中, 表示算法内部的随机选择。算法的运行时间以输入长度的某个指定函数为上界;在复杂性理论的讨论中,这个函数通常是多项式。惯用的常数错误概率上界是 ,不过,其他小于 的常数上界通常也可以通过重复执行来降低。
这种保证是对输入取最坏情况、对随机选择计算概率。如果一个算法对大多数输入都能成功,却对某些输入始终失败,那么仅仅平均成功率高,并不足以使其满足这一保证。
在数值计算中,输出通常是一个估计值,而非“是”或“否”的答案。相应的保证可能改为如下形式:
其中, 是目标量, 是估计值, 是容许误差, 是允许的失败概率。因此,“错误”可以指“超出要求的误差范围”,而不只是与精确值不相等。
与其他算法方法的关系
蒙特卡洛算法与拉斯维加斯算法
拉斯维加斯算法只要返回答案,答案就一定正确,但运行时间取决于随机选择。其性能通常用期望运行时间的上界来描述。
因此,两者的核心区别是:
| 方法 | 正确性 | 运行时间 |
|---|---|---|
| 蒙特卡洛算法 | 允许有界的错误概率 | 通常具有指定的最坏情况上界 |
| 拉斯维加斯算法 | 保证返回的答案正确 | 具有随机性;通常分析其期望值 |
这两个名称指的是随机性的不同用法,而非不同的应用领域。例如,随机化快速排序通常归为拉斯维加斯算法:随机选择枢轴会影响执行时间,但不会影响排序结果的正确性。
对于期望运行时间有限的拉斯维加斯算法,有时可以通过设置运行时限,并在超时时输出备用答案,将其转化为蒙特卡洛算法。此时,新增错误的概率不超过超时概率。反向转换则需要额外条件,例如能够高效验证候选答案,并非总能实现。
近似与随机化
蒙特卡洛算法不一定是近似算法。它可能寻求精确答案,例如判断一个整数是否为素数,同时允许以很小的概率作出错误回答。反过来,确定性近似算法可以不使用随机性,而始终满足其近似保证。
随机化近似方法将这两种思想结合起来:近似答案必须以指定概率满足指定的精度要求。
单侧错误与双侧错误
蒙特卡洛判定算法通常根据哪些答案可能出错来分类。
单侧错误是指算法对一类输入始终处理正确,而对另一类输入可能误判。例如,某种检验可能绝不把素数判为合数,却偶尔会把合数判为可能为素数。必须明确说明错误的方向:仅说“单侧”并不能表明哪一种答案具有确定性。
双侧错误是指两种答案都可能出错,但对每个输入,错误概率都有各自的上界。
这一区别会影响如何综合多次执行的结果。对于单侧错误检验,一次具有确定性的结果就可能足以作出判定。对于双侧错误检验,多数表决是降低错误概率的标准方法。
在计算复杂性中,复杂度类 BPP 包含可在多项式时间内以有界双侧错误求解的判定问题。复杂度类 RP 采用单侧错误:对答案为“否”的实例始终拒绝,对答案为“是”的实例则以至少 的概率接受。将这一方向反过来,就得到 co-RP。
通过重复执行降低错误概率
假设每次执行的错误概率至多为 。如果各次执行使用相互独立的随机选择,那么运行算法 次并采用多数表决,就能使错误概率随 指数下降。
当 为奇数时,一个标准的集中不等式给出:
当 与 之间保持固定的正间隔时,要将错误概率降至至多 ,只需重复 次。
对于单侧错误算法,如果其无法给出定论或具有误导性的结果出现的概率至多为 ,那么只有在 次独立重复中全部出现这一结果时才采用它,便可得到 的错误概率上界。
独立性十分重要。使用完全相同的随机种子重复执行,通常只会重现相同的行为,而不会产生新的独立试验。重复执行也无法弥补数学模型的缺陷或实现中的系统性错误。
代表性示例
米勒—拉宾素性检验
米勒—拉宾素性检验是单侧错误蒙特卡洛算法的典型示例。它检验每个素数都必须满足的代数条件。如果某个受检底数不满足这些条件,那么输入一定是合数。如果满足这些条件,输入仍只能视为可能为素数。
对于奇合数 ,在从 中均匀选取的底数中,至多四分之一能通过一次强可能素数检验。因此,进行 轮独立随机检验后,将合数误判为可能素数的概率至多为
这是针对固定合数输入、相对于所选底数而言的概率。它并不直接等于一个数通过检验后仍为合数的概率;后一种解释还取决于候选数的选取方式。
对于某些有界输入范围,使用适当的预定底数可以构成确定性检验。这些变体应与随机化算法区分开来。
多项式恒等性检验
多项式恒等性检验要判断一个以代数形式表示的多项式是否恒等于零。将表达式完全展开为各个项可能代价很高,因此算法可以改为在随机选取的点上求值。
施瓦茨—齐佩尔引理指出,如果某个域上的非零多元多项式总次数至多为 ,且每个变量都从该域的有限子集 中独立、均匀地抽取,那么
恒等于零的多项式在所有点上的值都是零。因此,只要一次求值结果非零,就能证明该多项式不恒等于零;而求值结果为零则可能造成误判。选取足够大的抽样集合并重复检验,就能将单侧错误概率控制在要求的范围内。
矩阵乘积验证
弗赖瓦尔兹算法用于检查给定的矩阵乘积 是否正确,而不必直接计算 的每个元素。对于 矩阵,该算法选取一个随机二元向量 ,并检验是否有
如果乘积正确,等式总是成立。如果乘积不正确,均匀抽取的二元向量未能揭示错误的概率至多为 。每轮检验使用 次算术运算,而直接进行矩阵乘法需要 次。独立重复检验可以降低接受错误乘积的概率。
数值蒙特卡洛方法
范围更广的蒙特卡洛方法利用随机抽样来估计积分、概率、预期结果及其他量。这一术语在20世纪40年代斯坦尼斯瓦夫·乌拉姆、约翰·冯·诺伊曼及其合作者开展的计算工作中逐渐确立,尤其与粒子输运方面的工作有关。
一个基本示例是通过独立样本估计期望值 :
如果每个样本都有有限的方差 ,那么
因此,估计量的标准差按 的速率下降。要将标准差减半,通常需要将样本数增加到原来的四倍。
这一抽样收敛速率的指数并不显式依赖维数,这有助于解释蒙特卡洛方法为何适合用于高维积分。不过,方差、样本生成成本以及表示稀有事件的难度,仍可能强烈依赖维数和问题结构。
应用领域包括粒子输运、金融模拟、统计推断,以及计算机图形学中的光传输估计。蒙特卡洛树搜索利用抽样结果来指导搜索决策,但仅凭这一名称,并不能认定它具有复杂性理论中那种针对固定有限次运行的错误概率保证。
实际局限与可靠性
随机性假设。 证明通常假设所用的随机比特或样本相互独立且服从均匀分布。实际实现一般使用伪随机数生成器,必须考虑其有限状态和确定性行为。在对抗性环境中,除了统计质量,可预测性也可能十分重要。
抽样偏差与依赖性。 如果样本来自错误的分布,错误概率保证就可能失效。样本之间的相关性可能减少重复试验所获得的有效信息量。置信度计算必须反映实际的抽样过程。
数值误差。 数学保证可能以精确算术为前提。舍入、溢出或不稳定的计算会引入不同于随机抽样误差的其他误差。
多次决策中的误差累积。 单次执行的失败概率很小,并不自动意味着整个系统的失败概率也很小。如果系统作出 次决策,每次的错误概率至多为 ,那么由并集界可知,至少出现一次错误的概率至多为 ,且不超过1。这一上界不要求各次决策相互独立。
验证与失败后果。 如果输出可以高效核验,验证就能发现部分失败,或为另一种算法设计提供支持。如果核验困难,可靠性就更直接地取决于概率分析是否成立,以及实现所依赖的假设是否成立。