COMP5270 Week 1 总结：随机性、概率与算法（题解 + 知识点）

Posted on 2026-05-25 In Course Notes , COMP5270 Word count in article: 5.5k Reading time ≈ 20 mins.

课程: COMP5270 - Randomness, Probability, and Algorithms
学期: S1 2026
来源: Week 1 Lecture Notes + Tutorial 1 Solutions

Part 1: Tutorial 1 详细题解

Problem 1: 同花色连续对的期望数量

题目: 4n 张牌，4 种花色各 n 张。随机洗牌后，相邻同花色对数的期望是多少？

详细题解:

第一题可以用"指示变量 + 期望线性性"完整做出来。

设随机变量

$相邻同花色对的总数。$

牌位有，所以相邻对一共有个：。

对每个，定义

$第张和第张同花色否则$

那么

$。$

由期望线性性：

$。$

现在算（任意都一样）：

先看第张，不管它是什么花色；
剩下张里，和它同花色的还剩张。

所以

$。$

代回去：

$。$

结论：

$。$

补充两个容易错的点：

不是个相邻对，而是个。
不需要假设这些相邻事件独立；期望线性性永远成立。

Problem 2: 连续3个1的run的期望数量

problem-2-consecutive-runs-of-3-ones.png

第二题本质是在数：长度为 2024 的随机比特串里，有多少个位置满足 $第位第位第位$ 。注意这里允许重叠，因为题目给了 1111 有 2 个（位置 1-3 和 2-4）。

设比特串是，每位独立且。

1. 定义指示变量

$。$

为什么是 2022？因为长度为 3 的窗口起点只能到。

2. 总个数写成和

$。$

3. 求每一项期望

$。$

4. 用期望线性性

$。$

结论：

补充：期望可以不是整数；它表示"重复很多次实验后的平均个数"。（这里不需要窗口之间独立，线性性直接成立。）

Problem 3: 排列的固定点期望与方差

题目: 在的均匀随机排列中，定义不动点为满足的位置。设为不动点个数。求和。

1. 定义指示变量

则

$。$

2. 先求期望

对任意，因为排列均匀随机，在上等可能：

$。$

所以

$。$

由期望线性性：

$。$

3. 求方差

$。$

已知，只需算。

4. 展开

$。$

取期望：

$。$

关键在于"交叉项怎么计数"：

有两种等价写法：

按无序对写：（有系数 2）
按有序对写：（无显式 2）

不是，"2"乘的是交叉项，不是平方项。

5. 计算第一项

，所以。因此

$。$

6. 计算第二项

$。$

用条件概率：

$。$

而的有序对个数是，所以

$。$

7. 合并

$。$

结论：

知识点总结

指示变量法：计数问题写成。
期望线性性：，不要求独立。
随机排列对称性：。
平方展开：。
指示变量性质：。
交集概率计算：，不是默认直接相乘。
有序对计数：共个。
方差公式：。

Problem 4: 期望无穷的随机变量

题目: 1. 给出一个定义在上的随机变量，使得。 2. 给出一个定义在上的随机变量，使得。

口诀

都是收敛，发散。

看"收敛/发散"就看极限是不是有限数。

1. 积分的收敛/发散（广义积分）

极限是有限数：收敛
极限是或不存在：发散

2. 级数的收敛/发散

极限有限：收敛
否则发散

常用秒判：

-型积分

收敛
发散

-型级数

收敛
发散（如调和级数发散）

比较法：如果在无穷远处"长得像" ，就按上面判。你那题里：

所以积分发散，。

离散型 vs 连续型随机变量：

离散型：取值可数，用概率质量函数，期望：
连续型：取值在区间上，用密度函数，期望：

一句话：离散型用"求和"，连续型用"积分"。

3步模板（构造）

先选"慢衰减尾巴"
- 连续型常用：（在）
- 离散型常用：
调成合法分布（总概率=1）
- 连续：乘常数让
- 离散：乘常数让
检查期望
- 连续：是否发散（通常变成）
- 离散：是否发散（通常变成）

4. 连续（）

5. 离散（）

Problem 5: 方差公式证明

题目翻译: 证明课上的结论：如果随机变量的方差有限，那么

$。$

解题过程:

设

$。$

由方差定义：

$。$

展开平方：

$。$

两边取期望（用期望线性性）：

$。$

因为，所以

$。$

证毕。

知识点:

方差定义：
代数展开：
期望线性性：，
"方差有限"保证相关期望量是良定义的，推导合法。

