COMP5270 Week 1 总结：随机性、概率与算法（题解 + 知识点）
课程: COMP5270 - Randomness, Probability, and Algorithms
学期: S1 2026
来源: Week 1 Lecture Notes + Tutorial 1 Solutions
Part 1: Tutorial 1 详细题解
Tutorial 开头的难度/要求说明
Tutorial 1 开头的要求不是按星号分级，而是按“lecture 前能不能做”来分。核心意思是：先尝试很重要，就算证明暂时不够严谨，也可以在 tutorial 里继续打磨。
| 题目 | Tutorial 原文难度/要求 | 复习时怎么安排 |
|---|---|---|
| Problem 1 | 更适合 lecture 后做，或者至少先看 lecture notes | 用来练 indicator random variable 和期望线性性 |
| Problem 2 | 更适合 lecture 后做，或者至少先看 lecture notes | 继续练 run/counting problem 的建模 |
| Problem 3 | 更适合 lecture 后做，或者至少先看 lecture notes | 固定点的期望和方差，注意随机变量之间不独立也能算协方差 |
| Problem 4 | 更适合 lecture 后做，或者至少先看 lecture notes | 理解“期望可以是无穷大” |
| Problem 5 | 更适合 lecture 后做，或者至少先看 lecture notes | 方差恒等式，属于后面分析随机算法的基础工具 |
| Problem 6 | 更适合 lecture 后做，或者至少先看 lecture notes | 自然数随机变量的 tail-sum expectation 公式 |
| Problem 7 | lecture 前也应该可以尝试并解决；第二部分若不直接使用 geometric 期望会比较 technical | 必做，von Neumann trick 是很经典的随机化构造 |
| Problem 8 | lecture 前也应该可以尝试并解决 | 适合先自己想，重点是把条件概率关系列清楚 |
| Problem 9 | 更适合 lecture 后做，或者至少先看 lecture notes | record/prefix maximum 的 indicator 分析 |
| Problem 10 | 更适合 lecture 后做，或者至少先看 lecture notes | 理解 XOR 随机变量和独立性的区别 |
Problem 1: 同花色连续对的期望数量
Tutorial 难度/要求: 更适合 lecture 后做，或者至少先看 lecture notes。重点是把“相邻两张牌同花色”写成 indicator，再用期望线性性求总期望。
题目: 4n 张牌，4 种花色各 n 张。随机洗牌后，相邻同花色对数的期望是多少？