COMP5270 Week 0-12 Cheatsheet

Posted on 2026-05-30 Edited on 2026-10-02 In Course Notes , COMP5270 Word count in article: 7.2k Reading time ≈ 26 mins.

课程: COMP5270 - Randomness, Probability, and Algorithms 学期: S1 2026 用途: 期中/期末快速复习，做题时定位工具

一、Week 0：预备知识与概率基础

1.1 数学工具

工具	公式/结论	用途
Stirling	，	阶乘渐近、组合数估计
组合数		二项式系数定义
调和数	（）	Coupon Collector、快速排序
积分估计		调和数上下界
平方倒数	（Basel）	Coupon Collector 方差
根号倒数		级数求和阶
几何级数	；时无穷和	期望计算、递推
二项式定理		Binomial 分布名来源：
AM-GM		不等式放缩

1.2 渐近符号速查

符号	含义	口诀
	上界	不要超过它
	下界	不会低于它
	紧确界	上下都卡住
	严格上界
	严格下界

常见复杂度：

1.3 概率基础

期望的线性性（最核心！不需要独立）：

指示随机变量：取 1 当事件发生。。

方差：。 - 独立时：（两两独立即可） - 缩放：

自然数随机变量期望（尾和公式）：

Jensen 不等式：凸函数。

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

1.4 四大分布速查表

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

分布关系：

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

Geometric 无记忆性：。

Poisson 标志性特征：期望 = 方差 = 。

Poissonization 魔术：先取，再投个球，则各箱子球数独立。

Bernoulli 分布详解

定义：Bernoulli 随机变量只取两个值：

$概率（成功）概率（失败）$

核心性质：

性质	公式	说明
期望
方差		在时最大，为
矩	（对）	因为，
MGF		直接定义

为什么方差 ≤ 1/4？

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

Bernoulli 是"原子"： - 所有离散分布都可以看成 Bernoulli 的某种组合或推广 - 指示变量就是 Bernoulli：事件发生 → 1，不发生 → 0 - 指示变量法的本质：把一个复杂事件拆成很多 Bernoulli 的求和

例：用 Bernoulli 算期望

空箱问题里， $第个箱子为空$ ，每个。空箱总数：

这就是期望线性性的威力：Bernoulli 不需要独立，求和期望就是期望求和。

二、Week 1：随机化算法入门

2.1 两类算法对比

类型	正确性	运行时间	特点
Las Vegas	总是正确	期望有界，worst-case 无界	可能慢，但绝不出错
Monte Carlo	高概率正确	worst-case 有界	可能出错，但时间可控

示例——找偶数：数组，找偶数下标。 - 确定性：最坏 - Las Vegas：随机选，奇数就重试，期望 - Monte Carlo：随机选一次，成功率，时间

2.2 四种分析类型

类型	公式	含义
Worst-case		最坏输入表现
Expected		最坏输入的期望时间
Average-case		输入服从分布时的期望
Amortized		多次运行的平均最坏

2.3 随机化 QuickSort

期望时间：
期望比较次数：
关键技巧：指示和是否被比较过，

三、Week 2：概率不等式与算法转换

3.1 四大不等式（从弱到强）

不等式	条件	衰减速度	适用场景
Markov			只有一阶矩
Chebyshev			有二阶矩
Hoeffding	独立	指数	有界独立变量和
Chernoff	独立变量和	指数	Bernoulli 和、乘法偏离

Union Bound：（不需要独立！）

标准放缩：（把化成指数）

3.2 算法转换

Las Vegas Monte Carlo（Markov 截断）： - 期望时间的 LV 算法，运行步后截断 - 超时概率，获得时间的 MC 算法

Monte Carlo Las Vegas（错误可检测时）： - 重复运行直到不返回 fail - 若每次失败概率，期望重复次

3.3 Randomised Median（时间，失败概率）

1. 抽样 $m = n^{2/3}$ 个元素（有放回），排序
2. 取 $b = B[m/2 - \Delta]$，$\bar{b} = B[m/2 + \Delta]$，$\Delta = 4\sqrt{m}$
3. 在 A 中收集 $[b, \bar{b}]$ 的元素形成候选集 C
4. 检查 C 大小，排序 C，返回中位数

