COMP5270 Week 4 总结:Derandomisation(题解 + 知识点)

Posted on Edited on In , Word count in article: 9.6k Reading time ≈ 35 mins.

课程: 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?生成均匀随机子集 呢?

题解:

课程 solution 的口径是:从大小为 的 domain 中生成一个均匀随机元素,需要:

个随机 bit。

为什么?

一个独立随机 bit 有 2 种等概率结果(0 或 1),所以 个独立 bit 可以产生 种等概率组合。要覆盖 个不同结果且每个结果概率相等,必须有 ,即 。bit 数必须是整数,所以取上界 。

信息论直觉:均匀分布的熵是 ,而每个独立 bit 最多提供 1 的熵,所以至少需要 个 bit 才能"装下"这个随机性。

举例: - 生成 : bit(刚好 )。 - 生成 : bit(用 ,其余丢弃或重映射即可保持均匀)。

如果 bit 数少于这个值,,不管怎么映射,总会有某些结果被分到的概率更大,就不是均匀随机了。

所以:

而 的子集总数是:

所以生成一个均匀随机子集需要:

个随机 bit。

更直观地说:每个元素都有"选 / 不选"两个选择, 个元素就是 个独立 bit。

知识点总结:

  1. 随机 bit 数量:从大小为 的域中生成一个均匀随机元素,需要 个独立随机 bit。

  2. 随机子集:生成 的均匀随机子集,需要 个随机 bit(每个元素选/不选)。

Problem 2: 两两独立但不完全独立

Tutorial 难度/要求: Warm-up；lecture 前也应该可以尝试并解决。重点是用反例理解 pairwise independence 不等于 mutual independence。

题目: 令 是独立 Bernoulli 随机变量,设:

证明 是均匀随机 bit，并且 两两独立，但不是整体独立。

是什么？ 是 XOR（异或）运算符。两个 bit 做 XOR，结果当且仅当两个 bit 不同时为 1，相同时为 0：
0 0 0
0 1 1
1 0 1
1 1 0

等价于 模 2 加法：。也等价于 （当 时）。

题解:

先看 是否均匀。

当且仅当 :

所以:

是公平 bit。

为什么两两独立?

本来独立。只需要证明 独立, 同理。

对任意 :

当 时, 等价于:

所以:

由于 独立:

而:

所以 独立。

为什么不是整体独立?

因为 完全由 决定:

例如:

但如果三者整体独立,应该有:

两者不相等,所以 不 fully independent。

知识点总结:

  1. XOR 构造: 是构造两两独立随机变量的经典技巧。
  2. 两两独立 vs 整体独立:两两独立(pairwise independent) 整体独立(mutually independent),要验证所有对的联合分布相等,但整体联合分布不等。

  3. 检查方法:检查两两独立只需验证 对所有对成立。

Problem 3: Strongly Universal 推出 Universal

Tutorial 难度/要求: Warm-up；应该 doable，但最好等 lecture 后做；如果提前做，至少先看 lecture notes。重点是直接展开 strongly universal 和 universal hashing 的定义。

题目: 已知 strongly universal hash family 满足:

证明它一定是 universal hash family,即:

题解:

固定 。

事件 可以拆成:

其中 遍历 中所有值。

所以:

由 strongly universal:

因此 strongly universal 一定 universal。

注意:universal 只要求 collision probability 小;strongly universal 要求两个输入的输出值像两个独立均匀随机变量一样。

知识点总结:

  1. Strongly Universal 定义:要求 1 均匀(输出 uniform);2 两两独立(不同输入的哈希值独立)。
  2. Strongly Universal ⇒ Universal:因为碰撞概率被两两独立性严格控制为 。
  3. Universal 更弱:只要求碰撞概率 ,不要求独立性或均匀性。

Problem Solving

Problem 4: 让随机 Max-Cut 以 0.99 概率成功

Tutorial 难度/要求: Problem Solving，标记 ，属于同级别偏难。重点是先用随机 cut 的期望，再通过重复或放大把成功概率推到 0.99。

