第5章 概率分析与随机算法

导读

在许多实际场景中，算法的输入不是确定性的，而是具有某种随机性。概率分析（Probabilistic Analysis）是一种分析算法在随机输入下期望运行时间的方法。而随机算法（Randomized Algorithm）则是在算法执行过程中引入随机性，利用随机选择来改善算法的性能或简化算法的设计。

本章将介绍概率分析的基本方法，包括指示器随机变量和期望的线性性，并通过一系列经典例子（如生日悖论、球与箱子问题、序列分析）来展示概率分析的应用。我们还将学习随机算法的设计思想，包括随机化快速排序、随机化选择算法等。

核心概念详解

5.1 概率基础

概率空间：

一个概率空间由样本空间Ω和概率测度P组成。样本空间Ω是所有可能结果的集合，概率测度P为每个事件分配一个[0,1]之间的概率值。

基本性质：

• 0 ≤ P(A) ≤ 1，对所有事件A
• P(Ω) = 1
• 若A和B互斥，则P(A∪B) = P(A) + P(B)

条件概率：

P(A|B) = P(A∩B) / P(B)

贝叶斯定理：

P(A|B) = P(B|A)P(A) / P(B)

独立性：

若P(A∩B) = P(A)P(B)，则A和B独立。

5.2 随机变量与期望

随机变量：

随机变量X是从样本空间到实数的函数。

期望（Expectation）：

E[X] = Σ x · P(X = x)（离散情况）

E[X] = ∫ x · f(x) dx（连续情况）

期望的线性性：

E[X₁ + X₂ + ... + Xₙ] = E[X₁] + E[X₂] + ... + E[Xₙ]

这是概率分析中最强大的工具之一。即使随机变量之间不独立，期望的线性性也成立。

方差：

Var[X] = E[(X - E[X])²] = E[X²] - (E[X])²

5.3 指示器随机变量

指示器随机变量（Indicator Random Variable）是概率分析中的重要工具。对于事件A，定义指示器随机变量：

I{A} = 1，若A发生

I{A} = 0，若A不发生

关键性质：

E[I{A}] = P(A)

这个简单的关系使得我们可以将计数问题转化为期望计算问题。

示例：n个人中有多少对生日相同？

• 定义指示器变量X_ij = I{第i个人和第j个人生日相同}
• E[X_ij] = 1/365
• 总对数X = Σ X_ij（对所有i < j）
• E[X] = C(n,2) · 1/365 = n(n-1)/(2·365)

5.4 生日悖论

生日悖论（Birthday Paradox）是一个经典的概率问题：在一个房间里需要多少人，才能使至少有两人生日相同的概率大于50%？

分析：

• 假设一年365天，生日均匀分布
• n个人生日都不同的概率：

P(不同) = 365/365 × 364/365 × 363/365 × ... × (365-n+1)/365

• 当n = 23时，P(不同) ≈ 0.493，即至少两人生日相同的概率 > 50%

直觉解释：

虽然23看起来很小，但我们需要考虑的是C(23,2) = 253对可能的配对。每对都有1/365的概率生日相同，所以至少一对相同的概率相当高。

算法意义：

生日悖论在哈希表分析中有重要应用。当哈希表中插入约√m个元素时（m为表大小），发生冲突的概率就达到50%。

5.5 球与箱子问题

球与箱子问题（Balls and Bins Problem）是另一个经典的概率模型：将n个球随机投入b个箱子中。

关键问题：

每个箱子中球的期望数：E = n/b

特定箱子为空的概率：P = (1 - 1/b)^n ≈ e^(-n/b)

最满箱子中的球数（当n = b时）：

- 期望最大负载约为ln n / ln ln n

- 这比平均负载1大得多

至少一个箱子为空的概率（当n = b时）：

- 约为1 - 1/e ≈ 0.632

应用：

• 哈希表冲突分析
• 负载均衡
• 随机化算法分析

5.6 序列分析

问题：连续抛n次硬币，最长连续正面序列的期望长度是多少？

分析：

• 设L为最长连续正面的长度
• E[L] = Θ(log n)
• 更精确地，E[L] ≈ log₂ n

概率分析：

• 长度为k的特定连续正面序列的概率为1/2^k
• 有n-k+1个可能的起始位置
• 期望出现次数为(n-k+1)/2^k
• 当k ≈ log₂ n时，期望次数约为1

5.7 随机化快速排序

标准快速排序的最坏情况时间复杂度为O(n²)，这发生在输入已经有序而每次选择最后一个元素作为主元时。

随机化版本：

在选择主元时，随机从当前子数组中选择一个元素，而不是固定选择最后一个元素。

RANDOMIZED-PARTITION(A, p, r)
    i = RANDOM(p, r)
    交换A[i]和A[r]
    return PARTITION(A, p, r)

分析：

• 最坏情况仍然可能，但概率极低
• 期望时间复杂度为O(n log n)
• 对任何输入都能保证期望O(n log n)