Problem 6: 自然数随机变量的期望表示

题目翻译: 证明课上的结论：如果随机变量取值于，且，那么

$。$

解题过程:

对每个样本点，因为是非负整数，有恒等式

$。$

（若，右边前项是 1，后面全是 0，总和就是。）

两边取期望：

$。$

由于求和项非负，可用单调收敛定理（等价地 Tonelli）交换期望与无穷求和：

$。$

即得所证。

知识点:

非负整数随机变量可写成指示变量和：。
指示变量期望：。
单调收敛定理 / Tonelli：非负项时可交换与无穷和。
尾和公式（tail-sum formula）：。
条件保证右侧级数是有限值。

Problem 7: von Neumann 公平硬币技巧

中文翻译:

假设你有一枚有偏硬币，正面概率为，但的值未知。你的目标是：只能使用这枚有偏硬币，生成一次均匀随机的掷硬币结果（即公平硬币结果）。

描述一种实现该目标的策略。
给出一个关于未知参数的界：为了生成一次公平结果，期望需要掷这枚有偏硬币多少次。

解题思路（标准做法：Von Neumann 方法）:

连掷两次硬币。
若结果是 HT，输出 H；若结果是 TH，输出 T。
若结果是 HH 或 TT，丢弃这一轮，重新做第 1 步。

为什么公平：

两者相等，所以在"接受事件" 下，

$输出输出。$

期望掷币次数:

一轮成功概率

$或。$

需要的轮数，

$。$

每轮 2 次掷币，所以

$。$

这个值对该策略是精确值（不只是上界）。并且不存在与无关的统一常数上界（当或时会变大）。

解这题需要知道的知识点:

独立伯努利试验（每次掷币独立）。
条件概率与对称性（）。
拒绝采样思想（HH/TT 丢弃重来）。
几何分布的期望（）。
期望线性放缩（ $总次数每轮次数轮数期望$ ）。

Problem 8: 老鼠与猫的概率问题

题目: 老鼠要从 M 走到 C，图中有若干条路径。每条边独立地以概率被猫占据。求：

(a) 老鼠仍有路径到达奶酪的概率； (b) 老鼠有长度不超过3的路径的概率； (c) 地图上猫的期望数量。

题解:

(a) 有路径的概率:

用补集计算更方便：

$有路径无路径$

老鼠无路径当且仅当三条路径（上、中、下）都被阻断： - 上路有2条边，全被占概率： - 中路有3条边，全被占概率： - 下路有4条边，全被占概率：

$有路径$

验证: - : 概率 = ✅ - : 概率 = ✅

(b) 长度的路径:

只考虑上路（2边）和下路（3边），忽略中路（4边）：

(c) 猫的期望数量:

设为边上是否有猫的指示变量，总边数：

Problem 9: 前缀最大值的期望

题目: 设是个不同数的数组。若是前个元素中最大的，则称为"prefix-maximum"。

(a) 若递增排序，是多少？ (b) 若随机排列得到，证明。

题解:

(a) 递增数组:

每个元素都比前面所有元素大，所以所有个位置都是 prefix-maximum：

（第1个元素也计入，因为它"大于前面空集合的所有元素"）

(b) 随机排列:

设为指示变量（是否为 prefix-maximum）。

对于位置：给定前个元素，其中最大的那个等可能地出现在个位置中的任何一个：

所以：

Problem 10: XOR 的随机变量

题目: 设是独立 Bernoulli() 随机变量，也是 Bernoulli()。

(a) 对，计算前几项并给出通项； (b) 求； (c) 给出递推关系； (d) 求解递推并证明收敛性。

题解:

(a) 特殊情况:

: , 对所有。解释：XOR 公平比特仍得公平比特！
: 对所有（全为0）。
: ，即偶数为0，奇数为1。

(b) 初始值:

（空和为0）
（定义）
（恰好一个为1）

(c) 递推关系:

。当且仅当： - 且，概率 - 且，概率

所以：

(d) 求解与收敛:

技巧: 以为中心（不动点），设：

化简得：

这是等比数列！

所以：

收敛性:

对：，所以，指数收敛到！
对：恒为0
对：不收敛（振荡）

Part 2: 讲义核心知识点

1. 什么是随机化算法？

随机化算法的行为不仅依赖于输入，还依赖于随机比特串 。

等价视角：随机化算法可以看作确定性算法族的概率分布：

运行时先随机选，再运行。

关键分析维度：