失败概率：三个坏事件各，Union Bound 得总失败概率。

3.4 概率放大（Amplification）

场景	方法	重复次数	效果
MC 可检测 fail	重复直到成功	—	转成 Las Vegas，期望时间
MC 失败概率	独立重复次，任一成功		失败率降到
Yes/No 黑盒（正确率）	Majority Vote		Chernoff 指数衰减
数值输出（常数概率落在好区间）	Median Trick		中位数高概率准确

Majority Vote：正确率的查询，重复次取多数。Chernoff 给出错误概率，故。

Median Trick：多次运行取中位数，适用于数值输出。

3.5 做题判断模板

看到什么	用什么工具
"至少一个事件发生"	补集 $全都不$ ，或 Union Bound
非负随机变量超过某值	Markov
偏离期望，知道方差	Chebyshev
独立变量的和偏离期望	Chernoff 或 Hoeffding
错误概率从常数降到	重复次
输出可检测 fail	重复直到非 fail，转 Las Vegas
Yes/No 黑盒，正确率	Majority Vote
数值输出，常数概率在好区间	Median Trick

四、Week 3：Balls in Bins

4.1 三大问题对比

问题	设定	结果	核心直觉
碰撞（Birthday Paradox）	球投箱	第一次碰撞：	样本后在大小空间碰撞
覆盖（Coupon Collector）	直到每箱至少 1 球	期望	最后几种"稀有"邮票等得久
负载均衡	球投箱，问最满箱	最大负载	某些箱子运气爆棚
双选择	每球随机看 2 箱，放较空的	最大负载	双指数衰减，指数级改进

记忆口诀：碰撞快（），覆盖慢（），负载居中（量级）。

4.2 碰撞（Collisions）

期望碰撞数（球均匀投箱）：

非均匀分布（分布）： - 均匀时，恢复经典结果 - 均匀分布使碰撞概率最小（ by Cauchy-Schwarz）

阈值：时碰撞概率为常数。

4.3 覆盖（Coupon Collector）

期望：

方差：

分解为几何分布之和： - 阶段（已收集种）：， - 总时间，各 相互独立（memoryless） - 期望：

浓度（Chebyshev）：

** coupon collector 时间高度集中在期望附近**：变异系数。

每箱至少 2 个球：（两阶段：先覆盖，再等第二轮）。

4.4 负载均衡（Load Balancing）

单选择：球投箱，最大负载

上界证明核心：Chernoff + Union Bound - 单个箱子的概率 - 取，使

MGF 替代证明：

4.5 Power of Two Choices

策略：每球随机选 2 箱，放入较空的那个。

结果：最大负载 —— 指数级改进！

直觉——双指数衰减：设 = 至少有个球的箱子比例。则。从出发，。要，需，即。

应用：Hash table（cuckoo hashing）、负载均衡（JSQ-2）、任务调度。

4.6 其他关键公式

空箱期望（球均匀投箱）：

空箱趋于 （）：由泊松近似， $某箱空$ 。

五、Week 4：Derandomisation

5.1 Max-Cut 随机 1/2-Approximation

问题：给无向图，，找 cut 最大化跨边数。

随机算法：每个顶点独立以概率放入，否则放入。

对每条边，设：

因为两个端点独立随机：

所以：

而，因此：

模板句：把目标值写成 indicator 之和，再用期望线性性得到 expected approximation guarantee。

5.2 Derandomisation 方法 1：枚举 Random Seed

把随机算法看成：

其中是随机 bit string。若算法最多用个随机 bit，并且 good solution 可高效验证，则可以枚举：

找到一个 good seed。

运行时间代价：

所以这个方法只有在时才高效。

关键判断：

如果	结论
	枚举，通常太慢
	枚举 polynomially many seeds，可行
good solution 可验证	可以检查并返回
只有期望保证	需要先说明存在好 seed

5.3 期望保证推出存在性

常用事实：

直觉：随机变量不可能总是严格小于自己的期望。

因此 Max-Cut 中：

