Joey

课程: COMP5270 - Randomness, Probability, and Algorithms
学期: S1 2026
来源: Week 12 - Learning from Experts, Week 12 - Tutorial 12 (Solutions)

---

Part 1: Tutorial 12 详细题解

Warm-up

Problem 1: 画 Theorem 61 / 62 中 的 bound

题目: 对不同 和 ，画 Theorem 61 的 bound 随 的变化；Theorem 62 同理。

题解:

这题主要是数值探索，核心是理解两个 bound 如何依赖 。

Theorem 61 deterministic MWU：

课程: COMP5270 - Randomness, Probability, and Algorithms
学期: S1 2026
来源: Week 11 - Learning and testing probability distributions, Week 11 - Tutorial 11 (Solutions), Lotto CSV data

---

Part 1: Tutorial 11 详细题解

Warm-up

Problem 1: Pearson-Neyman lemma 与 Alice-Bob game

题目: 解释 Pearson-Neyman lemma 如何推出 Alice-Bob game 的 interpretation。

题解:

游戏中 Alice 先抛公平硬币：

• Heads：从 抽样 ；
• Tails：从 抽样 。

Bob 看到 后猜硬币结果。

课程: COMP5270 - Randomness, Probability, and Algorithms
学期: S1 2026
来源: Week 10 - Linear Programming and Randomised Rounding, Week 10 - Tutorial 10 (Solutions)

---

Part 1: Tutorial 10 详细题解

Warm-up

Problem 1: LP 与 ILP 的区别

题目: 回忆 LP 和 ILP 的定义，并总结它们的关键区别。

题解:

LP: Linear Programming

LP 的形式是：在线性约束下优化线性目标函数。

标准形式：