COMP5270 Assignment 1 中文题解
COMP5270 Assignment 1 中文题解
说明：这是一份中文学习版题解，目标是帮助你理解每道题的思路、知识点和论证过程，后续可再压缩成提交版 LaTeX。
学术诚信提醒：如果你在最终提交中参考了讲义、教材、网页或 LLM，请按老师要求注明来源，并用自己的话重写，不要直接照搬。
Problem 1：随机集合的两个概率
题目概述
从全集 \(\{1,2,\dots,n\}\) 的所有子集中，独立且均匀随机地选出两个集合 \(S\) 和 \(T\)。求：
- \(\Pr[S \subseteq T]\)
- \(\Pr[S \cup T = \{1,2,\dots,n\}]\)
解题思路
这道题最关键的观察是：
- 对每个元素 \(i\) 而言，是否属于 \(S\) 是独立的 Bernoulli\((1/2)\)；
- 是否属于 \(T\) 也是独立的 Bernoulli\((1/2)\)；
- 因此对每个元素 \(i\)，它在 \((S,T)\) 中的状态共有四种，而且等可能： \[ 00,\ 01,\ 10,\ 11. \]
所以问题可以转化为：对每个元素分别看它是否满足条件，再利用元素之间的独立性，把单元素概率乘起来。
涉及知识点
- 均匀随机子集的含义
- 独立性
- 按元素分解事件
- 乘法原理 / 独立事件概率相乘
详细论证
(1) 求 \(\Pr[S \subseteq T]\)
事件 \(S \subseteq T\) 的含义是：如果某个元素在 \(S\) 中，那么它一定也在 \(T\) 中。
对某个固定元素 \(i\)，四种情况分别是：
- \(00\)：不在 \(S\)，也不在 \(T\)
- \(01\)：不在 \(S\)，在 \(T\)
- \(10\)：在 \(S\)，不在 \(T\)
- \(11\)：在 \(S\)，也在 \(T\)
其中唯一会破坏 \(S \subseteq T\) 的情况是： \[ 10. \] 因为这表示 \(i \in S\) 但 \(i \notin T\)。
所以，对单个元素来说，它“满足 \(S \subseteq T\) 要求”的概率是： \[ 1-\frac14 = \frac34. \]
又因为不同元素之间是独立的，所以全部 \(n\) 个元素都满足要求的概率为： \[ \Pr[S \subseteq T] = \left(\frac34\right)^n. \]
(2) 求 \(\Pr[S \cup T = \{1,2,\dots,n\}]\)
事件 \(S \cup T = \{1,2,\dots,n\}\) 的含义是：全集中的每个元素都至少出现在 \(S\) 或 \(T\) 中一次。
对某个固定元素 \(i\)，唯一会破坏这个条件的情况是： \[ 00, \] 即它既不在 \(S\) 中，也不在 \(T\) 中。
因此，对单个元素来说，它满足“属于 \(S \cup T\)”的概率为： \[ 1-\frac14 = \frac34. \]
再由元素独立性可得： \[ \Pr[S \cup T = \{1,2,\dots,n\}] = \left(\frac34\right)^n. \]
结论
\[ \boxed{\Pr[S \subseteq T] = \left(\frac34\right)^n} \]
\[ \boxed{\Pr[S \cup T = \{1,2,\dots,n\}] = \left(\frac34\right)^n} \]
一句话总结
这道题的核心是：把全集中的每个元素单独拿出来分析，找到“坏情况”只有 1 种，因此单元素成功概率都是 \(3/4\)，最后利用独立性得到 \((3/4)^n\)。
Problem 2：极小错误概率是否意味着算法必然正确？
题目概述
算法 \(A\) 在每个输入 \(x\) 上使用 \(r\) 个随机比特，并且输出错误答案的概率至多为 \[ \frac{9}{10}\cdot 2^{-r}. \] 问：算法是否实际上对所有输入都以概率 1 正确？
解题思路
这题的关键不在于概率计算技巧，而在于理解：
- 算法只使用 \(r\) 个随机比特；
- 所以总共只有 \(2^r\) 种可能的随机串；
- 每种随机串出现的概率都是 \(1/2^r\)；
- 因此错误概率一定是某个整数倍的 \(1/2^r\)。
而题目给出的上界却是 \[ \frac{9}{10}\cdot 2^{-r}, \] 这比 \(1\cdot 2^{-r}\) 还小。既然错误概率必须是“以 \(1/2^r\) 为单位”的整数倍，那么它不可能是一个严格介于 \(0\) 和 \(1/2^r\) 之间的值；唯一可能就是 0。
涉及知识点
- 随机算法的样本空间大小
- 离散概率
- 概率是等概率原子事件个数的倍数
- 整数约束
详细论证
固定任意一个输入 \(x\)。
由于算法使用 \(r\) 个随机比特，因此随机性完全由一个长度为 \(r\) 的比特串决定。这样的比特串一共有： \[ 2^r \] 种。
设其中有 \(k\) 个随机串会导致算法在输入 \(x\) 上输出错误答案，那么错误概率就是： \[ \Pr[\text{error on }x] = \frac{k}{2^r}, \] 其中 \(k\) 是一个非负整数。
题目又告诉我们： \[ \frac{k}{2^r} \le \frac{9}{10}\cdot 2^{-r}. \] 两边同乘 \(2^r\)，得到： \[ k \le \frac{9}{10}. \]
但是 \(k\) 是一个非负整数，因此只能是： \[ k=0. \]
这意味着：根本不存在任何随机串会让算法出错。
由于输入 \(x\) 是任意固定的，所以这个结论对所有输入都成立。于是算法在每个输入上都必定输出正确答案，也就是： \[ \Pr[\text{algorithm correct on input }x]=1. \]
结论
\[ \boxed{\text{Yes, the algorithm is correct on every input with probability }1.} \]
一句话总结
因为错误概率必须是 \(1/2^r\) 的整数倍，而题目给的上界却小于最小正倍数 \(1/2^r\)，所以错误概率只能是 0。
Problem 3：最大装载量的期望至少为 4 时，\(m\) 需要多大？
题目概述
把 \(m\) 个球独立且均匀地扔到 \(n\) 个桶里。问：为了让最大装载量（maximum load）的期望至少为 4，\(m\) 至少需要多大？要求用 \(\Omega(\cdot)\) 表示。
先把题目翻成人话
“最大装载量至少为 4” 的意思，其实就是：
开始出现某个桶里有 4 个球。
所以这题本质上是在问：
需要扔多少个球，才会比较明显地出现“4 个球撞进同一个桶”的现象？
这和 birthday paradox 的思路有点像，只不过 birthday paradox 关心的是“2 个撞在一起”，而这里关心的是“4 个撞在一起”。
解题思路
最大值通常不好直接算，所以我们换个角度：
- 如果最大装载量至少为 4，说明至少有一个桶装了 4 个球；
- 那我们不妨先研究：有多少个桶会装到 4 个球？
- 如果这种桶的期望数量已经达到常数量级（比如大约 1 个），那就说明“出现四球桶”已经不是很稀有了；
- 这时最大装载量就会进入 4 这个量级。
所以核心做法是：
- 先看一个固定桶装到 4 个球的概率；
- 再乘上 \(n\)，估计所有桶里这样的桶有多少个；
- 让这个数量达到常数量级，就得到阈值。
涉及知识点
- balls into bins 模型
- 二项分布 / 稀有事件估计
- 期望的线性性
- 阈值分析（threshold phenomenon）
- 渐近记号 \(\Omega, \Theta\)
详细论证
设某个固定桶中的球数为 \(X\)，则 \[ X \sim \mathrm{Bin}\left(m,\frac1n\right). \]
也就是说，每个球都有 \(1/n\) 的概率落进这个桶。
现在我们想知道：这个固定桶装到 4 个球的概率有多大？
先看“恰好装到 4 个球”的概率： \[ \Pr[X=4] = \binom{m}{4}\left(\frac1n\right)^4\left(1-\frac1n\right)^{m-4}. \]
这里要特别区分两个事件：
- \(X=4\)：这个桶恰好收到 4 个球；
- \(X\ge 4\)：这个桶至少收到 4 个球。
上面的公式算的是 \(X=4\)，所以它的含义是：
- 先从 \(m\) 个球里选出 4 个；
- 这 4 个球都进入这个桶，每个概率都是 \(1/n\)；
- 其余 \(m-4\) 个球都不进入这个桶，每个概率都是 \(1-1/n\)。
也就是说，“剩下的球不进这个桶”这句话并不是多余条件，而是因为我们现在算的是恰好 4 个球进入该桶，不是“至少 4 个球进入该桶”。
那为什么这里先算 \(X=4\)，而不是直接算 \(X\ge 4\)？
因为题目只关心量级。直接计算 \(X\ge 4\) 会更麻烦，而 \(X=4\) 已经足够帮助我们判断：什么时候开始出现“四球桶”这个现象。
由于题目只关心渐近量级，所以我们不用纠结常数，只看主导部分。上式的量级是： \[ \Pr[X=4] = \Theta\left(\frac{m^4}{n^4}\right). \]
这表示：
一个固定桶“恰好成为四球桶”的概率，大约由 \(m^4/n^4\) 控制。
接下来考虑全部 \(n\) 个桶。
设 \(Y\) 表示“装到 4 个球的桶”的个数，那么由期望的线性性可得： \[ \mathbb E[Y] = n \cdot \Theta\left(\frac{m^4}{n^4}\right)=\Theta\left(\frac{m^4}{n^3}\right). \]
这一步非常关键，因为它告诉我们：
系统里“四球桶”的总规模，大约由 \(m^4/n^3\) 决定。
现在分两种情况理解：
- 如果 \[ \frac{m^4}{n^3}=o(1), \] 那么四球桶的期望个数趋于 0，说明大多数时候根本不会出现这样的桶；
- 既然连“四球桶”通常都没有，那最大装载量当然还很难达到 4。
所以，想让最大装载量进入 4 这个量级，至少要让“四球桶的期望个数”不再趋于 0，而是达到常数量级，也就是要求： \[ \frac{m^4}{n^3} = \Theta(1). \]
解这个式子： \[ m^4 = \Theta(n^3), \] 因此 \[ m = \Theta(n^{3/4}). \]
题目只要求用 \(\Omega(\cdot)\) 表示必要规模，所以最终答案写成： \[ \boxed{m = \Omega(n^{3/4})}. \]
结论
\[ \boxed{m = \Omega(n^{3/4})} \]
一句话总结
这题的关键是：先不直接算最大值，而是先问“什么时候开始出现某个桶里有 4 个球”。这个现象的阈值正好是 \(m \approx n^{3/4}\)。
Problem 4：星形图上，这个采样算法为什么可能不准？
![[Figure 1 The star graph on n = 10 vertices..png]]
题目概述
这张图是一个星形图 \(G^\star\)：
- 有 1 个中心点；
- 有 \(n-1\) 个叶子点；
- 中心点连着所有叶子点；
- 叶子点之间没有边。
所以：
- 中心点的度数是 \(n-1\)；
- 每个叶子点的度数都是 1。
算法的做法很简单：
- 随机选 \(k\) 个点；
- 看这些点的度数；
- 把这些度数取平均，作为图的平均度数估计值。
题目要你分析：当输入是星形图时，这个算法会发生什么。
先把这题的核心想法讲清楚
这题最关键的地方是：
这张图非常“不平均”。
因为：
- 大部分点都是叶子，度数只有 1；
- 只有一个中心点，度数特别大，是 \(n-1\)。
所以如果你随机抽点：
- 很大概率会抽到叶子；
- 很小概率才会抽到中心点。
这就会导致一个问题：
如果你一直没抽到中心点，你看到的度数几乎全是 1，最后平均出来也会很接近 1。
但真实的平均度数其实不是 1，而是接近 2。
所以这题其实是在说明：
这个算法在星形图上可能会低估真实平均度数。
涉及知识点（白话版）
- 平均度数：所有点的度数加起来，再除以点的总数
- 随机采样：每次随机选一个点
- 独立：每次采样互不影响
- 概率连乘：连续 \(k\) 次都发生同一件事，就把概率乘起来
详细题解
(a) 星形图的平均度数是多少？
先看整张图里所有点的度数总和。
- 1 个中心点，度数是 \(n-1\)
- \(n-1\) 个叶子点，每个度数是 1
所以总度数是： \[ (n-1) + (n-1) = 2(n-1). \]
图里一共有 \(n\) 个点，所以平均度数就是： \[ \bar d(G^\star)=\frac{2(n-1)}{n}=2-\frac{2}{n}. \]
所以答案是： \[ \boxed{\bar d(G^\star)=2-\frac{2}{n}}. \]
(b) 如果抽到的 \(k\) 个点全是叶子，算法输出什么？
如果抽到的全是叶子，那么这些点的度数全都是 1。
也就是说，算法看到的是： \[ 1,1,1,\dots,1. \]
这些数的平均值当然还是 1，所以输出就是： \[ \boxed{\hat d = 1}. \]
(c) 抽到的 \(k\) 个点全是叶子的概率是多少？
图里总共有 \(n\) 个点，其中叶子有 \(n-1\) 个。
所以一次随机抽点，抽到叶子的概率是： \[ \frac{n-1}{n}. \]
如果抽 \(k\) 次，而且每次都独立，那么“每次都抽到叶子”的概率就是： \[ \left(\frac{n-1}{n}\right)^k. \]
所以答案是： \[ \boxed{\left(\frac{n-1}{n}\right)^k}. \]
(d) 为了让算法至少有 99% 的概率够准，\(k\) 要多大？
这一问最容易卡住的地方，是题目里的：
within a factor 1.1
它的意思是：估计值不能和真实值差太多。
如果真实值是 \(d\)，估计值是 \(\hat d\)，那么“within a factor 1.1”表示： \[ \frac{d}{1.1} \le \hat d \le 1.1d. \]
也就是说：
- 估计值不能太小；
- 也不能太大；
- 它必须落在真值附近的一个允许范围内。
现在回到这道题。
真实平均度数是： \[ d = 2-\frac{2}{n}. \] 这个值当 \(n\) 较大时很接近 2。
如果算法抽到的全是叶子，那么算法输出的是： \[ \hat d=1. \]
现在要判断：1 算不算“够接近真实值”？
如果真实值接近 2，那么 factor 1.1 允许的范围大约是： \[ \frac{2}{1.1} \le \hat d \le 1.1\cdot 2, \] 也就是大约 \[ 1.82 \le \hat d \le 2.2. \]
但是算法输出的是 1，而 1 明显比 1.82 还小，所以它不在允许范围内。
这说明：
只要“全抽到叶子”发生，算法这一次就会失败。
因此，如果题目要求算法至少有 99% 的概率成功，那么失败概率最多只能是 1%，也就是 0.01。
而我们在 (c) 中已经算过，“全抽到叶子”的概率是： \[ \left(\frac{n-1}{n}\right)^k. \]
所以必须有： \[ \left(\frac{n-1}{n}\right)^k \le 0.01. \]
接下来题目只要求量级，不要求精确常数，所以我们不必真的解出一个很精细的 \(k\)，只需要判断它大概有多大。
因为 \[ \frac{n-1}{n}=1-\frac1n, \] 所以左边就是 \[ \left(1-\frac1n\right)^k. \]
这种式子要降到一个固定的小常数（例如 0.01），通常需要 \(k\) 和 \(n\) 在同一个量级。直观上说：
- 如果 \(k\) 太小，你几乎一直都在抽叶子；
- 只有当 \(k\) 增长到和 \(n\) 一样大时，你才比较有机会抽到那个唯一的中心点。
所以结论是： \[ k=\Theta(n). \]
题目只要求写 big-Omega，因此最后写成： \[ \boxed{k=\Omega(n)}. \]
结论汇总
(a)
\[ \boxed{\bar d(G^\star)=2-\frac{2}{n}} \]
(b)
\[ \boxed{\hat d=1} \]
(c)
\[ \boxed{\left(\frac{n-1}{n}\right)^k} \]
(d)
\[ \boxed{k=\Omega(n)} \]
一句话总结
这题想说明的是：如果一张图里“重要的点”太少，而你又只是随机抽点，那么你很容易一直抽不到那个关键点，最后算出来的结果就会偏小。
总复习：这份作业考了什么？
这四题背后的核心能力主要是：
- 按元素/按对象分解概率事件
- Problem 1 是典型代表；
- 把复杂集合事件拆成单元素条件，再用独立性乘起来。
- 理解离散随机算法的随机空间
- Problem 2 本质不是复杂概率，而是“错误概率的离散粒度”。
- 掌握 balls-into-bins 的阈值分析思路
- Problem 3 训练的是渐近量级判断，而不是精确常数。
- 识别采样算法在最坏情况输入上的失败模式
- Problem 4 通过 star graph 说明：一个估计算法即使在很多图上好用，也可能在特殊图上失效。
如果后面要转成提交版，我建议你这样做
- 提交版用英文写，更符合课程环境；
- 每题压缩到 4--8 行，不要保留太多解释性语言；
- 保留：
- 关键定义
- 关键概率/推导
- 最终结论
- 不要复制题目，只写：
\solution{1}\solution{2}\solution{3}\solution{4}
- 如果你最终参考了这份笔记来提交，最好再用你自己的英文表达重写一遍。