题目: 给一个随机算法,在输入图 时,运行时间 ,并以至少 的概率输出 cut ,满足:

题解思路:

课堂上只证明了:

这说明:

但"正概率"可能非常小,不足以直接重复固定次数。

所以 tutorial 先证明一个更强的下界:

然后重复随机算法 次,就能把成功概率放大到至少 。

为什么重复能放大成功概率?

假设单次成功概率至少是 。

重复 次都失败的概率最多是:

使用不等式:

得到:

如果取:

那么:

所以至少一次成功的概率大于 。

为什么 ?

令:

对非负整数随机变量用 tail-sum idea:

把求和分成两段:

  1. 的部分,每项最多是 1;
  2. 的部分,每项最多是 。

因为左边等于 ,可以推出:

因此重复:

次即可。

每次生成 cut 需要 ,检查 cut size 需要 ,总时间:

知识点总结:

  1. Max-Cut 期望:随机 Max-Cut 的期望是 ,由 Markov 的反向用法可得 的反面。
  2. 重复放大:重复随机算法 次可将成功概率放大到 。

  3. 两两独立 derandomise:用两两独立哈希族 + 枚举所有种子可以 derandomise,代价是多项式时间而非指数时间。

Problem 5: 构造两两独立哈希族

Tutorial 难度/要求: Problem Solving，标记 ，very difficult 或 time-consuming；官方说不要求必须解出，但建议快速看 solution，抓住主要论证思路。

题目: 证明 lecture 中的 Fact 22.2。简单情况:设:

把 看作非零 -bit string:

对每个 ,定义:

即取 在 中那些位置的 bit,再做 XOR。

令:

证明 是 pairwise independent hash family。

(a) family 大小

的子集有:

个,所以:

因为 ,所以:

这和 lecture 里的:

一致。

(b) 需要多少随机 bit?

随机选一个 等价于选一个 -bit string:

其中:

所以需要:

个随机 bit。

计算时:

也就是先做 bitwise AND,再取 parity。

(c) 为什么 pairwise independent?

要证明:对任意不同的非零 ,任意 :

核心直觉:

  • ,所以至少有一个 bit 位置上两者不同;
  • 随机选 等价于每个位置独立选择是否进入 ;
  • 是若干独立随机 bit 的 XOR;
  • 只要 XOR 中至少包含一个真正随机 bit,它就是均匀随机的。

更具体地,把位置分成三类:

由于 , 和 至少一个非空。不失一般性,假设 非空。

则:

因为 不相交,对应的 XOR 随机变量相互独立。再分 是否为空讨论,可以证明任意 的概率都是 。

这说明 和 像两个独立公平 bit,因此 是 strongly universal。

知识点总结:

  1. 奇偶性构造:用随机子集 的奇偶性 可以构造 pairwise independent 的哈希族。
  2. Strongly Universal 关键:让任意两个不同输入的哈希值像一对独立均匀随机变量。

  3. 随机 bit 数:只需要 个随机 bit 来描述一个 hash 函数。

Problem 6: 随机定向与有向三角形

Tutorial 难度/要求: Problem Solving，未特别标难，属于正常练习题。重点是用随机定向、indicator 和期望线性性计算结构出现的期望数量。

题目: 给无向图 。要给每条边定方向,得到有向图,并最大化 oriented triangle 的数量。

Oriented triangle 指长度为 3 的有向环:

(a) 随机算法

对每条边独立随机选择一个方向。

设 是原图中的无向三角形集合。对每个三角形 ,定义:

一个三角形有 3 条边,每条边有 2 个方向,共:

种方向组合。

其中只有 2 种形成有向环:

或反方向:

所以:

总 oriented triangles 数量是:

由期望线性性:

而最优解不可能超过原图三角形总数:

所以:

这是随机的 -approximation。

(b) Derandomise

有两种方法。