说明一定存在某个 cut 满足：

这也是 Probabilistic Method 的基本套路：

5.4 Pairwise Independence 与 Strongly Universal Hashing

Max-Cut 分析每条边时只用到两个端点的随机 bit，因此不需要 full independence，只需要 pairwise independence。

Strongly universal hash family：

若对任意和任意：

则像两个独立均匀随机变量。

用法：

取，，随机选，令：

这样不一定完全独立，但任意两个独立，足够分析 Max-Cut。

课程结论：

所以只需：

个真正随机 bit。枚举 seed 的代价：

得到确定性 Max-Cut -approximation，运行时间：

5.5 Universal vs Strongly Universal

概念	条件	强度
Universal		只控制 collision
Strongly universal		输出像独立均匀变量

Strongly universal universal：

注意：反过来不一定成立。

5.6 Method of Conditional Expectations

目标：把随机选择逐个固定，同时保证目标随机变量的条件期望不下降。

每一步选：

为什么可行？

平均值不超过最大值，所以选较大的分支即可。

最终没有随机性：

5.7 Conditional Expectation 用在 Max-Cut

按顺序处理顶点。

处理时，只看它和之前已放置顶点之间的边：

表示把放入时新增跨边数。

贪心规则：

若，放入；
否则放入。

保证：

运行时间：

5.8 Oriented Triangles

给无向图每条边随机定向。固定一个三角形，3 条边共有种方向，其中 2 种形成 directed cycle：

所以：

Derandomise 方法：

用 3-wise independence：每个三角形只依赖 3 条边方向；
或用 conditional expectations：逐条边决定方向。

5.9 Probabilistic Method + Union Bound

证明存在性常用模板：

随机生成对象。
定义坏事件。
计算固定坏事件概率。
对所有坏事件用 union bound。
如果坏事件总概率，则存在没有坏事件的对象。

课堂例子：边随机红蓝染色。固定大小为的点集，它内部有条边。

monochromatic 的概率：

用 union bound：

若右边，则存在一种染色没有 monochromatic -set。

六、Week 5：Graph Algorithms

初学者主线：这一周先看懂两个“安全操作”。Karger 的安全操作是“不要 contract 目标 min-cut 的边”；MST 的安全操作是用 cut/cycle property 判断某些边一定能选或一定能删。遇到概率证明时，先固定一个最优解，再算随机过程保住它的概率。

6.1 Karger Min-Cut

Basic Karger：

当时，均匀随机选边并 contract；
返回最后两个 supervertices 定义的 cut。

固定一个 minimum cut ，大小。若当前还剩个点，且存活：

所以杀掉的概率：

存活概率：

结论：

算法	单次时间	单次成功率	放大后时间
Basic Karger
Karger-Stein

Karger-Stein recurrence：

6.2 Minimum Cuts 数量

每个固定 min-cut 被 Karger 输出概率至少：

输出不同 min-cuts 的事件互斥，总概率不超过 1，所以：

Cycle graph 达到 tight。

6.3 Weighted Karger

加权图中按边权采样：

若 minimum weighted cut weight 为，则每个顶点 weighted degree 至少，所以：

杀掉 fixed min-cut 的概率仍：

6.4 MST Randomised Linear Time

MST 核心性质：

性质	结论
Cut property	任意 cut 上最轻边在 MST 中
Cycle property	任意 cycle 上最重边不在 MST 中
-heavy edge	对 forest ，若加边成 cycle 且该边最重，则不在 MST 中

Karger-Klein-Tarjan building blocks：

Boruvka steps：顶点数缩小倍，时间；
random subsampling：每条边以概率保留；
MSTVerification：线性时间找 -heavy edges；
设，期望时间。

七、Week 6：Hashing and Friends

初学者主线：Hashing 是把大 universe 压到小 table。所有分析都围绕 collision：separate chaining 算期望 bucket size，perfect hashing 算，Bloom filter 算 bit 被置为 1 的概率。记住 Bloom filter 是 one-sided error：不会 false negative，但可能 false positive。

7.1 Universal vs Strongly Universal

Universal hashing：

Strongly universal：

关系：

反过来不一定。

