Math

Introduction 条件概率指一个事件在另一个事件发生的条件下发生的概率，用记号 $ \mathbb{P}(A|B) $ 表示，仅在 $ \mathbb{P}(B)>0 $ 时有定义： $$ \mathbb{P}(A|B) = \dfrac{\mathbb{P}(A \cap B)}{P(B)} $$ 可以写成 $$ \mathbb{P}(A \cap B) = \mathbb{P}(B)\cdot \mathbb{P}(A|B) $$ 对于 $ n $ 个事件，连续使用上式，即可得到 $$ \mathbb{P}\left( \bigcap_{i=1}^{n}A_{i} \right) = \prod_{k=1}^{n} \mathbb{P}\left( A_{k}\bigg|\bigcap_{i=1}^{k-1}A_{i} \right) $$ 这个式子被称为 链式法则。 Independence 对于事件 $ A,B $，如果 $ \mathbb{P}(A\cap B)=\mathbb{P}(A)\mathbb{P}(B) $，或者等价地 $ \mathbb{P}(A|B)=\mathbb{P}(A) $，那么我们称 $ A $ 和 $ B $ 是独立的。这表明 $ A $ 或 $ B $ 自己是否发生对对方是否发生没有影响。 ...

Motivation 例题：在圆上“随机”选一段弧，问弧长大于圆周的 $ \frac{1}{3} $ 的概率？（Bertrand paradox） 至少三种自然的“均匀化”模型会给出不同答案： 对弧长参数均匀（在 $ [0, 2\pi) $ 上均匀取长度，再随机起点）。 对端点在圆上独立均匀（等价于随机两点确定弧，需指定取较短或较长弧）。 对中心角或几何构造的中间量均匀（如均匀选角度后裁剪）。 核心问题：如何定义“随机”？不同“随机化”方案导致不同答案。 讨论概率问题必须先明确概率空间（样本空间、事件族与概率测度），否则“概率”无从谈起。 Probability Space 一个概率空间由三元组 $ (\Omega, \mathcal{F}, \mathbb{P}) $ 构成： $ \Omega $：样本空间（一次随机试验所有可能结果）。 $ \mathcal{F} \subseteq 2^{\Omega} $：事件族（允许讨论与运算的集合）。 $ \mathbb{P} : \mathcal{F} \to [0,1] $：概率测度（赋予事件概率）。 记号说明： $ \Omega $：样本空间。 $ 2^{\Omega} $：$ \Omega $ 的幂集（所有子集的集合）。 为什么 $ \mathbb{P} $ 要定义在 $ \mathcal{F} $ 上而非直接在 $ \Omega $ 上？ 离散可数时，取 $ \mathcal{F} = 2^{\Omega} $ 可行，且对单点赋值即可确定所有事件的概率。 连续时不同：单点的概率通常为 $ 0 $，但不可数并可有正概率；且 $ 2^{\Omega} $ 中存在不可测集合，无法一致赋值（见下文 Vitali set 与 Axiom of Choice）。因此需选择一个足够大又可控的 $ \sigma $- 代数作为事件族。 Sigma-Algebra 要求 $ \mathcal{F} $ 构成一个 $ \sigma $- 代数（域）： ...

Problem 1 (1) 求 $$ \sum_{k=0}^{n} \binom{ 2n }{ 2k } $$ 解 $$ \begin{align*} & \sum_{k=0}^{n} (-1)^{k}\binom{ n }{ k } = 0 \\ \implies & \sum_{k=0}^{2n} (-1)^{k}\binom{ 2n }{ k } =0 \\ \implies & \sum_{k=0}^{2n} \binom{ 2n }{ 2k } = \sum_{k=1}^{2n} \binom{ 2n }{ 2k - 1 } \end{align*} $$ 同时由于 $$ \sum_{k=0}^{2n} \binom{ 2n }{ 2k } + \sum_{k=1}^{2n} \binom{ 2n }{ 2k - 1 } = \sum_{k=0}^{2n} \binom{ 2n }{ k } = 2^{2n} $$ 得到 $$ \sum_{k=0}^{2n} \binom{ 2n }{ 2k } = 2^{2n-1} $$ ...