方法 1:3-wise independence + 枚举 seed

分析每个三角形时,只需要三条边的方向彼此独立,所以不需要所有 条边完全独立,只需要 3-wise independence。

要生成 个 3-wise independent bits,只需要:

个真正随机 bit。

然后枚举所有 seed,数量是:

每次检查 oriented triangles 数量最多用 ,所以整体仍是多项式时间。

方法 2:Conditional Expectations

按顺序处理边:

每一步选择当前边方向,使得:

不下降,其中 是最终 oriented triangle 数量。

对当前边 ,只需要考虑包含它的三角形。每个三角形根据已经确定的边数可以分情况:

  • 还没有其他边确定:当前选择后,剩下两条边要配合,期望贡献 ;
  • 已有一条边确定:如果当前方向仍可能形成环,期望贡献 ,否则为 0;
  • 已有两条边确定:如果当前方向刚好完成有向环,贡献 1,否则为 0;
  • 如果已经不可能形成有向环,贡献 0。

分别计算当前边两个方向对应的条件期望,选较大的那个。

最终得到确定性 -approximation。

知识点总结:

  1. 随机定向期望:每条无向边随机定向,期望有向三角形数是 。
  2. 存在性证明:因此存在一种定向使得有向三角形数 。

  3. Conditional Expectation Derandomise:逐个决定每条边的方向,保持期望不下降,最终得到确定性 -approximation。

Problem 7: 少量单色三角形染色

Tutorial 难度/要求: Problem Solving，标记 ；官方说它 “fun” but optional，用来展示 lecture 末尾的 Probabilistic Method。

题目: 证明对每个 ,存在 的一种红蓝边染色,使 monochromatic triangles 数量至多:

并给出多项式时间确定性算法。

题解:

随机给每条边独立染 red 或 blue。

固定一个三角形,它有 3 条边。它是 monochromatic 的情况有两种:

  1. 三条边全 red;
  2. 三条边全 blue。

概率是:

中三角形数量是:

所以期望 monochromatic triangles 数量是:

因此存在某种染色使数量不超过 。

确定性算法可以用和 Problem 6 类似的 derandomisation:

  • 用 3-wise independent hash / seed 枚举;
  • 或者用 conditional expectations,逐条边决定颜色。

知识点总结:

  1. 随机 2-colouring 期望:每条边独立随机染色,期望单色三角形数是 。
  2. 存在性:由期望原理,存在一种边染色使得单色三角形数严格小于 (对大的 )。

  3. Probabilistic Method:证明"存在好解"只需要算随机解的期望。

Advanced

Problem 8: Universal 但非 Strongly Universal 的哈希族

Tutorial 难度/要求: Advanced；官方把它和 Problem 5 一样归为 quite hard，不要求必须解出，但建议快速看 solution，理解 universal 与 strongly universal 的关键差别。

题目: 令 是素数,定义:

其中:

令:

(a) 需要多少 bit 描述函数?

描述一个 只需要描述 ,每个属于 ,所以需要:

bits。

任意函数:

需要为每个输入指定一个输出。输入数量是:

每个输出需要 bits,所以总共:

bits。

(b) 为什么 universal?

要证明对 :

等价于:

因为 ,所以 是非零向量。

设非零向量为 。要证明:

至少存在一个 。固定其他所有 后,方程:

对 有唯一解,因为在 中 可逆。

而 是均匀随机的,所以命中这个唯一解的概率是:

因此 是 universal。

(c) 是否 strongly universal?

不是。

因为:

对所有 都成立。

所以例如要求:

概率是 0,而 strongly universal 要求对任意输出值都有:

的联合概率。

因此它不是 strongly universal。

如果改成 affine form:

并随机选择 ,就可以修复这个问题。

知识点总结:

  1. Universal 定义:只要求碰撞概率 ,不要求输出均匀或独立。
  2. 充分非必要:Strongly universal 是 universal 的充分条件,但不是必要条件。

  3. 存在性构造:存在 universal 但非 strongly universal 的构造,例如固定某些输出的映射。