为什么随机化有效：

随机化消除了输入分布的影响。无论输入是什么样的，算法的期望性能都是O(n log n)。这使得算法不依赖于输入的特定假设。

5.8 随机化选择算法

选择问题（Selection Problem）：在n个元素的无序数组中找到第k小的元素。

RANDOMIZED-SELECT算法：

基于快速排序的分区思想：

随机选择主元并分区

如果主元恰好是第k小的元素，返回

否则，递归地在左半部分或右半部分继续查找

时间复杂度分析：

• 最坏情况：O(n²)（每次都选到最差的主元）
• 期望情况：O(n)

期望分析：

T(n) = 期望分区代价 + 期望递归代价

T(n) ≤ (1/n)Σ(T(max(i, n-i))) + O(n)

可以证明T(n) = O(n)

5.9 最坏情况线性时间的选择算法

BFPRT算法（也称Median of Medians）可以在最坏情况下保证O(n)的选择时间。

算法步骤：

将n个元素分成⌈n/5⌉组，每组5个元素

找出每组的中位数（用插入排序，每组O(1)）

递归调用SELECT找出这些中位数的中位数M

以M为主元进行分区

递归地在合适的子数组中查找

关键分析：

M作为主元时，至少保证3n/10个元素比M小，3n/10个元素比M大。

因此递归调用的最大规模为7n/10。

递归式：T(n) ≤ T(⌈n/5⌉) + T(7n/10) + O(n)

可以证明T(n) = O(n)

5.10 概率分析的应用场景

概率分析在算法分析中有广泛的应用：

哈希表分析：分析冲突概率和查找时间

随机图分析：分析随机图的连通性、直径等性质

随机化舍入：将线性规划的分数解转化为整数解

蒙特卡罗算法：以高概率给出正确答案

拉斯维加斯算法：总是给出正确答案，但运行时间是随机的

重要知识点

知识点1：期望的线性性的强大之处

期望的线性性不要求随机变量独立，这使得它在分析复杂问题时非常有用。例如，分析快速排序的比较次数时，可以为每对元素定义指示器变量，即使这些变量不独立，总期望也等于各指示器期望之和。

知识点2：蒙特卡罗算法与拉斯维加斯算法

• 蒙特卡罗算法：运行时间固定，但结果可能错误（以一定概率）

- 示例：随机化最小割算法

- 特点：快但可能错

• 拉斯维加斯算法：结果总是正确，但运行时间随机

- 示例：随机化快速排序

- 特点：对但时间不确定

知识点3：尾不等式

尾不等式（Tail Inequality）描述随机变量偏离期望值的概率：

• 马尔可夫不等式：P(X ≥ a) ≤ E[X]/a
• 切比雪夫不等式：P(|X - E[X]| ≥ t) ≤ Var[X]/t²
• 切尔诺夫界：对独立随机变量之和的更紧界

知识点4：随机化在密码学中的角色

随机化是现代密码学的基石：

• 密钥生成需要随机性
• 随机化加密方案可以抵抗特定攻击
• 零知识证明需要随机挑战

知识点5：去随机化

去随机化（Derandomization）研究如何将随机算法转化为确定性算法：

• 条件期望法
• 成对独立
• 伪随机数生成器

常见误区

误区1：期望时间等于平均时间

期望时间是概率意义上的平均值，但实际运行时间可能波动很大。一个期望O(n)的算法，实际运行时间可能是O(n²)（只是概率很低）。

误区2：随机算法总是比确定性算法好

随机算法的优势在于：

• 消除对输入分布的依赖
• 简化算法设计
• 有时能获得更好的理论保证

但随机算法也有缺点：

• 需要好的随机数源
• 结果可能不可重现
• 在某些场景下，确定性算法可能更优

误区3：生日悖论不是真正的悖论

生日悖论之所以称为"悖论"，是因为结果违反直觉。23人中有两人生日相同的概率超过50%，这与大多数人的直觉不符。但它不是逻辑矛盾，只是概率的有趣性质。

误区4：BFPRT算法在实践中最快

虽然BFPRT在最坏情况下是O(n)，但由于较大的常数因子，实践中随机化选择算法通常更快。理论最优不等于实践最优。

误区5：概率分析只适用于随机输入

概率分析可以应用于：

• 随机输入上的确定性算法
• 随机输入上的随机算法
• 固定输入上的随机算法
• 对抗输入上的随机算法

实践应用

应用1：哈希表设计

概率分析指导哈希表的设计：

• 表大小选择：负载因子α = n/m，冲突概率约为α
• 开放寻址：查找失败的期望探测次数约为1/(1-α)
• 链地址法：查找的期望时间为O(1 + α)

应用2：负载均衡

随机化是负载均衡的重要策略：

• 随机分配任务到服务器
• 最大负载的期望为O(log n / log log n)
• 比确定性轮询更简单且效果相当

