课程: COMP5270 - Randomness, Probability, and Algorithms
学期: S1 2026
来源: Week 2 Lecture Notes + Tutorial 2 Solutions
主题: Markov inequality, Chebyshev inequality, Chernoff bound, Hoeffding bound, probability amplification, Monte Carlo 与 Las Vegas 的转换

---

Part 1: Tutorial 2 详细题解

这一周的 Tutorial 主要围绕一个核心问题：

随机变量通常会不会离它的期望很远？

这类问题叫 concentration bounds，也就是“集中不等式”。它们用来控制坏事件发生的概率，是分析随机化算法的重要工具。

---

Problem 1: Union Bound 与独立事件的精确概率

题目: 假设 是两个独立事件，每个事件发生概率都是 。求至少一个事件发生的概率，并和 union bound 比较。再推广到 个独立事件。

详细题解:

来源: [[5270.md]]（原始文档）
说明: 本文档整理了 COMP5270 全部 Week 的 Quiz 题目及正确答案。Week 4 缺失，Week 12 仅有标题无内容。
用途: 期末复习、知识点快速回顾

---

Week 1: 随机变量与期望基础

Question 1

[EN] If is the indicator variable of an event , then is equal to...

[CN] 若 是事件 的指示变量，则 等于……

• 1
• 0
• ✅
• 1/2

[!note] 知识点 指示变量的期望等于事件发生的概率：。

---

Question 2

课程: COMP5270 - Randomness, Probability, and Algorithms
学期: S1 2026
来源: Week 0 — What to know before we start

这篇是课程正式开始前的预备知识回顾，涵盖三大块：经典算法、离散数学常用结论、以及概率论基础。如果有些内容感觉陌生，建议在上课前补一补。

---

1. 算法预备知识

这门课默认你已经熟悉经典算法。如果有需要，推荐两个资源：

• Tim Roughgarden 的 Algorithms Illuminated 系列（有视频和编程作业）
• Jeff Erickson 的 Algorithms（免费 textbook，覆盖面很广）

Big-O 记号

确保你熟悉渐近记号：

这些用来描述算法复杂度：上界、下界、紧确界。Tim Roughgarden 书的第一卷第二章有完整讲解。