Part 2: Week 4 知识点

这周在讲什么

Week 4 的核心问题是：随机算法靠抛硬币，能不能不抛硬币也做出一样好的结果？

答案是可以——这就是 derandomisation（去随机化）。

打个比方： - 随机算法像一个赌徒，每碰到一个选择就掷骰子。 - Derandomisation 是把骰子藏起来，用推理代替运气，但最后结果不输给赌徒。

这周讲两种具体方法，都用一个经典问题当例子——Max-Cut。

Max-Cut 问题——看图说话

先搞懂每个字母在说什么

想象一个社交网络：

  • 顶点（Vertex） = 人。一共有 个人。
  • 边（Edge） = 两个人之间有一条连线，表示他们是朋友。一共有 条朋友关系。
  • 图（Graph） = 全部人和全部朋友关系放在一起，记作 ：
    • 是所有人的集合（Vertex set），
    • 是全部朋友关系的集合（Edge set），

一个具体的小例子

假设只有 4 个人，朋友关系长这样：

v₁ ─── v₂
 │      │
v₃ ─── v₄
  • （4 个顶点）
  • （4 条边：v₁–v₂, v₂–v₄, v₄–v₃, v₃–v₁）

问题：把人分成两组，让 跨组的朋友对数 尽量多

把 4 个人分进两组：

  • 组（比如"蓝队"）
  • 组（比如"红队"）

一条边如果一头在蓝队、另一头在红队，就叫做"跨 cut 的边"（cross edge）。

目标：找到一种分组方式 ，让跨组的朋友对数最多。这个对数记作 （ = cut size）。

试着分一下

分组方式 v₁ v₂ v₃ v₄ 跨组边
全放一组 A A A A 全在同组，0 条跨 0
随便分 A A B B v₁–v₃, v₁–v₄, v₂–v₃, v₂–v₄ 4
另一种 A B A B v₁–v₂, v₁–v₄, v₃–v₂, v₃–v₄ 4

在这个 4 人例子里，最好的分法能把全部 4 条边都跨组，所以最优解 。

为什么这个叫 Max-Cut？

把顶点分成 就是在图上"切一刀"（Cut）—— 是一边， 是另一边。让跨切口的边数最多 = Maximum Cut = Max-Cut。

Max-Cut 有多难？

Max-Cut 是 NP-hard 问题——对任意大的图，不存在已知的高效算法总是找到最优解。但 Week 4 要证明：哪怕我们找不到最优解，也能高效找到一个至少是最优解一半好的解。 这就是 -approximation。

随机 Max-Cut 算法——最简单的做法

算法：每人扔一枚硬币

  1. 对每个顶点 ，独立扔一枚公平硬币（正面概率 = 反面概率 = 50%）。
  2. 如果正面 → 放进 组（蓝队）。
  3. 如果反面 → 放进 组（红队）。
  4. 输出分组 。

这个算法有多好？我们来算

关键思路：对每一条边，算它跨 cut 的概率，然后把所有边加起来。

拿一条边 ，连接 和 两个人。定义一个"指示变量" ：

  • ：如果 和 被分到了不同组（这条边跨 cut 了 ✅）
  • ：如果 和 被分到了同一组（没跨 cut ❌）

两个人扔硬币是独立的，所以有 4 种等概率情况：

扔到 扔到 跨 cut 吗？
正面 → A 正面 → A ❌ 都在 A，同组 0
正面 → A 反面 → B ✅ 跨组！ 1
反面 → B 正面 → A ✅ 跨组！ 1
反面 → B 反面 → B ❌ 都在 B，同组 0

4 种情况里 2 种跨 cut，所以每条边跨 cut 的概率 = 。

因此：

读作" 的期望是 "——意思是平均而言，每条边有 的概率跨 cut。

把全部边加起来

总跨 cut 边数 = 所有边的 之和：

