随机化算法详解：从期望、集中不等式到Monte Carlo实践

简介《算法设计》课程英文课件第11章聚焦随机化算法Randomized Algorithms面向已掌握基础算法、希望系统理解随机化思想与概率分析的计算机专业学生、考研学生及算法竞赛选手。课件先概述随机化算法的两类基本形态优化问题中追求最优解且关注平均复杂度决策问题中允许以极小概率出错。随后以经典最近点对问题为主线展示随机选取子集、确定初始距离、划分网格、倍增网格尺寸、检查同网格点对并更新结果等完整流程并给出平均O(n)时间复杂度的推导。同时还延伸到素数测试和Rabin-Karp模式匹配体现随机化在不同问题下的灵活应用。资源为1个PPT文件约494KB英文原版幻灯片包含定义、伪代码、图示和复杂度分析适合双语教学、课后复习和面试准备。已有163人加入学习可作为算法设计课程第11章的配套参考资料。1. Randomized Algorithms 不是撞运气而是把随机性当计算资源Randomized Algorithms 这一章在算法设计与分析课程里常被排到最后很多人把它当成“选修中的选修”。但真实情况正好反过来Bloom filter、跳表、随机化快速排序、通用哈希、RSA 里的素数生成这些生产环境天天在用的东西底层全是随机化算法。它的核心思路是把“最坏情况”从确定性算法的必然事件压缩成概率意义上的小概率事件用很小的失败概率或近似偏差换确定性算法给不出的时间下界。这篇按课件一贯的叙事线走先立理论再给三个能直接跑通的最小实现接着讲参数权衡最后讨论随机数质量与去随机化验证。正在准备算法设计与分析期末编程题、或者要在系统里自己写随机组件的工程师都能从里面拿到可复现的东西。2. 期望分析与集中不等式Randomized Algorithms 的两个理论支点随机化算法的正确性证明通常不依赖具体哪一次随机结果而依赖两个层面期望值和尾概率。前者回答“平均表现如何”后者回答“偏离平均的可能性有多大”。这两件事在课件里是分开讲的但做题和写代码时往往要一起用。2.1 期望的线性性质为什么平均情况那么好算期望的线性性质说的是对于任意随机变量 X 和 Y即使它们完全不独立也有 E[XY] E[X] E[Y]。这一条常常被低估但它几乎是所有随机化算法平均复杂度分析的基础。以随机化快排为例。把数组里的两个元素 x、y 称为“可比较对”它们发生比较当且仅当在递归过程中先于两者被选为主元的元素在两者之外。对任意一对元素它们被比较的概率是 2/(它们在数组中相隔的距离1)。利用线性期望把所有元素对的比较概率加起来得到总比较次数的期望是E[C] Σ 2/(j - i 1) O(n log n)这个推导里元素对之间是否互相独立完全不影响结论。用线性期望把每对元素的贡献求和一步到位。注意区分这里算的是“期望比较次数”不是“以高概率完成的比较次数”。课件里通常先证期望再补充 Boltzmann 界说“偏离期望太远的概率随偏差指数下降”两条线叠加才能得出“几乎总是 O(n log n)”这种更强的结论。2.1.1 用模拟验证期望与集中不等式的关系理论讲得再顺不如跑一次数字直观。下面这个脚本统计掷 n 枚公平硬币时正面数偏离均值超过 0.1n 的经验频率并把它和 Hoeffding 不等式的理论上界对比import random def coin_deviation_freq(n: int, trials: int 20000) - float: over 0 for _ in range(trials): heads sum(random.randint(0, 1) for _ in range(n)) if abs(heads - n / 2) n / 10: over 1 return over / trials for n in (50, 200, 800): freq coin_deviation_freq(n) bound 2 * pow(2.71828, -2 * n * 0.1 * 0.1) print(fn{n:4d}, 经验频率{freq:.6f}, Hoeffding上界{bound:.4e})参数说明参数 n 是硬币数量trials 是模拟轮数0.1 是允许偏离均值的比例阈值。运行后会看到当 n 从 50 涨到 800经验频率从约 1.6e-2 掉到 1e-6 以下而 Hoeffding 上界始终比经验值大一个数量级左右。这个对照说明两件事集中不等式给出的上界足够保守可以用来设计预算但它也偏松工程上要留余量时上界只作为数量级参考不要直接拿它当实际失败概率。2.2 集中不等式概率离期望有多远期望只能说明“长期来看不错”但随机化算法的用户更关心单次运行会不会翻车。集中不等式就是回答“X 偏离 E[X] 超过 t 的概率上界”的工具。课件里最常见的三个不等式适用条件结论典型用途MarkovX ≥ 0P(X ≥ a) ≤ E[X]/a从期望推概率的最粗糙工具Chebyshev已知方差 Var(X)P(X−E[X]HoeffdingX₁…Xₙ 独立且有界P(ΣXᵢ − E ≥ t) ≤ 2e^(−2t²/Σbᵢ²)掷币、抽样误差、随机化快排主元质量实际应用时不需要记全部形式只需要判断“随机变量之间独立吗”“有没有界”然后选能用的最紧的那条。Hoeffding 对独立有界变量最常用Chernoff 变体则可以处理泊松型试验和乘积型阈值。2.3 两种算法契约Las Vegas 与 Monte Carlo随机化算法的正确性契约有两类这个分类比具体算法更重要因为它决定了你怎么设置参数、怎么测试Las Vegas结果永远正确运行时间是随机变量。随机化快排、随机化的 Treap 查找都属此类。它不引入错误概率代价是最坏运行时间可能爆炸但概率极小。Monte Carlo运行时间可以设定上限结果以小概率出错。Miller–Rabin 素性检测、Bloom filter 的查询都属于此类。它们给出的是“能以至少 1−ε 的概率正确”的保证。还有一个容易混淆的细分Monte Carlo 算法有“单侧错误”和“双侧错误”。Miller–Rabin 把合数判成素数是假阳性属于单侧错误而随机化近似算法输出一个在区间内的近似值时上下都可能超差属于双侧错误。单侧错误可以通过重复试验快速压低失败率双侧错误只能靠对称放大样本量两者的参数公式不一样。3. 三个最小实现随机化快排、蓄水池抽样与 Miller–Rabin 素性检测理论和参数讲得多不如三个能直接运行的实现。这三个算法一个代表 Las Vegas、一个代表流式采样、一个代表 Monte Carlo恰好覆盖 Random ized Algorithms 课件最常见的三个例题类型。3.1 随机化快排随机选主元把最坏情况变成概率问题import random def randomized_quicksort(arr): if len(arr) 1: return arr pivot random.randrange(len(arr)) pivot_val arr[pivot] left [x for x in arr if x pivot_val] mid [x for x in arr if x pivot_val] right [x for x in arr if x pivot_val] return randomized_quicksort(left) mid randomized_quicksort(right)参数说明random.randrange(len(arr)) 从当前数组范围等概率取主元下标而不是固定取第一个或最后一个元素。固定主元最坏 O(n²)随机主元后任一特定输入触发最坏情况的概率最多是 2/n且主要发生在总是抽出最小或最大元素时。代码里把等于主元的元素单独放进 mid避免大量重复元素时递归深度失控这是 LeetCode 版快排常被忽视的坑。3.2 蓄水池抽样未知长度流中的均匀抽样import random def reservoir_sample(stream, k: int): reservoir [] for i, item in enumerate(stream): if i k: reservoir.append(item) else: j random.randint(0, i) if j k: reservoir[j] item return reservoir逻辑说明前 k 个元素直接入池。从第 k1 个元素下标 i k开始每个新元素以 k/(i1) 的概率被纳入池子并等概率替换掉池子里的某个旧元素。当流结束时任意位置的元素最终留在池中的概率均为 k/n其中 n 是流总长度。注意这里 random.randint(0, i) 两端都闭合如果写成 random.randrange(i) 会让新元素的入选概率偏小抽样就不是均匀的。这个算法在课件里常被当作“在线均匀抽样”的标准答案实际工程里对应的场景是从日志流、传感器数据或大批量扫描结果里在不知道总条数的前提下抽取固定大小的样本。只要不要求重置就不需要把全量数据落盘。3.3 Miller–Rabin 素性检测单侧错误的 Monte Carloimport random def is_probable_prime(n: int, rounds: int 10) - bool: if n 2: return False if n % 2 0: return n 2 d, s n - 1, 0 while d % 2 0: d // 2 s 1 for _ in range(rounds): a random.randint(2, n - 2) x pow(a, d, n) if x in (1, n - 1): continue for _ in range(s - 1): x x * x % n if x n - 1: break else: return False return True参数说明rounds 是独立随机基底的试验次数默认 10。先把 n−1 分解成 d·2^s 的形式再用随机基 a 做平方探测。如果某次试验没通过平方链直接判定合数全部通过则返回“可能是素数”。返回 True 时合数被误判的概率不超过 4^(−rounds)rounds10 时理论误判率在 1e-6 以下。这里把 Fermat 检测和 Miller–Rabin 放在一起对比效果最明显。用 561卡迈克尔数测试Fermat 在多数基底下都会误判成素数而 M-R 几轮就能踢出合数。所以生产环境不要只做费马小定理检测必须用平方探测。4. Monte Carlo 的参数权衡轮数、采样比例与失败概率怎么定课件里给了各种概率上界公式但实践中最常被问的是“rounds 设多少”“样本量要多大”。这一章给出可以直接抄的参数推演方法和一组参考表。4.1 重复试验次数怎么定用 union bound 控制总失败率对 Miller–Rabin每轮独立试验的错误概率至多 1/4重复 r 轮的错误概率是 (1/4)^r。这个乘积已经足够小不用再做更复杂的联合概率计算。但注意很多工程场景会把“检测失败”和“检测次数超预算”两个事件混在一起严格的写法应该是P(总失败) ≤ P(第1轮坏) P(第2轮坏 | 前一轮没坏) … ≤ r · (1/4)^r用 union bound 收紧后实际所需的轮次比直觉少很多。下面这张表可以直接拿来设计参数目标失败概率Miller–Rabin 轮次Bloom filter 哈希函数数 k随机抽样相对误差 5% (95% 置信度)1e-355约 384 个样本1e-6107约 38416 个样本1e-9159约 3.8e6 个样本表里的抽样行用了简单随机抽样的正态近似公式 n ≈ (1.96/0.05)² · p(1−p)在 p0.5 时样本量最大。实际做 AB 测试或流式统计时样本量先按这个公式起步再配合序贯检验动态调整。4.2 用实验观察轮数和错误率的实际关系import random def mr_error_rate(rounds: int, trials: int, composite_pool): errors 0 for _ in range(trials): n random.choice(composite_pool) if is_probable_prime(n, rounds): errors 1 return errors / trials # 用前 1000 个奇合数做测试池 odd_composites [n for n in range(9, 20000, 2) if not is_probable_prime(n, rounds20) and n % 2 1] for r in (1, 3, 5, 10): print(frounds{r:2d}, 误判率{mr_error_rate(r, 2000, odd_composites[:1000]):.4f})逻辑说明这个实验先筛出一个合数池再统计不同轮次下把这些合数误判成素数的比例。因为测试池里故意放了很多难缠的合数实验得到的误判率通常比理论界的 4^(−r) 还低这符合预期但不能反过来说理论界没用——真实输入分布未知理论上界才是安全线。4.2.1 轮次不是越多越好计算预算与延迟从表里看失败率目标从 1e-6 降到 1e-9 只需要把轮次从 10 加到 15计算量只增加 50%但从 1e-9 再往下压收益就很有限因为此时瓶颈已经不是算法本身的错误率而是随机数生成器的质量、系统熵源、算法实现里平方链的常数开销。生成 RSA 素数时常规做法是每轮 Miller–Rabin 用 16 到 20 轮配合一次确定的 Pocklington 或 Lucas 素性证明来兜底。4.3 Las Vegas 转 Monte Carlo给不确定的运行时间设定上限拉斯维加斯算法的运行时间是无界的工程上不好直接做 SLA。常见做法是给它加上“重试预算”设一个最大尝试次数 T超过就放弃或降级。以随机化快排为例如果每次随机选主元都选到区间最小元素递归深度会达到 n但这种情况的概率是 2/n。设最大深度预算 D当递归深度超过 D 时直接切换到堆排序算法就从 Las Vegas 变成了一个确定时间内结束、最坏结果是排序不完全正确的 Monte Carlo 变体。切换阈值 D 取 4n 时触发概率约为 e^(−Ω(n))几乎没有实际影响。这种“确定性算法兜底 随机化主路径”的组合是生产系统里最常见的落地形态。课件里讲的纯随机化算法在工程上往往要加一个 fallback 分支才敢上线。5. 随机数质量与可复现性种子管理、并行流与抽样偏差陷阱随机化算法的正确性建立在“输入概率分布正确”的前提上。如果随机数生成器不合格或者使用姿势不对再好的算法也会悄悄产生偏差。课件一般只讲“假设有真随机源”但实际工程里的坑都在这一层。5.1 常用伪随机生成器的选型从 MT19937 到 PCGPython 的 random 模块默认用梅森旋转MT19937它统计性质好但状态大、启动慢且在并行场景下容易出现相关性。C 库里的 rand() 往往是 LCG低位周期很短直接取模会产生明显偏差。现代替代品是 PCG 系列和基于 ChaCha20 的 CSPRNG。生成器周期优点典型问题C 库 rand()约 2^31简单、快低位随机性差取模偏差明显MT199372^19937统计性质好历史兼容状态 2.5KB预热慢非密码学安全PCG322^64快、状态小、通过统计测试生态还在整合ChaCha202^256 以上密码学安全抗预测速度比 PCG 慢一个量级非密码学场景随机化快排、蓄水池抽样、蒙特卡洛模拟用 PCG 或 MT 都行涉及安全、抽奖、密钥生成时必须用密码学安全生成器。一个常见误区是把 random.seed(time.time()) 当成“增加随机性”多进程同时启动时会拿到几乎相同的时间戳生成高度相关的随机序列实际效果比固定种子还差。5.2 取模偏差经典有偏抽样 bug把均匀整数映射到 m 个桶时直接取模是错误做法。假设随机数源产生 [0, 2^31) 的均匀整数直接 x % 6 会让 0 和 1 这两个桶分别多获得约 1/32768 的概率增量。单独一次抽样感知不到但像蓄水池抽样、随机洗牌这类执行千万次的算法偏差会被放大到肉眼可辨。import random def sample_with_modulus(rng_high: int, modulus: int) - int: limit (1 31) - (1 31) % modulus while True: x rng_high() if x limit: return x % modulus参数说明limit 是小于 2^31 的最大模数整数倍。当生成的 x 落在 [limit, 2^31) 区间时直接丢弃并重新采样称为拒绝采样。这样每个桶接收到的取值数量严格相等概率完全均匀。Python 的 random.randrange 内部就实现了这一套所以业务代码尽量不要自己写取模逻辑直接交给标准库即可。5.3 并行环境下的随机流隔离多进程并行跑蒙特卡洛模拟时最忌讳共享一个随机数生成器或在每个进程里用相同种子初始化。前者会造成进程间锁竞争和序列相关性后者会让所有进程产出完全相同的结果浪费整机算力。常见做法是按进程或者按任务划分独立随机流。NumPy 1.17 之后的推荐姿势是用 SeedSequence.spawn 生成互不相关且可复现的子种子import numpy as np from numpy.random import SeedSequence, default_rng ss SeedSequence(20240601) children ss.spawn(8) rngs [default_rng(c) for c in children]简单说明SeedSequence.spawn 不是简单地“种子加一”而是通过对父种子做哈希派生确保子序列之间统计独立且互不重叠。同一组子种子在任意机器上可复现同一序列这对调试和回归测试非常关键。5.4 洗牌算法的偏差来源随机洗牌如果用排序法即给每个元素生成随机 key 再排序在 key 冲突时会引入由排序稳定性和冲突解决策略决定的偏差。标准做法是 Fisher–Yates 洗牌从后往前遍历每次把当前元素与前面随机位置交换。Python 的 random.shuffle 已经实现 Fisher–Yates不需要自己写。如果必须自定义注意交换时用 random.randrange(i 1)而不是 random.randrange(n)否则会产生有偏排列。6. 去随机化的接口设计把随机算法变成可验证的确定性结果随机算法的结果天然不可直接复现这让 CI 回归测试和线上问题排查变得棘手。下面是一个既保留随机性优势、又能稳定验证的设计套路把随机种子从算法内部提升到接口层。6.1 固定种子 种子扫描的验证方法实现上把所有随机调用收敛到少数几个入口函数并允许从外部注入随机源import random def sort_with_seed(arr, seed: int) - list: rng random.Random(seed) # 用 rng 代替 random 模块做内部随机决策 return randomized_quicksort(arr, rng)测试时先固定若干种子跑一次冒烟测试判断功能正确再做种子扫描估计失败率def seed_sweep(fn, inputs, seeds200): failures 0 for s in range(seeds): try: fn(inputs, seeds) except AssertionError: failures 1 return failures / seeds逻辑说明因为随机种子是显式传入的任何单次失败都可以用对应的种子精确复现。种子扫描的目的不是证明“绝无问题”而是估计算法在这个特定输入分布上的实际失败率。如果扫描 200 个种子出现一次失败先不要急着加轮次先确认失败是否集中在某类输入上再决定是修算法还是修边界条件。6.2 去随机化的两条生产线去随机化不是让随机算法消失而是让“随机性的效果”可以被确定性手段逼近。常用思路有两类第一类是“随机采样改确定性选择”。比如 Miller–Rabin 的高精度版本可以把随机基换成一个固定的、针对目标位数验证过的基集合。对 64 位以内的整数固定用 [2, 325, 9375, 28178, 450775, 9780504, 1795265022] 这 7 个基底就足够确定性地判断素性。第二类是“随机选择改中位数分组”。算法第四版里提到的确定性快排选主元用三数取中法近似随机化效果复杂度退化到最坏 O(n log n) 的概率远小于手写随机版本踩雷的概率适合对可复现性要求极高的环境。调试这类算法时建议先跑一遍固定种子的单测再针对极端输入做种子扫描最后再上正式的失败概率验证。多跑几个种子看分布比在一个种子上跑到天荒地老更能说明问题。本文还有配套的精品资源点击获取