COMP5270 Assignment 1 Feedback-only 中文总结

Posted on 2026-03-24 Edited on 2026-06-02 In Course Notes , COMP5270 Word count in article: 3.6k Reading time ≈ 13 mins.

来源: Assignment 1 (Feedback-only) Solutions.pdf
主题: Longest Increasing Subsequence, uniform random permutation, randomized fingerprinting, communication reduction

这份 feedback-only assignment 有两个独立大题：

Problem 1: 随机排列上的 LIS（Longest Increasing Subsequence），包含 Fisher-Yates shuffle、实验估计和理论证明。
Problem 2: 文件完整性验证，也就是用很短的随机 fingerprint 判断两个 -bit 文件是否相同。

其中 Problem 1 的一部分明确要求 Python 实现和画图，这些实现细节更像作业实践，不像期末证明题的核心。这里按复习目的处理：代码和画图不展开，只保留算法思想、正确性证明和最终结论。

哪些代码部分可以略过

位置	内容	复习时怎么处理
Problem 1(d)	在 Ed 上实现 corrected permutation generator	不写代码，记住 Fisher-Yates 的修正和正确性
Problem 1(e)	对做 100 次实验并画	不写代码，知道实验在估计随机排列的 LIS 平均长度
Problem 1(f)	画 log-log plot，用 numpy 拟合	不写代码，记住 log-log 斜率给，结论约为

期末更值得复习的是：为什么 shuffle 要从里抽、为什么 LIS 的期望是、以及随机 fingerprint 为什么能用很少 bit 检测文件是否相同。

Problem 1: Random Permutation 上的 LIS

1. LIS 是什么

给定一个长度为的数组，一个 increasing subsequence 是一组下标

满足

LIS（Longest Increasing Subsequence）就是最长的 increasing subsequence。注意它是 subsequence，不要求连续。

作业开头给了两个求 LIS 长度的算法：

Dynamic Programming 版本：；
Patience Sorting 版本：。

这部分主要是背景，不是重点证明。

2. 原始 GeneratePermutation 为什么错

原算法的问题在于第 5 行：

也就是说，每一轮都从整个数组里随机选一个位置来交换。循环进行了次，所以不同随机执行路径一共有

条。

如果算法真的能均匀生成所有个排列，那么每个排列应该对应相同数量的执行路径，因此需要

但这一般不成立。例如是素数时，里包含这些因子，而只有因子，不可能整除。

所以原算法不可能均匀生成所有排列。

3. 正确修正：Fisher-Yates shuffle

修正非常小：第轮不应该从所有位置抽，而应该从还没固定的位置里抽：

也就是：

第 1 轮，从中随机选一个元素放到位置 1；
第 2 轮，从中随机选一个元素放到位置 2；
一直继续；
已经固定的前缀之后不再改变。

这样一共有

条等概率执行路径。

4. Corrected algorithm 的正确性

固定任意目标排列

要生成它，算法必须在第轮把放到第个位置。

在第轮之前，前个位置已经固定，一定还在后缀中。这个后缀长度是

所以第轮选中所在位置的概率是

因此生成整个目标排列的概率是

每个排列概率都是，所以生成的是 uniform random permutation。

5. 时间复杂度

如果把“随机生成中的整数”看成操作，那么算法只做一遍数组初始化和一遍交换：

如果随机整数生成本身按 bit complexity 算成，则总时间是

6. 实验结论：LIS 平均长度像

作业让你对随机排列做实验：对每个，生成很多随机排列，计算 LIS 长度，然后估计平均值和标准差。

实验图显示不是线性增长，而更像

取 log 后：

所以在 log-log plot 上，斜率就是，截距是。

官方解答中的拟合结果大约是：

因为实验数据有限，可以合理猜测：

也就是：

最长 decreasing subsequence 的期望和 LIS 相同，因为随机排列在“大小顺序反过来”后分布不变，increasing 和 decreasing 是对称的。

7. 理论结论：

令表示随机排列的 LIS 长度，记

作业用理论证明：

下界：

用到的 Lemma 是 Erdos-Szekeres 型结论：

任意长度为的排列，都包含长度至少为的 increasing subsequence 或 decreasing subsequence。

取

考虑随机排列中前个元素诱导出的相对顺序。它仍然是一个均匀随机排列。

对这个长度为的排列，设是 LIS 长度，是最长 decreasing subsequence 长度。Lemma 给出

又因为

取期望得到

由 increasing/decreasing 对称性，

所以

因此

上界：

如果，说明存在一组大小为的下标，它们对应的值是递增的。

大小为的下标集合有

个。固定一组下标，其对应值的种相对顺序等可能，其中只有 1 种是递增顺序，所以概率是

Union Bound 给出

然后用 tail-sum formula：

前项直接用上界，后面用上面的 union bound：

再用两个常见估计：

于是

选择

则尾和变成一个快速下降的几何级数，得到

结合下界：

这个理论结论和实验里一致。

Problem 1 用到的知识点

LIS / LDS 的定义；
Fisher-Yates shuffle；
uniform random permutation 的正确性证明；
渐近时间复杂度；
log-log plot 的斜率解释；
Erdos-Szekeres lemma；
symmetry between increasing and decreasing subsequences；
union bound；
tail-sum formula；
组合数估计与阶乘下界；
级别分析。

Problem 2: 文件验证与随机 Fingerprinting

1. 问题背景

Carole 有一个 -bit 文件

Dave 下载到了一个 -bit 文件

目标是让 Dave 检查：

$还是$