是求和符号。因为一共有 条边，每条期望是 ：

读作"随机分组的期望 cut size 是 "。

这算好吗？

最优解 不可能超过全部边数 （一条边一次最多算一次），所以：

随机算法平均输出至少是一半最优解！这叫 1/2-approximation。

通俗总结：随机扔硬币分人，不管你图长什么样，平均跨 cut 的边至少是一半。简单粗暴但好使。

Derandomisation 方法 1：扔掉骰子，穷举所有可能性

核心想法

随机算法的"随机性"来自随机 bit（扔硬币的结果）。如果我们只有很少的几个随机 bit，那可以把所有可能的扔硬币结果都试一遍，选最好的那个——这样就不再需要随机了！

形式化

把算法记作 ： - = 输入（图 ） - = 一串随机 bit（比如 ，每一位对应一个硬币结果）

如果： 1. 随机算法有一定概率输出好结果； 2. 只用了 个随机 bit（ 很小）； 3. 给定结果，能快速判断它好不好；

那就这么做：

尝试所有可能的 r（从 00...0 到 11...1，共 2^R 种）：
    用当前 r 跑算法，得到结果 y
    如果 y 是好的：
        返回 y  ← 找到了！

为什么一定能找到好的？

随机算法有正概率（）输出好结果，说明至少存在某一个 seed 能让它输出好结果。我们枚举所有 ，一定会试到它。

代价是什么？

总共有 种 seed。

（随机 bit 数） 需要尝试的次数 可行吗？
3 ✅ 很轻松
10 ✅ 还行
20 万 ⚠️ 勉强
（=1000） ❌ 宇宙爆炸都算不完

所以关键问题是：Max-Cut 的随机算法到底用了几个随机 bit？

原始算法对每个顶点独立扔硬币， 个顶点 = 个随机 bit。 是致命的——枚举 是不可能的。

Pairwise Independence——我们不需要完全独立！

关键观察

回头看随机 Max-Cut 的证明。对一条边 ，我们只用到：

和 的硬币结果是独立的——即知道 的结果不能推测 的结果。

但我们不需要所有 个顶点之间全部独立！只需要：

任意一对顶点的硬币结果独立。

这就叫 pairwise independence（两两独立）。

完全独立 vs 两两独立

完全独立 两两独立
任意两个独立？ ✅ ✅
任意三个独立？ ✅ ❌ 不一定
需要的随机 bit 很多（ 个） 很少（约 个）

两两独立比完全独立弱很多，但节省了大量随机 bit。而在 Max-Cut 的证明里，两两独立就够用了——因为我们一次只看一条边（两个顶点）。

Strongly Universal Hash Family——一种"够用"的随机函数

等价描述

"两两独立"和"strongly universal hash family"在课程里是同一个概念，只是换了个说法。

通俗理解：有一族函数 （一个"工具箱"），你从里面随机抽一个函数 。这个函数把每个顶点映射到 0 或 1（即决定它去 A 还是 B）：

  • 顶点 1 → = 0 或 1（随机决定）
  • 顶点 2 → = 0 或 1（随机决定）
  • ...

任意两个不同顶点的输出必须像两个独立硬币一样——任何一对 (0,0), (0,1), (1,0), (1,1) 概率各 1/4。

用在 Max-Cut 上

取 （ 个顶点），（A 或 B）。

存在一个 explicit（显式构造的）两两独立 hash family，大小只有：

所以随机选一个 只需要：

个随机 bit！

为什么？ 这是 Problem 1 的结论直接套用：要从 个等概率选项中选一个，需要 个随机 bit。这里 ，所以：

因为 本身就是 2 的幂， 之后正好消掉外面的指数，剩里面 的上取整。

对比：独立 vs 两两独立

原随机算法 用两两独立 hash
随机 bit 数 （每个顶点一个）
枚举 seed 代价 （指数爆炸） （多项式！）
每条边跨 cut 概率 仍为 仍为
最终保证