输出正确性: 总是正确？还是高概率正确？
运行时间: 总是有界？还是期望有界？高概率有界？

2. 两类随机化算法

🔷 Las Vegas 算法

总是正确（输出100%正确）
运行时间只在期望上有界（worst-case 时间无界）

🔶 Monte Carlo 算法

只在高概率下正确（可能出错）
运行时间总是有界（worst-case 确定）

示例：找偶数

问题: 给定数组包含到的所有数，输出一个偶数的下标。

类型	结论
确定性	最坏情况时间
Las Vegas	期望时间，总是正确
Monte Carlo	最坏情况时间，成功率 99%

Las Vegas 做法：随机选下标，若为奇数则重来。期望次抽到偶数。

3. 四种分析类型总结

分析类型	公式	含义
Worst-case		最坏输入下的表现
Expected		算法随机化时最坏输入的期望时间
Average-case		输入服从某个分布时的期望
Amortized		多次运行时的平均最坏表现

4. 随机化 QuickSort 分析

算法回顾

QuickSort(A):
  if |A| ≤ 1: return A
  随机选 pivot p
  划分 A 为 A₁(<p), A₂(=p), A₃(>p)
  递归排序 A₁ 和 A₃
  合并返回

期望时间复杂度

定理: 随机化 QuickSort 的期望运行时间为。

证明方法 1: 猜测 + 归纳法（设）

证明方法 2: 将递推与微分方程比较

引入原函数后化为：

解得。

比较次数分析（更优雅的证明）

定理: 期望比较次数 = 。

设为排序后的元素，指示和是否被比较过。

总比较次数：

由线性性：

$和被比较$

关键观察: 两个元素被比较，当且仅当它们中第一个被选为 pivot 时，另一个还在同一子数组中。即 pivot 必须是或，且落在到的范围内。

$和被比较$

所以：

其中为第个调和数。

⚠️ 注意：最坏情况时间仍是！

5. 概率论基础工具箱

Fact 1: 自然数随机变量的期望

若取值于：

记忆技巧：令，则，若从开始，所以从开始。

Fact 2: 方差公式

推论: （有时有用）。

Fact 3: 期望的线性性（最核心！）

不需要独立！

推广：

Fact 4: 方差的性质

若独立：
若 两两独立（pairwise independent）：

⚠️ 两两独立比相互独立弱！

Jensen 不等式

若是凸函数：

若是凹函数，不等号反向。

记忆：用（凸函数），，所以。

6. Bernoulli 分布与指示随机变量

Bernoulli 随机变量

，。

（因为 , ）
（最大值在处）

二项分布

：个独立同分布 Bernoulli() 之和。

指示随机变量

对于事件，定义：

$若发生否则$

本质上是参数为的 Bernoulli 随机变量。

7. 使用随机化的原因与局限

✅ 优点

快速找到代表性样本（大数据集采样）
避开病态的最坏情况输入
避免可预测的行为（安全性）
允许更简单或更高效的算法设计

⚠️ 局限

行为是随机的（输出或运行时间不确定）
随机比特从哪来？（实际中靠伪随机数生成器）

Part 3: 符号速查表

一、渐近复杂度符号

1. ：上界（Big-O）

定义：存在正常数和，使得对所有，。记作。

2. ：下界（Big-Omega）

定义：存在正数和，使得对一切都有。记作。

直观：的增长速度"至少"与同阶。

3. ：紧确界（Big-Theta）

定义：存在正常量、和，使得对所有：

同时有上界和下界，记作。

二、概率与统计符号速查

符号	名称	核心含义
	概率	事件发生的可能性，取值
	期望	随机变量的长期平均值
	方差	随机变量围绕期望的波动程度
	服从分布	的概率分布是
	伯努利分布	，
	二项分布	次独立 Bernoulli 之和
	调和数

三、积分与级数收敛速判口诀

: 收敛
: 发散

常用例子： - 调和级数发散 - 收敛（Basel问题） - 发散（对数发散）

核心方法总结

技巧	应用场景
期望的线性性	计数问题、指示变量求和
指示随机变量	将复杂事件分解为简单指示器
补集概率	"至少一个"转为"全都不"
交换求和顺序	双重求和、期望的积分表示
递推关系	序列问题、动态期望计算
中心化处理	找不动点简化递推

核心公式速查

公式	内容
期望线性性	（无需独立）
方差
自然数期望
调和数
Bernoulli 方差
二项分布	,
指示变量

整合自旧笔记 COMP5270.md + 新讲义总结，完成于 2026-05-25