7.2 Hash Table 速查

Load factor：

Separate chaining：

所以：

Worst-case：

Perfect hashing：

第一层大小；
bucket 若有个元素，第二层大小；
lookup worst-case ；
expected total space 。

关键：

7.3 Collision Handling

方法	Lookup	Insert	备注
Chaining	expected	expected	worst-case
Linear probing	依赖 clustering	依赖 clustering	接近满表时变差
Cuckoo hashing	worst-case	expected	插入可能触发 eviction chain
Perfect hashing	worst-case	static/batch	expected space

7.4 Bloom Filter

参数：

bits；
hash functions；
插入个元素；
bits per element。

某 bit 被置为 1：

False positive：

最优 hash 数：

Guarantee：

no false negative；
possible false positive；
simple version 不支持 remove；
counting Bloom filter 可支持 remove，但空间增加。

八、Week 7：Nearest Neighbours, JL, LSH

初学者主线：Nearest Neighbour 难在高维和大数据。JL 负责“降维但保距离”，LSH 负责“让近点更容易撞在一起”。看到 LSH 题，先写 near collision probability 和 far collision probability ，再用 AND/OR amplification 放大差距。

8.1 NN / ANN

Nearest Neighbour：

-Approximate NN：

Baselines：

空间	Query	方法
		线性扫描
		Hamming cube 全 universe array

8.2 Johnson-Lindenstrauss

随机 Gaussian matrix：

Distributional JL：

对固定，保留 norm：

JL for points：

同时保留所有 pairwise distances。

8.3 LSH

-LSH：

Sensitivity：

Amplification：

concatenate hashes：；
repeat tables：提高找到近邻概率。

常用参数：

Baby ANN：

指标	结果
Space
Expected query

8.4 LSH Examples

Hamming：

Euclidean SimHash：

Unit vectors 夹角：

Jaccard / MinHash：

九、Week 8：Streaming and Sketching I

初学者主线：Streaming 的限制是不能保存整个输入，只能维护小 summary。Misra-Gries 用“抵消”找 heavy hitters；Morris counter 用随机概率压缩计数； distinct counting 用 hash sampling 从少量样本反推不同元素总数。

9.1 Streaming Setup

Stream：

Frequency：

目标空间：

最好是 polylog。

9.2 Misra-Gries

参数：

维护最多个 counters。

Guarantee：

Space：

Heavy hitter sandwich 用：

9.3 Morris Counter

存指数，事件来时以概率增加，输出：

性质：

Median-of-means：

个 copies/block 结构。

Careful Morris：

9.4 Distinct Elements

Distinct count：

Tidemark/AMS：

用 trailing zeros；
得 constant-factor estimate；
space 。

Bottom-：

第小 hash value ，估计：

取：

得到常数成功率。

BJKST：

distinct count，空间约：

十、Week 9：Streaming and Sketching II

初学者主线：Sketch 是 frequency vector 的压缩表示。CountSketch 用 random signs 抵消噪声，误差看；CountMinSketch 不用 signs，永远 overestimate，误差看。能否处理负更新，是区分二者的重要考点。

10.1 Sketching

Sketching algorithm：

Linear sketch：

10.2 CountSketch

Update：

Query：

Guarantee：

Space：

Works in turnstile model，且是 linear sketch。

10.3 CountMinSketch

Update 每一行：

Query：

Cash register / strict turnstile guarantee：

Space：

CMS 依赖 nonnegative noise 和 Markov，因此标准 proof 不适合 general turnstile。

10.4 CountSketch vs CountMinSketch

项目	CountSketch	CountMinSketch
Error norm
Bias	unbiased	overestimate
Space in
Model	turnstile	cash register/strict turnstile
Amplification	median	min over rows

同样空间下二者 guarantee incomparable。

十一、Week 10：LP and Randomised Rounding

初学者主线：先把离散问题写成 ILP，再放松成 LP，最后 rounding 回整数解。Maximization 中 LP optimum 是 upper bound，所以只要证明 rounding 的期望至少是，就得到 approximation。

11.1 LP / ILP / Relaxation

LP：

ILP：加整数约束，例如：