注意： 和 在数值上几乎一样（差最多 1）。比如 ，，。所以有时候简写为 ，但严谨写法是 。

结论：用两两独立 hash 替换完全独立，随机 bit 从 降到 ，枚举 seed 从不可能变成多项式时间。而且还保证一样好的结果！

为什么"期望 "能推出"存在 "？

这条用了一个简单但极其重要的原则：

一个数不能总低于自己的平均值。

全班考试平均分是 70 分，那一定至少有人考了 分，否则平均分不可能到 70。

在 Max-Cut 里： - 随机分组的 cut size 平均是 。 - 所以一定存在至少一种分组方式，cut size 。

这就是 probabilistic method（概率法） 的核心思想：

要证明"存在一个好对象"，不需要费劲去构造它——只要随机生成，算期望，期望够了就说明至少有一个好的存在。

Derandomisation 方法 2：一步步贪心选

枚举 seed 需要 才可行。如果 更大怎么办？第二种方法不枚举，而是一个一个顶点地贪心决定。

直觉

原始随机 Max-Cut 中每个顶点独立扔硬币。现在我们把这些硬币逐个"锁定"：

  1. 先看顶点 ：如果决定它去 A，对最终 cut size 会有什么影响？去 B 呢？
  2. 选那个让预期 cut size 更高的选项。
  3. 锁定后，再看 ：给定 已经定了，放 A 好还是放 B 好？
  4. 继续，直到所有顶点都定下来。

为什么每一步都不会变差？

假设已经确定了前 个顶点的去向。对下一个顶点 ，只有两种可能——去 A 或去 B：

  • 如果选 A，条件期望 =
  • 如果选 B，条件期望 =

当前的条件期望 = （两个等概率选项的平均）。

两个数的平均值不会超过较大的那个数。

所以只要每次选 和 中较大的那个，条件期望就不会下降。

起点期望是 ，一路不下降，最终锁定所有顶点后（没有随机性了），cut size 仍然 。

具体怎么做：Max-Cut 的贪心规则

当处理顶点 时，之前 已经分好了。 的去向只影响它和已处理顶点之间的边。

  • = " 和已处理顶点之间，如果 去 A 会跨 cut 的边数"
  • = " 和已处理顶点之间，如果 去 B 会跨 cut 的边数"

通俗说： - = 数一下： 的邻居里，已经去了 B 的有几个——如果 去 A，这些边都会跨 cut。 - = 数一下： 的邻居里，已经去了 A 的有几个——如果 去 B，这些边都会跨 cut。

贪心规则：如果 ，放 去 A；否则放 去 B。

一句话：每次让新顶点加入能让"已有边跨 cut"更多的那个组。

回到 4 人例子

v₁ ─── v₂
 │      │
v₃ ─── v₄
步骤 当前顶点 邻居状态 决策
1 v₁ 还没处理任何人 0 0 随便，放 A
2 v₂ v₁ 在 A 如果 v₂ 去 A：0 跨；去 B：v₁–v₂ 跨 0 1
3 v₃ v₁ 在 A，v₂ 在 B 如果 v₃ 去 A：v₃–v₂ 跨 1 1
4 v₄ v₁ 在 A，v₂ 在 B，v₃ 在 A 去 A：v₄–v₂ 跨 1 2

最终分组：A = {v₁, v₃}，B = {v₂, v₄}。跨 cut 边：v₁–v₂, v₁–v₄, v₃–v₂, v₃–v₄ = 4 条 = 最大值！

运行时间：每个顶点数一遍邻居 = 对每个顶点，总共 。

终极总结：不扔任何硬币，按"哪个组让已有边跨 cut 更多就放哪个组"的贪心规则，保证输出 的 cut。这就是 Method of Conditional Expectations 在 Max-Cut 上的具体实现。

Probabilistic Method

Probabilistic method 用来证明"某个对象存在"。

套路是:

  1. 定义一个随机对象 。
  2. 证明它满足某个好性质 的概率大于 0:

  1. 因此一定存在至少一个对象满足性质 。

