COMP5270 Week 0 总结：课程预备知识（算法、离散数学与概率基础）

课程: COMP5270 - Randomness, Probability, and Algorithms
学期: S1 2026
来源: Week 0 — What to know before we start

这篇是课程正式开始前的预备知识回顾，涵盖三大块：经典算法、离散数学常用结论、以及概率论基础。如果有些内容感觉陌生，建议在上课前补一补。

---

1. 算法预备知识

这门课默认你已经熟悉经典算法。如果有需要，推荐两个资源：

• Tim Roughgarden 的 Algorithms Illuminated 系列（有视频和编程作业）
• Jeff Erickson 的 Algorithms（免费 textbook，覆盖面很广）

Big-O 记号

确保你熟悉渐近记号：

这些用来描述算法复杂度：上界、下界、紧确界。Tim Roughgarden 书的第一卷第二章有完整讲解。

两个具体算法

主题	要求	参考位置
Median in Linear Time	能在 时间求中位数	Erickson Ch.1.8 / Roughgarden Vol.1 Ch.6
Max-Flow and Min-Cut	熟悉 Max Flow 和 Min Cut 算法	Erickson Ch.10–11

Median in Linear Time 用到了 median-of-medians 的分治策略，也是练习解递推式（以及 Master Theorem）的好机会。

---

2. 离散数学：需要记住的结论

以下结论不需要全会证明，但要熟悉并能使用。

阶乘与 Stirling 近似

阶乘的增长速度：

更精确的 Stirling 近似：

其中 表示“随 趋于 0 的项”。

由 Stirling 可以推出组合数的渐近行为：

---

调和数

第 个调和数（Harmonic Number）定义为：

前几项：，，，，，。

---

为什么 ？——积分估计法

调和数没有闭式公式，但可以用积分来估计。考虑函数 ，它是递减的。

用矩形法比较：

对于 ，当 时，。因此：

对 到 求和：

即：

整理得：

所以：

更精确的估计：

其中 是欧拉-马歇罗尼常数（Euler-Mascheroni constant）。

---

更紧的上下界

用积分判别法（Integral Test）可以证明：

或等价地：

这说明 与 的差距是一个有界常数（约 0.577），加上一个 的修正项。

---

增长阶

调和数增长速度是对数级的——非常慢。例如： - （一百万）： - （十亿）： - ：（虽然 天文数字，调和数只有 231！）

---

应用：Coupon Collector

调和数在 Coupon Collector 问题中直接出现：

其中 是收集 种邮票所需的期望次数。 是 Coupon Collector 的核心公式。

应用：快速排序比较次数

随机快速排序的期望比较次数也是 。

---

记忆要点： 1. （定义） 2. （近似， 是欧拉常数） 3. （增长阶，最常用） 4. （调和级数发散，但发散速度极慢）

---

常用级数

平方倒数级数（收敛）：

根号倒数级数（发散，但可估阶）：

几何级数：

对 ：

当 时无穷级数收敛：

还有一个进阶结论（求导可得）：

建议自己试着推一遍这个式子，很有价值。

---

AM-GM 不等式

对任意 ：

特别地，二元情形：

---

3. 概率论基础

记号约定

记号	含义
	概率
	期望
	方差
	随机变量 服从分布
	至少为 5 的概率
	额外指定 的分布为

---

概率分布的公理化定义

离散情形：概率分布 可以看作定义在子集上的非负函数，满足：

1. ，（空集概率为 0，全集概率为 1）
2. 对任意可数、两两不交的事件 ：

这就是概率的可数可加性。特别地，若 不交：

对任意（不一定不交）事件：

连续情形：类似，只是把求和换成积分。

---

随机变量

随机变量 由其概率分布 刻画。对任意事件 ：

离散型（ 取有限或可数无限个值）：由概率质量函数（pmf）完全描述：

于是 。

连续型：用累积分布函数（cdf）描述：

如果两个随机变量的 cdf 相同，它们的分布就相同。

---

指示随机变量（Indicator Random Variable）