LP relaxation：把整数约束放松成：

Maximization：

11.2 Max-SAT

Naive random assignment：

长度 clause 满足概率：

所以 approximation。

Max-SAT ILP/LP：

subject to:

LP rounding：

AM-GM 分析给：

Best-of-two：

结合 naive 和 LP rounding：

11.3 Conditional Expectation Derandomisation

对 randomized rounding / assignment，逐个固定变量。

非均匀 Bernoulli：

选择条件期望更大的分支，最终 deterministic value 至少达到 randomized expectation。

十二、Week 11：Learning and Testing Distributions

初学者主线：Learning 要估计整个分布，样本复杂度通常是；Testing 只判断性质，uniformity testing 可以降到。TV distance 是主距离，collision probability 是 uniformity testing 的核心统计量。

12.1 Total Variation

定义：

Scheffe：

DPI：

Pearson-Neyman：

12.2 Sample Complexities

任务	样本复杂度
Coin bias learning
Distribution learning in TV
Uniformity testing, constant success
Uniformity testing, high probability

12.3 Uniformity Testing

Collision probability：

Uniform：

Distance relation：

Collision statistic：

若太大，拒绝 uniform。

十三、Week 12：Learning from Experts

初学者主线：Experts 问题不追求绝对正确，而是和事后最好的 expert 比。Halving 适合存在完美 expert 的情况；MWU 适合 best expert 也会犯错的情况。所有 MWU 证明都看总权重：上界来自算法犯错导致权重下降，下界来自最好 expert 的剩余权重。

13.1 Experts Setting

Algorithm cost：

Best expert：

目标：让接近。

13.2 Consistent / Halving

若：

算法	Bound
Consistent Expert
Halving

Halving 每次错会删除至少一半 remaining experts。

13.3 MWU

权重更新：

Deterministic weighted majority：

当：

Randomised MWU：

按权重随机抽 expert 跟随。

Potential：

上下界夹住是所有 MWU proof 的核心。

十四、公式大全

6.1 不等式总表

不等式	形式	何时用
Markov		非负，一阶矩
Chebyshev		有二阶矩
Chernoff (上尾)		独立 Bernoulli 和
Chernoff (下尾)		独立 Bernoulli 和
Hoeffding		有界独立变量
Union Bound		多事件联合
Jensen	（凸）	凸函数期望
Cauchy-Schwarz	（）	范数下界
	标准放缩

6.2 分布速查

分布	期望	方差	关键性质
Bernoulli
Geometric			无记忆性
Binomial			个 Bernoulli 之和
Poisson			；稀有事故事件极限

6.3 核心渐近结果

问题	结果
	，



生日悖论阈值
Coupon Collector
最大负载（单选择）
最大负载（双选择）
随机 QuickSort	期望
Randomised Median	时间，失败概率
Max-Cut 随机算法
Max-Cut seed 枚举 derandomisation
Max-Cut conditional expectation
Oriented triangles 随机定向

十五、考试/做题策略

7.1 看到题目先问

是什么类型？ 计数 / 求期望 / 尾概率 / 算法设计 / 复杂度证明
有哪些随机变量？ 指示变量？独立？分布已知？
要什么精度？ 精确值 / 渐近阶 / 高概率界

7.2 工具选择流程

需要尾概率？
  └─ 只有期望 + 非负 ──→ Markov
  └─ 有期望和方差 ────→ Chebyshev
  └─ 独立 Bernoulli 和 ─→ Chernoff（首选！）
  └─ 有界独立变量和 ───→ Hoeffding

需要多个事件联合坏？
  └─ ────→ Union Bound

需要最大值期望？
  └─ ────→ MGF + Jensen: E[max X_i] ≤ (1/t)ln Σ E[e^{tX_i}]

需要算法转换？
  └─ LV → MC ──→ Markov 截断
  └─ MC → LV ──→ 错误可检测时重复
  └─ 降低失败率 ─→ 重复 O(log(1/δ)) 次