它不一定给出如何高效找到这个对象,但可以证明存在性。

课堂例子:边 2-colouring 避免 monochromatic set

对完全图 的每条边随机染成 red 或 blue。

固定一个大小为 的点集 。它内部有:

条边。

是 monochromatic 的概率是:

大小为 的点集一共有:

个。用 union bound:

如果:

那么右边小于 1,所以存在一种染色方式没有 monochromatic -set。

核心方法总结

方法 什么时候用 关键句
期望线性性 随机算法的平均质量分析 把总贡献写成 indicator sum
Pairwise independence 证明只依赖任意两个随机 bit 不需要 full independence
k-wise independence 每个局部事件只依赖 个随机选择 用少量 seed 生成足够的局部独立性
枚举 random seed 随机 bit 数 很小,且可验证 good solution 代价是
Conditional expectations 可以高效计算给定部分选择后的期望 每一步选不降低条件期望的分支
Probabilistic method 证明存在性 正概率好对象意味着好对象存在
Union bound 证明坏事件概率小于 1

考试 / 作业写法模板

写随机近似算法

  1. 定义随机算法。
  2. 定义 indicator variable。
  3. 计算每个 indicator 的期望。
  4. 用期望线性性求总期望。
  5. 用 的上界转成 approximation guarantee。

例如 Max-Cut:

写 conditional expectation derandomisation

  1. 说明随机算法的选择序列 。
  2. 定义目标随机变量 。
  3. 说明每一步选:

  1. 说明平均值不超过最大值,所以条件期望不下降。
  2. 最终没有随机性,得到确定性解,且值至少为初始期望。

写 probabilistic method

  1. 随机生成对象。
  2. 定义坏事件或好事件。
  3. 计算固定对象坏的概率。
  4. 用 union bound 控制所有坏事件。
  5. 如果坏事件概率 ,则存在没有坏事件的对象。

Part 3: Week 4 Quiz 回顾

来源：Canvas Quiz / Ed Discussion Quiz 4 截图。每题含中英文题目、正确答案及知识点解析。

Question 1

[EN] We know how to convert every randomised algorithm into a deterministic algorithm with similar running time and guarantees.

[CN] 我们知道如何把每一个随机化算法都转成运行时间和保证类似的确定性算法。

选项 答案
False ✅
True ❌
Only for decision problems ❌

知识点：这个说法太强。课程里只是在特定条件下讨论 derandomisation，例如随机 bit 很少、分析只需要有限独立性、或可以计算条件期望。并不是所有随机化算法都能无条件转成类似保证的确定性算法。

Question 2

[EN] If a (Monte-Carlo) randomised algorithm for a decision problem runs in time and uses random bits, it can be converted into a deterministic algorithm running in time .

[CN] 若一个决策问题的 Monte Carlo 随机化算法运行时间为 ，且只使用 个随机 bit，则可转成运行时间 的确定性算法。

选项 答案
False ❌
True ✅

知识点： 时，随机串总数是 。枚举所有随机串只带来常数倍开销，所以总时间仍为 。对决策问题可以用多数/保证正确的分支来去随机化。

Question 3

[EN] A PNRG outputs truly uniform random bits.

[CN] PNRG 会输出真正均匀随机的 bit。

选项 答案
True ❌
False ✅

知识点：伪随机生成器从短的真随机 seed 生成更长的 bit 串。输出是“对目标算法/测试足够像随机”，不是在所有长 bit 串上真正均匀分布。

Question 4

[EN] The method of conditional expectations consists in replacing random choices by making instead a greedy choice at each stage.

[CN] 条件期望法就是把随机选择替换为每一步做一个贪心选择。

选项 答案
True ✅
False ❌

知识点：每一步固定一个随机选择，并选择使条件期望不下降的分支。因为两个分支的加权平均等于当前条件期望，所以至少有一个分支不差。最终得到确定性解。

Question 5

