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

Posted on In , Word count in article: 7.5k Reading time ≈ 27 mins.

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

Part 1: Tutorial 4 详细题解

Warm-up

Problem 1: 需要多少随机 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: 两两独立但不完全独立

题目: 令 是独立 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

题目: 已知 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 概率成功

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

题解思路:

课堂上只证明了:

这说明:

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

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

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

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

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

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

使用不等式:

得到:

如果取:

那么:

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

为什么 ?

令:

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

把求和分成两段:

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

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

因此重复:

次即可。

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

知识点总结:

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

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

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

题目: 证明 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: 随机定向与有向三角形

题目: 给无向图 。要给每条边定方向,得到有向图,并最大化 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: 少量单色三角形染色

题目: 证明对每个 ,存在 的一种红蓝边染色,使 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 的哈希族

题目: 令 是素数,定义:

其中:

令:

(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. 如果坏事件概率 ,则存在没有坏事件的对象。

Written for COMP5270 S1 2026