但 Carole 不想把整个 bit 文件重新发给 Dave。她只想发一个很短的 message。

这就是 randomized fingerprinting：用很短的随机摘要来比较两个大对象。

Part I: Deterministic 不可能，随机化可以

2. deterministic 协议为什么不可能用 bit

如果 Carole 只发送 bit，那么可能的消息数只有

但可能的文件有

个。

因为，由 pigeonhole principle，一定存在两个不同文件，它们产生同一个 message。

Dave 收到同一个 message 时，不可能同时正确区分：

Carole 的文件是；
Carole 的文件是。

所以如果要求对所有都 deterministic 正确，就必须发送本质上 bit 信息。

3. Protocol 1：用 prime modulus 做 fingerprint

把文件看成整数

把看成整数

协议：

Carole 从前个 prime 中均匀随机选一个 prime ；
Carole 发送

给 Dave； 3. Dave 计算； 4. 若

则 Dave 判断相等，否则判断不等。

4. 通信量是

Carole 要发送两部分：

prime ；
residue 。

由 Prime Number Theorem，前个 prime 的大小至多是

因此和都只需要

bit 来表示。

所以总通信量是

5. 正确性

如果，则，所以对任意 prime ，

因此不会误判：

如果，则。官方证明的核心是：

如果有太多不同 prime 让，那么这些 prime 的乘积会整除，最后迫使，矛盾。

更具体地，如果至少个不同 prime 都满足

则这些 prime 的乘积满足

但，而，这会迫使，矛盾。

所以在前个 prime 中，坏 prime 少于一半：

6. 放大到 0.99 成功概率

独立重复次，每次选新的 prime。Dave 只有在所有重复都通过时才判断相等。

若，每次都通过，所以仍然以概率判断相等。

若，每次误通过概率小于，所以次都误通过的概率小于

取

就有

通信量仍然是

7. 为什么不能把 prime 换成普通整数

证明依赖的是：

若且，其中是不同 prime，则可以推出。

如果不是互素的 prime，这个推理会失败。

官方例子中，，取

对，都有

误判概率高达，说明普通整数版本不可靠。

Part II: Common Random Seed 下只发 1 bit

8. Protocol 2：随机内积 mod 2

假设 Carole 和 Dave 共享一个公开随机 seed：

Carole 发送 1 bit：

Dave 计算：

然后比较这两个 bit 是否相等。

通信量：

9. 正确性

如果，那么对任意，

所以

如果，令

则。

比较两个 fingerprint 是否相等，等价于：

这是非空集合上一堆独立均匀 random bits 的 parity。非空 random parity 本身仍然是均匀 random bit，所以为 0 的概率是

因此

10. 放大到 0.99 成功概率

独立重复 7 次，每次用新的随机 seed。Dave 只有在所有 7 次 fingerprint 都相等时才判断。

若，永远通过。

若，误判概率为

所以 Carole 只需要发送

就可以达到至少的检测成功概率。

Part III: 把 common random seed 从 bit 降到 bit

上面的 Protocol 2 通信量很低，但需要一个长度为的公开随机 seed。Part III 证明：可以预先固定一个大小为的 seed 集合，然后只随机选其中一个 seed。

11. 固定一对时的 Chernoff/Hoeffding 分析

对固定，如果用个独立随机 seed，令表示误判相等的次数。由前面结论：

且

Part III 中规则是：如果至少的 runs 都说相等，就输出 equal。

所以错误概率是

Hoeffding 或 Chernoff 都能给出指数下降：

其中是常数。

12. Union Bound 覆盖所有输入对

输入对的数量是

对每一对不同输入，失败概率至多是。用 union bound：

$失败$

只要选

就能让

官方解答说取类似的常数倍就足够。

13. Probabilistic Method 得到固定 seed 集

如果随机选个 seed 时，有正概率对所有输入对都成功，那么一定存在某一组固定 seed

具有这个性质。

之后协议不需要从整个中随机选 seed，只需要从这个固定集合中随机选一个下标

选下标需要的 random bits 是

所以 common random seed 可以从 bit 降到

14. 没有 common random seed 时怎么办

如果没有公共随机 seed，Carole 可以自己随机选下标，并把发送给 Dave。

这会额外花费

bit 通信。

因此最终结论是：

设置	Carole 需要发送多少 bit	随机性
没有 common random seed		Carole 发 seed index
有 common random seed		公共随机性只需 bit

Problem 2 用到的知识点

Pigeonhole principle；
deterministic communication lower bound；
randomized fingerprinting；
prime modulus hashing；
Prime Number Theorem；
modular arithmetic；
Chinese Remainder Theorem 的基本思想；
one-sided error；
probability amplification；
random inner product modulo 2；
parity of random bits；
Chernoff / Hoeffding bound；
union bound；
probabilistic method；
seed reduction / public randomness。

期末复习抓重点

这份 assignment 最值得记的不是代码，而是下面几条证明套路：

Fisher-Yates shuffle：第轮只能从未固定后缀里抽，才能保证每个排列概率。
随机排列 LIS：实验看到，理论用 Erdos-Szekeres 给，用 union bound + tail sum 给。
随机 fingerprint：用很短的随机摘要比较大对象，允许 one-sided error。
放大成功概率：独立重复把错误率压到。
从随机到固定 seed 集：Chernoff/Hoeffding 控制单对输入，union bound 控制所有输入对，再用 probabilistic method 说明存在一组固定 seeds。

代码实现和画图部分可以作为理解辅助，但复习时优先掌握上述理论结构。