COMP5270 Assignment 1 中文题解
来源: Assignment 1 (Marked) Solutions.pdf
主题: random subsets, randomized algorithms, balls into bins, empirical average via vertex sampling
这份作业是 short-answer assignment，官方答案本身很短。下面保留必要推导，把每一步为什么成立写清楚，但删掉和题解无关的复习建议、提交建议和重复铺垫。
Problem 1: 随机集合的两个概率
题目
从全集
\[ U=\{1,2,\dots,n\} \]
的所有 \(2^n\) 个子集中，独立且均匀随机地选择两个集合 \(S\) 和 \(T\)。求：
- \(\Pr[S\subseteq T]\)；
- \(\Pr[S\cup T=U]\)。
题解
均匀随机选择一个子集的意思是：对每个元素 \(i\in U\)，它是否进入该集合可以看成一次独立的 Bernoulli\((1/2)\) 选择。
因为 \(S\) 和 \(T\) 是独立选出的，所以对固定元素 \(i\)，它在 \((S,T)\) 中的状态一共有四种，并且等概率：
| 状态 | 含义 | 概率 |
|---|---|---|
| \(00\) | \(i\notin S,\ i\notin T\) | \(1/4\) |
| \(01\) | \(i\notin S,\ i\in T\) | \(1/4\) |
| \(10\) | \(i\in S,\ i\notin T\) | \(1/4\) |
| \(11\) | \(i\in S,\ i\in T\) | \(1/4\) |
(a) 计算 \(\Pr[S\subseteq T]\)
\(S\subseteq T\) 的意思是：
只要某个元素在 \(S\) 里，它就必须也在 \(T\) 里。
对一个固定元素 \(i\) 来说，唯一会破坏 \(S\subseteq T\) 的状态是
\[ 10, \]
也就是 \(i\in S\) 但 \(i\notin T\)。
因此单个元素不破坏条件的概率是
\[ 1-\frac14=\frac34. \]
不同元素之间的选择相互独立，所以 \(n\) 个元素全部不破坏条件的概率是
\[ \Pr[S\subseteq T] =\left(\frac34\right)^n. \]
(b) 计算 \(\Pr[S\cup T=U]\)
\(S\cup T=U\) 的意思是：
每个元素至少出现在 \(S\) 或 \(T\) 中的一个集合里。
对固定元素 \(i\) 来说，唯一会破坏这个条件的状态是
\[ 00, \]
也就是 \(i\notin S\) 且 \(i\notin T\)。
因此单个元素满足 union 条件的概率也是
\[ 1-\frac14=\frac34. \]
同样由元素之间的独立性，
\[ \Pr[S\cup T=U] =\left(\frac34\right)^n. \]
结论
\[ \boxed{\Pr[S\subseteq T]=\left(\frac34\right)^n} \]
\[ \boxed{\Pr[S\cup T=U]=\left(\frac34\right)^n} \]
本题用到的知识点
- 均匀随机子集：每个元素独立地以概率 \(1/2\) 被选入集合。
- 独立性：\(S\) 和 \(T\) 独立，且不同元素的选择也可以逐元素相乘。
- 按元素分解事件：把集合事件拆成每个元素的局部状态。
- 补集思想：先找唯一的坏状态，再用 \(1-\Pr[\text{bad}]\)。
- 乘法原理：\(n\) 个独立元素都满足条件时，概率为单元素概率的 \(n\) 次方。
Problem 2: 极小错误概率是否意味着算法必然正确
题目
算法 \(A\) 对每个输入 \(x\) 使用 \(r\) 个随机 bit。若它输出错误答案的概率至多为
\[ \frac{9}{10}\cdot 2^{-r}, \]
问：算法是否在所有输入上都以概率 \(1\) 正确？
题解
答案是 是的。
固定任意输入 \(x\)。算法只使用 \(r\) 个随机 bit，所以它的随机性完全由长度为 \(r\) 的 bit string 决定。
长度为 \(r\) 的 bit string 一共有
\[ 2^r \]
种，并且每一种出现的概率都是
\[ 2^{-r}. \]
设在输入 \(x\) 上，会导致错误输出的随机串数量为 \(b_x\)。因为 \(b_x\) 是随机串的个数，所以它必须是非负整数。
算法在输入 \(x\) 上的错误概率就是
\[ \Pr[\text{error on }x] =\frac{b_x}{2^r}. \]
题目给出
\[ \frac{b_x}{2^r} \le \frac{9}{10}\cdot 2^{-r}. \]
两边同时乘以 \(2^r\)，得到
\[ b_x\le \frac{9}{10}. \]
但 \(b_x\) 是非负整数，所以只能是
\[ b_x=0. \]
这说明：在这个固定输入 \(x\) 上，没有任何随机串会让算法输出错误答案。
由于 \(x\) 是任意输入，所以这个结论对所有输入都成立。因此算法在所有输入上都以概率 \(1\) 正确。
结论
\[ \boxed{\text{Yes. The algorithm is correct on every input with probability }1.} \]
本题用到的知识点
- 随机 bit 的样本空间大小：\(r\) 个随机 bit 对应 \(2^r\) 个等概率随机串。
- 离散概率粒度：错误概率必须是 \(2^{-r}\) 的整数倍。
- 整数约束：若非负整数 \(b_x\le 0.9\)，则 \(b_x=0\)。
- 固定输入分析：先固定任意 \(x\)，证明该输入上永不出错，再推广到所有输入。
Problem 3: 最大装载量期望至少为 4 时，\(m\) 需要多大
题目
把 \(m\) 个球独立且均匀地扔进 \(n\) 个箱子。问：为了让 expected maximum load 至少为 \(4\)，\(m\) 在 \(\Omega(\cdot)\) 记号下至少需要多大？
官方答案是：
\[ m=\Omega(n^{3/4}). \]
下面解释这个量级为什么是 \(n^{3/4}\)。
题解
令 \(L\) 表示最大装载量：
\[ L=\max_{1\le j\le n}\{\text{第 }j\text{ 个箱子里的球数}\}. \]
若 \(L\ge 4\)，说明至少有一个箱子收到了至少 \(4\) 个球。为了估计这个现象什么时候开始出现，可以先看“四个指定球落进同一个箱子”的概率。
任取 \(4\) 个球。第一个球落到哪里不重要；之后另外 \(3\) 个球都必须落到第一个球所在的同一个箱子。每个球命中该箱子的概率是 \(1/n\)，所以这 \(4\) 个球同箱的概率是
\[ \frac{1}{n^3}. \]
从 \(m\) 个球中选出 \(4\) 个球有
\[ \binom{m}{4} \]
种选择。因此“四球同箱组”的期望数量大约是
\[ \binom{m}{4}\frac{1}{n^3} =\Theta\left(\frac{m^4}{n^3}\right). \]
如果
\[ \frac{m^4}{n^3}=o(1), \]
那么四球同箱现象的期望数量趋于 \(0\)。更严格地说，对任意 \(t\ge4\)，
\[ \Pr[L\ge t] \le n\binom{m}{t}\left(\frac1n\right)^t =O\left(\frac{m^t}{n^{t-1}}\right), \]
因为可以先选一个箱子，再选 \(t\) 个球要求它们全部落入该箱子。于是
\[ \mathbb E[L] =\sum_{t\ge1}\Pr[L\ge t] \le 3+\sum_{t\ge4}O\left(\frac{m^t}{n^{t-1}}\right). \]
当 \(m=o(n^{3/4})\) 时，右侧从 \(t=4\) 开始的尾和是 \(o(1)\)，所以
\[ \mathbb E[L]\le 3+o(1), \]
不可能达到至少 \(4\)。
因此，要让最大装载量的期望达到 \(4\)，至少需要让四球碰撞数量达到常数量级：
\[ \frac{m^4}{n^3}=\Omega(1). \]
解这个不等式：
\[ m^4=\Omega(n^3), \]
所以
\[ m=\Omega(n^{3/4}). \]
也可以把它理解成 birthday paradox 的高阶版本：
- 2 个球撞进同一个箱子的阈值是 \(n^{1/2}\)；
- 3 个球撞进同一个箱子的阈值是 \(n^{2/3}\)；
- 4 个球撞进同一个箱子的阈值是 \(n^{3/4}\)。
结论
\[ \boxed{m=\Omega(n^{3/4})} \]
本题用到的知识点
- Balls into bins 模型：\(m\) 个球独立均匀投进 \(n\) 个箱子。
- Maximum load：最大装载量至少为 \(4\) 等价于出现某个箱子有至少 \(4\) 个球。
- 高阶碰撞计数：用 \(4\) 个球同箱的期望数量判断阈值。
- 期望线性性：把所有 \(4\)-tuple 的碰撞 indicator 加起来。
- 渐近记号：由 \(\frac{m^4}{n^3}=\Omega(1)\) 推出 \(m=\Omega(n^{3/4})\)。
Problem 4: 星形图上的平均度采样算法
题目
令 \(G^\star\) 是 \(n\) 个顶点的 star graph：
- 一个中心点连接所有其他 \(n-1\) 个点；
- 其他 \(n-1\) 个点是 leaves；
- leaves 之间没有边。
算法做的是 vertex sampling：
- 均匀随机抽取 \(k\) 个顶点 \(v_1,\dots,v_k\)；
- 查询这些顶点的度数 \(d_{v_1},\dots,d_{v_k}\)；
- 输出经验平均值
\[ \hat d=\frac1k\sum_{i=1}^k d_{v_i}. \]
题目要求分析该算法在 star graph 上的行为。
(a) 星形图的平均度数
Star graph 有
\[ m=n-1 \]
条边。由 Handshaking Lemma，所有顶点度数之和是
\[ 2m=2(n-1). \]
因此平均度数是
\[ \bar d(G^\star) =\frac{2(n-1)}{n} =2-\frac2n. \]
所以
\[ \boxed{\bar d(G^\star)=2-\frac2n}. \]
(b) 如果抽到的 \(k\) 个顶点全是 leaves，算法输出什么
每个 leaf 的度数都是 \(1\)。
如果 \(k\) 次抽样全部抽到 leaves，那么算法看到的度数序列是
\[ 1,1,\dots,1. \]
因此经验平均值是
\[ \hat d =\frac1k\sum_{i=1}^k 1 =1. \]
所以
\[ \boxed{\hat d=1}. \]
(c) \(k\) 次抽样全部抽到 leaves 的概率
Star graph 一共有 \(n\) 个顶点，其中 \(n-1\) 个是 leaves。
一次均匀随机顶点查询抽到 leaf 的概率是
\[ \frac{n-1}{n} =1-\frac1n. \]
\(k\) 次抽样相互独立，所以全部抽到 leaves 的概率是
\[ \left(\frac{n-1}{n}\right)^k =\left(1-\frac1n\right)^k. \]
所以
\[ \boxed{\Pr[\text{all }k\text{ samples are leaves}] =\left(1-\frac1n\right)^k}. \]
(d) 为了以至少 99% 概率得到 1.1 倍以内估计，\(k\) 需要多大
真实平均度数是
\[ \bar d(G^\star)=2-\frac2n. \]
当 \(n\ge 3\) 时，
\[ 1 < \frac{2-\frac2n}{1.1}. \]
所以如果算法输出 \(\hat d=1\)，它就低于真实平均度数的 \(1/1.1\) 倍，不是 within a factor \(1.1\) 的好估计。
也就是说，只要 \(k\) 次抽样全部抽到 leaves，算法就会失败。
由 (c)，这个失败事件的概率是
\[ \left(1-\frac1n\right)^k. \]
要让算法在每个图上都以至少 \(99\%\) 的概率成功，在 star graph 这个输入上也必须成功。因此失败概率至少要被压到常数 \(0.01\) 以下：
\[ \left(1-\frac1n\right)^k\le 0.01. \]
这个不等式说明 \(k\) 必须和 \(n\) 同阶。更具体地，用近似
\[ \left(1-\frac1n\right)^k\approx e^{-k/n}, \]
若要 \(e^{-k/n}\le 0.01\)，就需要
\[ k\ge n\ln 100. \]
因此在 big-Omega 记号下，
\[ k=\Omega(n). \]
官方答案也可以用 Bernoulli inequality 表达同样的必要性：
\[ \left(1-\frac1n\right)^k \ge 1-\frac{k}{n}. \]
如果 \(k=o(n)\)，那么 \(1-k/n\to 1\)，算法会以很高概率只看到 leaves，从而输出错误的估计。
结论
\[ \boxed{\bar d(G^\star)=2-\frac2n} \]
\[ \boxed{\hat d=1\text{ if all sampled vertices are leaves}} \]
\[ \boxed{\Pr[\text{all sampled vertices are leaves}] =\left(1-\frac1n\right)^k} \]
\[ \boxed{k=\Omega(n)} \]
本题用到的知识点
- Star graph 结构：中心点度数 \(n-1\)，每个 leaf 度数 \(1\)。
- Handshaking Lemma：\(\sum_v d_v=2|E|\)。
- 平均度数：\(\bar d(G)=2|E|/|V|\)。
- 独立重复采样：\(k\) 次都抽到 leaf 的概率是单次概率的 \(k\) 次方。
- 近似公式：\((1-1/n)^k\approx e^{-k/n}\)。
- 最坏情况输入分析：为了保证 “on every graph” 成功，star graph 这种反例也必须满足成功概率要求。