Chap11 随机算法

返回：0400 算法设计与分析总目录 · 上一章：0410 Chap10 局部搜索

1、学习目标

随机算法把随机性作为算法设计工具。它不是“碰运气”，而是用概率分析证明算法在期望意义或高概率意义下表现良好。

模块	要掌握的内容
随机化思想	随机选择、打乱输入、随机试验
期望分析	指示变量、期望线性性
算法类型	Las Vegas、Monte Carlo
典型问题	竞争解决、MAX 3-SAT
概率界	Markov、Chebyshev、Chernoff 直觉

2、为什么使用随机性

随机化常用于：

1. 避免最坏输入卡死固定策略。
2. 简化算法设计。
3. 在复杂问题上获得期望或高概率保证。
4. 打散冲突，如哈希、负载分配、快速排序轴点。

随机快速排序就是典型例子：最坏情况仍可能发生，但随机选轴点让期望复杂度变好。

3、Las Vegas 与 Monte Carlo

类型	正确性	运行时间
Las Vegas	总是正确	运行时间随机
Monte Carlo	可能小概率错误	运行时间通常固定或可控

例：

算法	类型
随机快速排序	Las Vegas，排序结果总正确，时间随机
随机素性测试	Monte Carlo 或单边错误版本

4、期望线性性

期望线性性：

E[X + Y] = E[X] + E[Y]

无论 X、Y 是否独立都成立。这是随机算法分析里最常用的工具。

常用方法：

1. 把总成本拆成若干指示变量。
2. 分别计算每个指示变量为 1 的概率。
3. 求和得到期望。

指示变量：

X_i = 1 表示事件 i 发生
X_i = 0 表示事件 i 不发生
E[X_i] = Pr[X_i = 1]

5、竞争解决

竞争解决可以理解为多个请求同时竞争同一资源。随机化策略常让参与者以某个概率尝试，失败后重试。

一个简化模型：

n 个节点同时争用信道
每轮每个节点以概率 p 发送
恰好一个节点发送则成功

恰好一个成功的概率：

n * p * (1-p)^(n-1)

选择合适的 p 可以让成功概率保持常数级别。

6、MAX 3-SAT

MAX 3-SAT：给定若干 3-CNF 子句，目标是满足尽可能多的子句。

简单随机算法：

每个变量独立随机取 true/false

对于一个有 3 个文字的子句，只有一种赋值会让它不满足，所以满足概率：

1 - 1/8 = 7/8

若共有 m 个子句，用指示变量 X_i 表示第 i 个子句被满足，则：

E[X] = E[sum X_i] = sum E[X_i] = 7m/8

因此随机赋值期望满足 7/8 的子句。

7、Chernoff Bounds 直觉

期望只告诉平均值，但有时需要知道结果偏离期望的概率。Chernoff Bounds 用来控制独立随机变量和的尾部概率。

直觉：

大量独立随机试验的总和，远离期望的概率会指数级下降。

常见用途：

1. 随机采样误差控制。
2. 随机负载均衡。
3. 随机算法高概率成功证明。
4. 哈希桶大小控制。

不需要先背复杂公式，先记住它解决的问题：从“期望好”升级到“高概率也好”。

8、随机算法分析套路

步骤	内容
定义随机变量	成本、成功次数、冲突数
拆成指示变量	把复杂总量拆开
计算概率	每个事件发生概率
用期望线性性	求总期望
需要高概率时	用 Chernoff、Markov 等概率界

9、随机化与近似

随机算法常和近似算法结合：

问题	思路
MAX 3-SAT	随机赋值得到期望 7/8
随机舍入	线性规划分数解按概率取整
负载均衡	随机分配再用概率界分析最大负载
采样估计	用少量样本估计整体

随机不等于无保证，关键是把保证写成期望或高概率形式。

10、易错点

易错点	修正
认为随机算法结果不可信	看它是 Las Vegas 还是 Monte Carlo
期望线性性要求独立	不要求独立
只算期望不看波动	需要高概率时用概率界
MAX 3-SAT 满足概率算成 1/2	3 个文字子句随机满足概率是 7/8
把随机化当工程玄学	随机算法要有概率分析

11、复盘清单

检查项	状态
能区分 Las Vegas 和 Monte Carlo	待复盘
能解释期望线性性	待复盘
能用指示变量分析简单随机过程	待复盘
能推导 MAX 3-SAT 的 7/8 期望	待复盘
能说出 Chernoff Bounds 的用途	待复盘
能说明随机化和近似算法的关系	待复盘