[EN] If a randomised algorithm uses uniformly random bits but its analysis only relies on pairwise independence, then it can be implemented with uniformly random bits, where is...

[CN] 若随机化算法原本使用 个均匀随机 bit，但分析只依赖两两独立性，则可以用 个均匀随机 bit 实现，其中 为

选项 答案
❌
❌
✅

知识点：两两独立的 个 bit 可由长度为 的真随机 seed 构造出来。核心思想是用小 seed 生成满足分析所需独立性的伪随机对象，而不是生成完全独立的 个 bit。

Question 6

[EN] We know how to derandomise the algorithm for Max-CUT seen in class to solve deterministically the Max-CUT problem in time.

[CN] 我们知道如何把课上 Max-CUT 算法去随机化，从而在 时间内确定性地求解 Max-CUT 问题。

选项 答案
True ❌
False ✅

知识点：课上的 derandomised Max-CUT 算法给出的是确定性的 -approximation，不是 exact Max-CUT。精确 Max-CUT 是 NP-hard，因此不能把“近似保证”误读成“求最优解”。

Question 7

[EN] There exist efficiently constructible strongly universal hash families (pairwise independent hash functions)...

[CN] 存在可以高效构造的 strongly universal hash family（两两独立哈希函数）……

选项 答案
We don't know any efficient construction ❌
Unconditionally ✅
Under cryptographic assumptions only ❌
Under complexity-theoretic assumptions only ❌

知识点：strongly universal / pairwise independent 哈希族有显式高效构造，不需要密码学假设或复杂性理论假设。这也是减少随机 bit 的基本工具之一。

Question 8

[EN] The probabilistic method is a way to algorithmically construct objects with the desired property.

[CN] 概率方法是一种算法式构造满足目标性质对象的方法。

选项 答案
False ✅
True ❌

知识点：概率方法通常证明“存在性”：如果随机对象以正概率满足好性质，那么好对象存在。但它本身不一定给出高效构造算法。若要构造，通常还要结合条件期望法、枚举 seed 等技术。

Question 9

[EN] Computers can easily generate true, independent random bits.

[CN] 计算机可以轻易生成真正独立随机 bit。

选项 答案
True ❌
False ✅

知识点：普通确定性计算机只能从 seed 生成伪随机 bit。真随机性需要外部物理熵源，而且独立性和质量也需要额外保证。

Question 10

[EN] A PNRG is an algorithm/function to generate ____ amounts of ____ randomness based on small ____ random seeds.

[CN] PNRG 是一种算法/函数：基于小的_随机 seed，生成_数量的____随机性。

选项 答案
smaller / good enough / true ❌
larger / true / good enough ❌
larger / good enough / truly ✅
smaller / true / good enough ❌

知识点：伪随机生成器用一个小的 truly random seed，扩展出更大量的 good enough randomness。这里的“good enough”是相对于具体算法或分析而言的。

Week 4 Quiz 速查表

题号 核心概念 正确答案
1 并非所有随机算法都可类似保证去随机化 False
2 常数随机 bit 可枚举 True
3 PNRG 输出不是真均匀随机 False
4 条件期望法 = 逐步贪心固定选择 True
5 两两独立所需 seed 长度
6 Max-CUT 去随机化不是 exact solve False
7 strongly universal hash family 构造 Unconditionally
8 概率方法本身不是构造算法 False
9 计算机不能轻易生成真独立随机 bit False
10 PNRG 扩展 seed larger / good enough / truly

高频混淆点： - Derandomisation 不是万能转换器：只有在额外结构成立时才可行（Q1, Q2, Q5）。 - Max-CUT 课堂算法是 -approximation，不是 exact solver（Q6）。 - 概率方法证明存在，不等于直接算法构造；条件期望法才是常见构造化工具（Q4, Q8）。 - PNRG/PRNG 输出的是 good enough randomness，不是真均匀随机（Q3, Q10）。

Written for COMP5270 S1 2026