04篇把随机性放在算法内部，要求固定输入后再谈期望。现在比较两种不同承诺：随机选择无论抽到什么主元都会返回正确答案，但耗时变化；随机收缩总会返回一个合法割，却可能错过最小割。

这两种随机性不能用一句“期望表现不错”概括。需要分别回答输出是否一定正确、成本对谁取期望，以及重复执行改善的是哪一项。

随机选择的答案始终正确

输入是长度n的整数数组和从0开始的秩k，要求0≤k<n；输出排序后第k个值，允许重复元素。每轮均匀选取当前数组的一个位置，把元素分为小于、等于、大于主元三组。

若k小于左组长度，继续在左组找同一秩；若k落在等值组，直接返回主元；否则在右组寻找k减去左组与等值组长度后的秩。三路划分把重复元素一次处理完，避免所有元素相等时仍每轮只移走一个。

正确性只依赖三组的大小和顺序关系，与主元是否幸运无关。每轮保留的子问题严格缩小，空输入或越界秩应在入口拒绝。这是Las Vegas型保证：结果一定正确，运行成本是随机变量。

对任意固定输入，至少一半的位置落在按秩划分的中间一半。选到这样的主元，下一轮待查部分至多约3n/4；重复值只会扩大可直接结束的等值组。每轮遇到这种缩小的概率至少1/2，因此在同一规模阶段等待有效缩小的期望轮数不超过2。

把各阶段的线性扫描成本求和，得到O(n)期望工作量：n、3n/4、(3/4)²n等形成几何级数。小规模取整只改变常数。这里的期望对内部均匀主元选择取，不要求输入随机排列，也不是把若干次调用摊还后得到线性。

坏主元序列仍可每次只排除一个元素，累计Θ(n²)工作。需要无条件最坏线性时，应采用21篇介绍的确定性选择方法，而不能把期望O(n)改写成最坏O(n)。

全局最小割的随机收缩

26篇处理固定源汇的最小割。这里输入是n≥2个顶点的无向无权多重图，求任意非空真子集S，使跨越S及其补集的边出现次数最少。平行边各计一次，不能合并成一条后仍按普通边均匀抽样。

若图不连通，任一连通分量与其补集已经构成容量0的最小割，先返回它。以下概率证明针对连通图，其最小割大小λ≥1。自环不影响割，应在入口排除或在收缩中删除。

一次收缩从当前所有边出现中均匀选择一条，把两端合并成超级顶点。保留新超级顶点之间所有平行边，删除自环，直到只剩两个超级顶点。它们对应原图的一个非平凡划分，跨边数是此次返回的割值。

与27篇的匹配不同，收缩不是选择一批互不相交边；同一个超级顶点可以继续参与后续合并。实现需要保存原顶点的分组，最终返回原图中的S，而不能只给一个无法核对的数字。

固定一个最小割，计算它存活的概率

事先固定原图的一个最小割C。只要没有收缩C中的边，两侧就不会被合并到一起，C一直保存在收缩后的多重图中。

条件于已经存活到r个超级顶点。收缩图的任何割都对应原图的一个割，所以每个超级顶点的度至少λ；由度数和可知当前边数至少rλ/2。被固定割C禁止收缩的边仍恰有λ条，因此下一步误选它的概率至多2/r，存活概率至少1−2/r。

从r=n收缩到2，固定割一路存活的概率至少为

∏r=3n(1−2r)=∏r=3nr−2r=2n(n−1).\prod_{r=3}^{n}\left(1-\frac2r\right)=\prod_{r=3}^{n}\frac{r-2}{r}=\frac{2}{n(n-1)}.

n=2时乘积为空，概率为1，与公式相符。最后若固定割存活，剩下两组正好实现它。算法还可能找到别的最小割，所以这只是成功概率下界，不是所有图上的精确成功率。

每次返回的都是合法割，值不小于λ；失败表示返回了更大的割。合法性可直接检查，最优性却不能仅靠一张分组列表确认。这是有单侧目标误差的Monte Carlo型算法；本篇不提供能够检测每次失败的证书。

重复次数来自目标失败率

记单次成功下界p=2/[n(n−1)]。从原图重新开始，独立运行T次并取割值最小的合法结果。所有试验都失败的概率至多

(1−p)T≤e−pT.(1-p)^T\le e^{-pT}.

要让失败概率不超过δ，0<δ<1，取T≥⌈n(n−1)ln(1/δ)/2⌉就足够。这里的独立性是重复放大的条件，不能把同一次收缩继续执行当成新的试验。

若希望失败率至多n^{-c}，固定c>0，代入δ=n^{-c}即可得到O(n²log n)次重复。这才是一种明确的高概率最优保证；常数次数不能自动冠以“高概率”。运行成本还要乘上单次收缩成本。

固定种子使教学程序可复跑，但伪随机发生器不等同于数学证明中的独立随机源。尤其是每轮重新设成同一个种子，会重复同一条收缩轨迹，没有得到T次独立机会。实验报告多种种子的结果，仅说明这些执行发生了什么。

边界与实现成本

把平行边去重会改变均匀抽样的分布，也改变度数与割值。若某对超级顶点之间有十条边，另一对只有一条，前者应有后者十倍的抽中概率，不能两对各占一半。

收缩循环还必须处理输入不连通的情况，否则未剩两组时活跃边表可能已经为空。n=0或1不存在非平凡割，不能随意输出0再宣称解决了同一问题。

教学实现examples/advanced-algorithms/randomized_algorithms.py复用10篇的DSU保存收缩分组。每轮重新扫描原边列表、筛出跨组边，按出现次数抽样。单次需要O(n+nmα(n))的摊还并查集工作，活跃边列表和分组占O(n+m)空间；Python集合操作另外按期望成本计。这里的“摊还”描述并查集操作，不是随机收缩的成功率，也不是快速收缩变体的时间界。

random_select(values, k, rng)返回值和扫描元素数，临时三路列表占O(n)空间；karger_cut(n, edges, rng)返回割值和原顶点集合的一侧。两者都注入随机发生器，便于复跑同一配置。

1
python3 examples/advanced-algorithms/check_randomized_algorithms.py

本轮用排序参照检查6015次选择，共扫描45195个元素，另有7个非法输入拒绝。最小割参照独立枚举非空真子集；对断开图、平行边图、三角形、四环、四顶点完全图加一条桥五种输入分别运行种子0–19，并逐次检查返回划分合法、割值不小于穷举最优。

带桥图最优值为1，20次结果依次为[3,1,3,1,1,1,3,3,3,1,3,3,4,1,4,1,3,1,3,4]，观察到8次命中。这个比例不是成功概率的证明；其他四图均20次命中，也不能据此声称算法永不失败。原始结果保存于writing-plans/advanced-algorithms/evidence/randomized-algorithms-results.json。

练习

  1. 对五个互异元素选择最小值，写出一条每次只排除最大元素的主元序列。计算扫描规模之和，解释它为何不反驳期望线性界。
  2. 对n=10、δ=0.01，按正文公式计算足够的独立重复次数。若只换输出文件名但始终重置同一随机种子，失败率公式的哪个前提不再成立？

参考资料