Joey

课程: COMP5270 - Randomness, Probability, and Algorithms 学期: S1 2026 来源: Week 4 - Derandomisation, Week 4 - Tutorial 4 (Solutions)

---

Part 1: Tutorial 4 详细题解

Tutorial 开头的难度/要求说明

Tutorial 4 开头说明了本周每题的投入要求，并解释了星号含义：标记 的题在所属级别内偏难；标记 的题非常难或很耗时。

题目	所属部分	Tutorial 原文难度/要求	复习时怎么安排
Problem 1	Warm-up	lecture 前也应该可以尝试并解决	必做，用来确认随机 bit 数量和 sample space 大小的关系
Problem 2	Warm-up	lecture 前也应该可以尝试并解决	必做，理解 pairwise independence 不等于 mutual independence
Problem 3	Warm-up	应该 doable，但最好等 lecture 后做；否则至少先看 lecture notes	必做，强通用哈希推出通用哈希是定义题
Problem 4	Problem Solving	标记 ，属于同级别偏难	练概率方法 + amplification，建议认真做
Problem 5	Problem Solving	标记 ，quite hard；不要求必须解出，但建议快速看 solution 理解论证主线	难题，有时间再细做；至少看懂构造思路
Problem 6	Problem Solving	未特别标难，属于正常 problem-solving 题	建议做，练随机定向和线性期望
Problem 7	Problem Solving	标记 ；“fun” but optional，用来展示 lecture 末尾的 Probabilistic Method	选做，适合加深概率方法直觉
Problem 8	Advanced	和 Problem 5 类似 quite hard；不要求必须解出，但建议快速看 solution 理解论证主线	高级难题，重点理解 universal 与 strongly universal 的差别

Warm-up

Problem 1: 需要多少随机 bit?

Tutorial 难度/要求: Warm-up；lecture 前也应该可以尝试并解决。重点是把“均匀生成 个可能结果之一”转成需要覆盖 sample space 的 bit 数。

题目: 生成 中的均匀随机整数,需要多少独立随机 bit?生成均匀随机子集 呢?

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

---

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

1.1 数学工具

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

1.2 渐近符号速查

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

常见复杂度：

1.3 概率基础

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

课程: COMP5270 - Randomness, Probability, and Algorithms
学期: S1 2026
来源: Week 3 Lecture Notes (Balls in Bins) + Tutorial 3 Solutions
主题: Collisions (Birthday Paradox), Coverage (Coupon Collector), Load Balancing, Power of Two Choices

---

Part 1: Tutorial 3 详细题解

这一周的 Tutorial 围绕一个核心模型：

把 个球随机均匀独立地投入 个箱子。然后问：会不会发生碰撞？多少箱子是空的？最满的箱子多满？要投多少球才能让每个箱子都至少有 1 个？

这套模型出现在 hashing、负载均衡、coupon collector、生日悖论、distributed systems 中。本周的工具箱：指示变量 + 期望线性性 + Markov / Chebyshev / Chernoff / Union Bound + MGF 技巧。

---

Tutorial 开头的难度/要求说明

Tutorial 3 开头把题目分成了几类：前几题检查你是否理解 balls-and-bins 和 coupon collector；中间几题更 technical；后面 Advanced 题比较重，尤其 Problem 9 的计算量很大。

题目	Tutorial 原文难度/要求	复习时怎么安排
Problem 1	读 lecture notes 或看 lecture 后用于检查理解	必做，掌握空箱期望和基本下界直觉
Problem 2	读 lecture notes 或看 lecture 后用于检查理解	必做，coupon collector 的核心题
Problem 3	读 lecture notes 或看 lecture 后用于检查理解	必做或至少读懂，理解“每个箱子至少 2 个球”的等待时间
Problem 4	more technical，但 good practice	练 Chernoff + Union Bound 的标准组合
Problem 5	more technical，但 good practice	练非均匀分布下碰撞概率的计算
Problem 6	设计为 tutorial 中完成；可以提前看，但不要求自己独立解出	课前先看思路，课上重点跟住 power of two choices 的直觉
Problem 7	conceptually interesting，simple in hindsight 但不 obvious；当 puzzle 想，做不出也没关系，但要看 solution	适合当思维题，重点是理解 的来源
Problem 8	lecture 思想的 real-world application；应该可以自己解决	必做，彩票题能帮助把概率模型放回真实场景
Problem 9	Advanced，quite involved，尤其数学计算很 heavy；标记为	有时间再做，至少读懂 Poissonization 的目的
Problem 10	Advanced，quite involved；但结果在理论计算机、机器学习、数学中很有用	建议认真读，MGF 控制最大值是很通用的技巧