对事件 ，定义：

例子：设 在 上均匀分布，则

指示变量本质上就是参数为 的 Bernoulli 随机变量，后面会详细讲。

---

独立性

两个随机变量独立：

等价表述：对任意函数 ：

特别地：。

多个随机变量相互独立：

等价地：

---

Bayes 规则与条件概率

对两个事件 （且 ）：

例子： 在 上均匀分布，求“ 是质数，已知 是偶数”：

（因为 2 是唯一的偶质数。）

---

条件期望

对事件 的条件期望（离散情形）：

更一般地，可以定义关于随机变量的条件期望 ：它表示“知道了 之后，对 求平均”。有两个非常重要的性质：

性质 1：全期望公式（Law of Total Expectation）

直观：分步求期望和一步到位结果一样。

性质 2：独立性

若 独立，则知道 对 的期望没有影响：

性质 3：确定性函数

若 （ 完全由 决定），则条件期望“不再平均”：

例子： - - 若 独立：

条件期望在行为上很像普通期望，只是末尾多了“”。

---

4. 常用概率分布（详细版）

这四种分布在 COMP5270 中反复出现。你需要熟悉：它们的定义、直观含义、期望和方差、以及它们之间的关系。

---

4.1 分布之间的关系图

先建立全局认知——四种分布的关系：

Bernoulli(p)  -- n次独立重复 --\>  Binomial(n, p)
       |                          |
       | (p=λ/n, n→∞)            | (n很大, p很小)
       v                          v
  指示变量                    Poisson(λ=np)
       |
       v
  Geometric(p)  -- 等待"第一次成功"

关系总结： - Bernoulli 是最基础的：单次试验，结果 0 或 1。 - Binomial 是 次独立 Bernoulli 的和（统计成功次数）。 - Poisson 是 Binomial 在 但 固定的极限（稀有事故事件）。 - Geometric 是 Bernoulli 序列中等待第一次成功的时间。

---

4.2 Geometric 分布

定义：取值于 ，pmf：

直观：每次试验成功概率 ，独立重复，直到第一次成功为止。 = 需要做的试验次数。

例子： - 掷一枚公平硬币，第一次出现正面的期望次数 = 2 - 每次密码破解尝试成功概率 ，期望尝试 次 - Coupon Collector 中每个阶段等待时间服从几何分布

期望与方差：

期望的推导：

用尾和公式（tail-sum formula）：

关键性质：无记忆性（Memoryless）

直观：已经等了 次还没成功，还要继续等的次数分布和从零开始完全一样——几何分布"忘记"了过去的等待。

为什么这是 Bernoulli 序列的"等待时间"？

因为 意味着前 次都是失败（概率 ），第 次成功（概率 ），所以 。

---

4.3 Poisson 分布

定义：取值于 ，pmf：

直观： 是单位时间/空间内平均发生的事件数。泊松分布描述稀有、独立事件在固定区间内的计数。

例子： - 某客服中心每小时平均接到 4 通电话，实际来电数 ~ Poi(4) - 某放射性物质每秒平均发射 2 个粒子，实际计数 ~ Poi(2) - 一本书平均每页 3 个错字，某页错字数 ~ Poi(3) - Balls in Bins 中，当 很大时，单个箱子里的球数近似 Poi(1)

期望与方差：

关键：期望 = 方差 = 。这是泊松分布的标志性特征，也用来检验数据是否近似泊松。

为什么期望是 ？

与 Binomial 的关系

当 , ，且 固定时，收敛到 ：

这就是 Poisson 的"稀有事故事件"模型： 很大（很多试验）， 很小（每次成功概率低），但 中等（平均成功数固定）。

应用：Poissonization（泊松化）

在 Balls in Bins 中，如果先取 ，再投 个球，则每个箱子的球数 ，且各箱子之间独立。这是 Poissonization 的"魔术"——把依赖的约束（）拿掉后，箱子变得完全独立。Week 3 Tutorial 中 Problem 9 会用到这个技巧。

---