需要 derandomise？
  └─ 随机 bit R 很小 + 可验证 ─→ 枚举 seed，代价 2^R
  └─ 分析只用 pairwise/k-wise independence ─→ 用 hash family 降 seed
  └─ 能算条件期望 ─→ Method of Conditional Expectations

看到 Max-Cut / oriented triangles？
  └─ 随机局部分配 ─→ indicator + 线性期望
  └─ 再 derandomise ─→ conditional expectation 或 k-wise independence

7.3 常见陷阱

Chebyshev vs Chernoff：Binomial 和用 Chernoff（指数衰减），不要用 Chebyshev（多项式衰减）
独立性：期望线性性不需要独立，但方差相加需要至少两两独立
Pairwise vs full independence：Max-Cut 只需要边两端 bit 两两独立，不需要所有顶点完全独立
Universal vs strongly universal：universal 只控 collision；strongly universal 才给 pairwise independent outputs
Derandomisation seed 枚举：只有才多项式；会爆炸
Conditional expectation：不是每步最大化当前实际收益，而是最大化“给定当前选择后的未来期望”
几何分布定义：有的教材从 0 开始计数，有的从 1 开始。COMP5270 采用，
Coupon Collector 阶段：是独立的！不要误以为相关
Union Bound 方向：，不是等号

整理自 Week 0-12 讲义与 Tutorial 题解。如有遗漏，回查对应周的详细博客。

一、Week 0：预备知识与概率基础

1.1 数学工具

1.2 渐近符号速查

1.3 概率基础

1.4 四大分布速查表

Bernoulli 分布详解

二、Week 1：随机化算法入门

2.1 两类算法对比

2.2 四种分析类型

2.3 随机化 QuickSort

三、Week 2：概率不等式与算法转换

3.1 四大不等式（从弱到强）

3.2 算法转换

3.3 Randomised Median（ 时间，失败概率 ）

3.4 概率放大（Amplification）

3.5 做题判断模板

四、Week 3：Balls in Bins

4.1 三大问题对比

4.2 碰撞（Collisions）

4.3 覆盖（Coupon Collector）

4.4 负载均衡（Load Balancing）

4.5 Power of Two Choices

4.6 其他关键公式

五、Week 4：Derandomisation

5.1 Max-Cut 随机 1/2-Approximation

5.2 Derandomisation 方法 1：枚举 Random Seed

5.3 期望保证推出存在性

5.4 Pairwise Independence 与 Strongly Universal Hashing

5.5 Universal vs Strongly Universal

5.6 Method of Conditional Expectations

5.7 Conditional Expectation 用在 Max-Cut

5.8 Oriented Triangles

5.9 Probabilistic Method + Union Bound

六、Week 5：Graph Algorithms

6.1 Karger Min-Cut

6.2 Minimum Cuts 数量

6.3 Weighted Karger

6.4 MST Randomised Linear Time

七、Week 6：Hashing and Friends

7.1 Universal vs Strongly Universal

7.2 Hash Table 速查

7.3 Collision Handling

7.4 Bloom Filter

八、Week 7：Nearest Neighbours, JL, LSH

8.1 NN / ANN

8.2 Johnson-Lindenstrauss

8.3 LSH

8.4 LSH Examples

九、Week 8：Streaming and Sketching I

9.1 Streaming Setup

9.2 Misra-Gries

9.3 Morris Counter

9.4 Distinct Elements

十、Week 9：Streaming and Sketching II

10.1 Sketching

10.2 CountSketch

10.3 CountMinSketch

10.4 CountSketch vs CountMinSketch

十一、Week 10：LP and Randomised Rounding

11.1 LP / ILP / Relaxation

11.2 Max-SAT

11.3 Conditional Expectation Derandomisation

十二、Week 11：Learning and Testing Distributions

12.1 Total Variation

12.2 Sample Complexities

12.3 Uniformity Testing

十三、Week 12：Learning from Experts

13.1 Experts Setting

13.2 Consistent / Halving

13.3 MWU

十四、公式大全

6.1 不等式总表

6.2 分布速查

6.3 核心渐近结果

十五、考试/做题策略

7.1 看到题目先问

7.2 工具选择流程

7.3 常见陷阱

3.3 Randomised Median（时间，失败概率）