应用3：随机抽样

在大数据场景中，随机抽样是降低计算成本的常用方法：

• 简单随机抽样
• 蓄水池抽样（Reservoir Sampling）：在未知总量的数据流中等概率抽取k个元素
• 加权抽样

应用4：随机化测试

随机化在软件测试中的应用：

• 模糊测试（Fuzzing）：随机生成输入测试程序
• 随机化基准测试：减少缓存效应的影响
• 蒙特卡罗模拟：通过大量随机实验估计系统行为

应用5： randomized algorithms in machine learning

机器学习中的随机化应用：

• 随机梯度下降（SGD）
• Dropout（随机失活）
• 随机森林
• 随机投影降维

5.11 概率分析的深入工具

切尔诺夫界（Chernoff Bound）：

切尔诺夫界提供了独立随机变量之和偏离期望值的指数级衰减概率。

定理（加法形式）：设X = Σ Xᵢ，其中Xᵢ是独立的0-1随机变量，μ = E[X]。则：

• P(X ≥ (1+δ)μ) ≤ (e^δ / (1+δ)^(1+δ))^μ
• P(X ≤ (1-δ)μ) ≤ (e^(-δ²) / 2)^μ

应用：

• 分析随机化算法的失败概率
• 哈希表中冲突次数的尾界
• 随机图的性质分析

马尔可夫不等式和切比雪夫不等式：

马尔可夫不等式：对非负随机变量X，P(X ≥ a) ≤ E[X]/a

切比雪夫不等式：P(|X - E[X]| ≥ t) ≤ Var[X]/t²

这两个不等式是更紧界的基础，在算法分析中广泛使用。

5.12 随机化数据结构的深入分析

随机跳表（Skip List）：

跳表是一种随机化数据结构，提供O(log n)期望时间的查找、插入和删除。

结构：多层链表，第i层包含第i-1层的每个元素以概率p独立存在。

查找：从最高层开始，在当前层向右移动直到下一个节点超过目标，然后下降到下一层。

分析：

• 期望层数：log_(1/p) n
• 查找的期望步数：(1/p)·log_(1/p) n
• 取p = 1/2，期望查找时间为O(log n)

随机化Treap：

Treap结合了BST和堆的性质。每个节点有键值和随机优先级。

• BST性质：键值满足搜索树性质
• 堆性质：优先级满足堆性质

由于优先级是随机的，树的期望高度为O(log n)。插入和删除通过旋转维护两个性质。

5.13 随机化在密码学中的深入应用

随机化加密：

• ElGamal加密：每次加密使用不同的随机数，相同明文产生不同密文
• RSA-OAEP：使用随机填充，保证语义安全性

零知识证明：

证明者可以向验证者证明某个陈述为真，而不泄露任何额外信息。随机挑战是零知识证明的核心。

随机预言机模型：

将哈希函数建模为随机函数，简化密码方案的安全性证明。

5.14 随机化算法的去随机化

条件期望法：

将随机算法转化为确定性算法。逐步固定随机选择，保证条件期望不降低。

成对独立：

使用成对独立的随机变量代替完全独立的随机变量，减少随机位的使用。

伪随机数生成器：

使用短的随机种子生成长的伪随机序列。如果生成器足够好，随机算法使用伪随机数的表现与使用真随机数相似。

本章小结

本章深入介绍了概率分析与随机算法的核心概念和方法。我们学习了：

概率基础：概率空间、条件概率、贝叶斯定理、独立性等基本概念。

期望与指示器随机变量：期望的线性性是概率分析的核心工具，即使随机变量不独立也成立。

经典概率问题：生日悖论（哈希冲突分析）、球与箱子问题（负载均衡分析）、序列分析。

随机化算法：随机化快速排序（期望O(n log n)）、随机化选择（期望O(n)）、BFPRT（最坏O(n)）。

算法分类：蒙特卡罗算法（快但可能错）vs 拉斯维加斯算法（对但时间不确定）。

高级工具：切尔诺夫界、马尔可夫不等式、切比雪夫不等式等概率尾界。

随机化数据结构：跳表、Treap等利用随机化保证期望性能的数据结构。

去随机化：将随机算法转化为确定性算法的技术。

概率分析和随机算法是现代算法理论的重要组成部分。它们不仅提供了分析算法行为的工具，还为我们设计高效、简洁的算法提供了新的思路。

关键术语

思考题

在一个有n个元素的哈希表中，使用链地址法处理冲突。假设简单均匀哈希，证明查找一个不存在元素的期望时间为O(1 + n/m)，其中m为表大小。

设计一个随机算法，在O(n)期望时间内找出数组中出现次数超过n/2的元素（多数元素）。

使用指示器随机变量分析：将n个球随机投入n个箱子中，恰好有一个箱子为空的期望箱子数。

证明：在随机化快速排序中，任何特定元素被比较的期望次数为O(log n)。