Product and Sum Principles 加法原理（分类计数） 若一个任务可分解为若干个互斥的子类，第 $ i $ 类有 $ a_i $ 种方案，则总数为 $ \sum_i a_i $。 解释：互斥保证不重不漏，求和即“或”的计数。 乘法原理（分步计数） 若一个任务分为若干个有序步骤，步骤 $ i $ 有 $ b_i $ 种选择且相互独立，则总数为 $ \prod_i b_i $。 解释：有序步骤逐个做决定，“且”的计数对应乘法。 Constructing Maps 有些组合证明可以依赖于构造映射： 单射：不同原像映到不同像，用于证明下界或“可嵌入性”。 满射：像覆盖全体，用于证明上界可达或构造覆盖。 双射：建立集合 $ A $ 与 $ B $ 的一一对应，从而数 $ |A|=|B| $；这是“数某一个量 ⇒ 构造双射”的核心思想。 Twelvefoldway 将 $ n $ 个球放入 $ m $ 个盒子，球与盒子可“可区分/不可区分”，以及盒子容量约束“任意/至多 1/至少 1”。 $ n $ $ m $ 任意 $ \leq 1 $ $ \geq 1 $ 不同 不同 $ m^{n} $ $ m^{\underline{n}} $ $ m!\left\{ {n \atop m} \right\} $ 同 不同 $ \binom{ n+m-1 }{ m-1 } $ $ \binom{ m }{ n } $ $ \binom{ n-1 }{ m-1 } $ 不同 同 $ \sum_{k=0}^{\min(n,m)} \left\{ {n \atop k} \right\} $ $ [n \leq m] $ $ \left\{ {n \atop m} \right\} $ 同 同 $ p_{\leq m}(n) $ $ [n \leq m] $ $ p(n,m) $ “把 $ n $ 个不同球分成 $ k $ 个非空无序盒”对应第二类斯特林数 $ \left\{ {n \atop k} \right\} $。 ...

课程讲义 在这门课里，我们会专注于所谓的 科尔莫哥洛夫（Kolmogorov）的公理体系，它使得我们能够使用数学分析的工具来研究概率。 St. Petersburg Paradox 圣彼得堡悖论。假设一个基于抛硬币赌博的游戏，庄家会一直扔硬币直到结果是正面，如果扔了 $ k $ 次，那么就会给玩家 $ 2^{k} $ 元的奖金。现在的问题是你愿意花多少钱来购买一次玩这个游戏的机会。 一个很自然的想法是计算游戏的期望，那么我们很容易发现期望收益是 $$ \sum_{k \geq 1} 2^{k}\cdot 2^{-k} = 1 + 1 + \dots = +\infty $$ 这说明平均每一轮我们的收益是无穷大，然而在现实生活中你真的愿意花大价钱去玩这个游戏吗？或者可以写一个简单的程序模拟一下就会发现，在比如门票定为 $ 100 $ 元，玩几百局，还是会轻易地输掉几万块钱。我们生活中一个常见的直觉是如果重复一个随机过程足够多次，平均收益就会逐渐趋近于期望收益，这在概率论中叫做大数定律（Law of large numbers），但是在现实生活中我们并没有能力重复足够多游戏轮数去达到这个期望值。那么现在的问题就是如果定价用 $ a\cdot n $ 元来购买 $ n $ 次游戏机会，$ a $ 定为多少是合理的？ 用这门课中后续会学习到的数学工具，我们可以得到答案为 $ \log n $ （这个结果也符合我们实际的直觉）。 随机游走 对二维随机游走问题的一个简化的建模是在 $ \mathbb{Z}^{2} $ 的网格上随机游走，从原点 $ (0,0) $ 出发，每次以 $ \dfrac{1}{4} $ 的概率往上下左右四个方向移动。我们现在询问，这个随机游走的路径是否会无数次回到原点？用 $ T $ 来表示第一次回到原点的时间，那么可以证明无数次回到原点等价于 $ \mathbb{P}[T < \infty] = 1 $ ，也就是 $ T $ 以 $ 1 $ 的概率是有限的，当然目前只能从直觉上去理解，这个写法需要在后续的课程中去严格定义。 ...