4.4 Bernoulli 分布

定义：取值于 ，pmf：

直观：单次试验，成功（1）概率 ，失败（0）概率 。这是最简单的非平凡随机变量——所有离散分布都可以看作 Bernoulli 的某种组合或推广。

例子： - 掷硬币正面朝上：（正面）， - 某邮件是垃圾邮件：（垃圾）， - 某箱子被某个球击中：（击中）， - 指示变量 ：事件 发生 ，不发生 ，

核心性质：

性质	公式	说明
期望
方差		在 时取最大值
矩	（对 ）	因为 ，
MGF

为什么方差 ？

是开口向下的抛物线，顶点在 ，最大值 。这个性质在 Chernoff 界里经常用到：如果 是独立 Bernoulli 和，方差上界就是 ，简化了很多推导。

信息论直觉

一个 Bernoulli 变量的熵是 bit（最大不确定性）。如果 ，熵小于 ，说明这个 bit 的"信息量"没有充分利用。均匀分布的熵是 ，每个独立 bit 最多提供 的熵，所以生成 个等概率结果至少需要 个 bit——这就是 Problem 1 中 的来源。

与指示随机变量的联系

指示变量 就是参数为 的 Bernoulli 随机变量。所以：

这是 COMP5270 中最常用的期望计算技巧：把计数问题拆成指示变量之和，再求期望。Bernoulli 不需要独立，求和期望就是期望求和。

例：用 Bernoulli 算期望（空箱问题）

，每个 。空箱总数：

与 Binomial 的关系

设 ，则：

---

4.5 Binomial 分布

定义：取值于 ，pmf：

直观： 次独立 Bernoulli 试验，每次成功概率 ，统计成功次数。

为什么叫「二项」分布？—— 二项式定理

二项式定理（Binomial Theorem）：

将 ， 代入，验证 Binomial pmf 是合法的概率分布：

这就是分布「Binomial」名字的来源：它的 pmf 正好是 展开式的各项。 也因此得名二项式系数。

例子： - 掷 次公平硬币，正面次数 ~ Bin(, 1/2) - 投 个球入 个箱子，某个箱子里的球数 ~ Bin(, 1/) - 随机调查 人，支持某政策的比例服从 Binomial

期望与方差：

期望推导（两种方法）：

方法1：直接求和

方法2：拆成 Bernoulli 之和（更优雅）

（因为独立，方差直接相加。）

Chernoff Bound 提示

Binomial 的尾巴衰减是指数级的。对 ，期望 ：

这是 COMP5270 的核心工具——比 Chebyshev 的 多项式衰减强得多。

---

4.6 四种分布对比速查表

分布	取值	pmf	期望	方差	核心场景
Bernoulli					单次试验、指示变量
Geometric					等待第一次成功、Coupon Collector 阶段
Binomial					次独立 Bernoulli 之和、负载计数
Poisson					稀有事件计数、Poissonization

记忆要点： 1. Bernoulli 是基础砖块，Binomial 是砖块堆成的墙 2. Poisson 是"很多小块"（ 大 小）的极限 3. Geometric 是 Bernoulli 序列的"等待时间"，有无记忆性 4. Poisson 的 是标志性特征 5. Binomial 用 Chernoff 做 tail bound，不要用 Chebyshev（太弱）

---

5. 总结检查清单

知识点	是否熟悉	备注
Big-O / /	☐	渐近分析基础
Median in Linear Time	☐	median-of-medians
Max-Flow / Min-Cut	☐	图算法
Stirling 近似	☐	的渐近
调和数	☐
几何级数求和	☐
AM-GM 不等式	☐	均值不等式
概率公理	☐	可加性、规范性
指示随机变量	☐
独立性	☐
Bayes 规则	☐	条件概率
全期望公式	☐
Geometric / Poisson / Bernoulli / Binomial	☐	期望和方差

---

这篇里的内容如果有些不太熟，没关系——课程中遇到时会再解释。但如果大面积感觉陌生，建议提前复习一下，这样上课会更顺畅！