Mika Field Notes

Article

离散概率导论

本笔记基于 UC Berkeley CS 70 课程内容及个人课堂手写笔记整理，旨在建立直观又严谨的离散概率知识体系。

May 3, 2026 修考 21 min read

https://www.eecs70.org/assets/pdf/notes/n13.pdf

离散概率导论 (Introduction to Discrete Probability) 学习笔记

1. 随机实验与样本空间 (Random Experiments & Sample Space)

一个随机实验 (Random Experiment) 通常包含从基数为 nn 的集合 SS 中抽取 kk 个元素。抽样方式可以分为：有放回/无放回，以及考虑顺序/不考虑顺序（这与组合计数紧密相连）。

核心概念理清与纠错

在学习概率初期，极易混淆“样本点”与“事件”的概念，此处务必注意：

概念英文名称定义与数学表示形象理解纠错与注意点
样本空间Sample Space (Ω\Omega)实验所有可能结果的集合。整个大集体（全集）必须定义清晰，否则概率讨论没有意义。
样本点Sample Point (ω\omega)样本空间 Ω\Omega 中的单个元素，即 ω∈Ω\omega \in \Omega。一种具体的单一样本结果手写笔记纠错：手写笔记中误记为“一个子集”。请记住，它只是一个元素而非集合。
事件Event (AA)样本空间 Ω\Omega 的一个子集，即 A⊆ΩA \subseteq \Omega。满足某些条件的结果集合事件是一个集合（可以包含多个样本点）。

经典引入：硬币投掷 4 次

  • 基础集合 S={H,T}S = \{H, T\}（正面 HH，反面 TT），有放回地抽取 k=4k = 4 次。
  • 样本点 ω\omega：HTHTHTHT 是其中的一个样本点。
  • 样本空间 Ω\Omega：包含全部 24=162^4 = 16 个可能的序列： Ω=(HHHHHTHHTHHHTTHH HHHTHTHTTHHTTTHT HHTHHTTHTHTHTTTH HHTTHTTTTHTTTTTT)\Omega = \begin{pmatrix} HHHH & HTHH & THHH & TTHH \ HHHT & HTHT & THHT & TTHT \ HHTH & HTTH & THTH & TTTH \ HHTT & HTTT & THTT & TTTT \end{pmatrix}

2. 概率空间 (Probability Space)

一个概率空间由样本空间 Ω\Omega 以及为每个样本点 ω\omega 赋予的概率 P[ω]P[\omega] 共同构成，它必须满足以下两个核心公理：

  1. 非负性 (Non-negativity)：对所有 ω∈Ω\omega \in \Omega，有 0≤P[ω]≤10 \le P[\omega] \le 1。

  2. 和为一 (Sum to 1)：所有样本点的概率之和必须为 1，即：

    ∑ω∈ΩP[ω]=1\sum_{\omega \in \Omega} P[\omega] = 1

均匀概率空间 (Uniform Probability Space)

如果样本空间中的每个结果都是等可能的（例如抛一枚均匀的硬币或掷一颗公平的骰子），若样本空间大小为 N=∣Ω∣N = |\Omega|，则每个样本点的概率为：

P[ω]=1N,∀ω∈ΩP[\omega] = \frac{1}{N}, \quad \forall \omega \in \Omega

事件的概率 (Probability of an Event)

由于事件 AA 是样本空间 Ω\Omega 的子集，因此事件 AA 的概率就是它所包含的所有样本点的概率之和：

P[A]=∑ω∈AP[ω]P[A] = \sum_{\omega \in A} P[\omega]

  • 练习：在 4 次公平硬币投掷中，求“恰好出现 2 次正面”这一事件 AA 的概率。
    • 符合条件的事件集：A={HHTT,HTHT,HTTH,THHT,THTH,TTHH}A = \{HHTT, HTHT, HTTH, THHT, THTH, TTHH\}，大小 ∣A∣=(42)=6|A| = \binom{4}{2} = 6。
    • 总样本空间大小：∣Ω∣=24=16|\Omega| = 2^4 = 16，每个样本点概率为 116\frac{1}{16}。
    • 计算：P[A]=6×116=38P[A] = 6 \times \frac{1}{16} = \frac{3}{8}。

3. 经典概率模型与例题 (Examples)

3.1 投掷硬币 (Coin Tosses) — 非均匀概率空间

设硬币出现正面的概率为 P[H]=pP[H] = p，出现反面的概率为 P[T]=1−pP[T] = 1-p。我们投掷 nn 次。

  • 例题：若投掷 44 次，且硬币不均匀，正面概率 p=23p = \frac{2}{3}（反面概率为 13\frac{1}{3}）。

    1. 样本点 HHHHHHHH 的概率：

      P[HHHH]=(23)4=1681P[HHHH] = \left(\frac{2}{3}\right)^4 = \frac{16}{81}

    2. 样本点 TTHHTTHH 的概率：

      P[TTHH]=(13)×(13)×(23)×(23)=481P[TTHH] = \left(\frac{1}{3}\right) \times \left(\frac{1}{3}\right) \times \left(\frac{2}{3}\right) \times \left(\frac{2}{3}\right) = \frac{4}{81}

    3. 事件 AA = “四次投掷结果全部相同”：

      A={HHHH,TTTT}A = \{HHHH, TTTT\}

      P[A]=P[HHHH]+P[TTTT]=(23)4+(13)4=1681+181=1781P[A] = P[HHHH] + P[TTTT] = \left(\frac{2}{3}\right)^4 + \left(\frac{1}{3}\right)^4 = \frac{16}{81} + \frac{1}{81} = \frac{17}{81}

    4. 事件 BB = “恰好出现 2 次正面”：

      • 符合条件的样本点数量为 (42)=6\binom{4}{2} = 6。

      • 其中每一个样本点的概率均相同，例如 P[HTHT]=p2(1−p)2=(23)2(13)2=481P[HTHT] = p^2(1-p)^2 = (\frac{2}{3})^2(\frac{1}{3})^2 = \frac{4}{81}。

      • 所以：

        P[B]=(42)⋅p2(1−p)2=6×481=2481=827P[B] = \binom{4}{2} \cdot p^2(1-p)^2 = 6 \times \frac{4}{81} = \frac{24}{81} = \frac{8}{27}

  • 一般化推广（事件 CC：在 nn 次投掷中恰好出现 rr 次正面）：

    P[C]=(nr)pr(1−p)n−rP[C] = \binom{n}{r} p^r (1-p)^{n-r}

💡 联想与思考（手写笔记心得）： 这个公式让我立刻想到了数学中的二项式定理 (Binomial Theorem)：

(a+b)n=∑r=0n(nr)arbn−r(a+b)^n = \sum_{r=0}^n \binom{n}{r} a^r b^{n-r}

如果我们将 a=p,b=1−pa = p, b = 1-p 代入，会发现所有可能事件（从 00 次正面到 nn 次正面）的概率总和为：

∑r=0n(nr)pr(1−p)n−r=(p+(1−p))n=1n=1\sum_{r=0}^n \binom{n}{r} p^r (1-p)^{n-r} = (p + (1-p))^n = 1^n = 1

这从数学上完美证明并契合了概率空间“和为一”的性质！

3.2 掷骰子 (Rolling Dice) — 均匀空间简化计数

考虑掷两枚公平的骰子。样本空间 Ω={(i,j):1≤i,j≤6}\Omega = \{(i,j) : 1 \le i,j \le 6\}，大小 ∣Ω∣=36|\Omega| = 36。每个样本点的概率均为 136\frac{1}{36}。

由于是均匀空间，计算事件概率可以直接转化为计数问题：

P[A]=∣A∣∣Ω∣=A 中的样本点数量Ω 中的样本点数量P[A] = \frac{|A|}{|\Omega|} = \frac{A \text{ 中的样本点数量}}{\Omega \text{ 中的样本点数量}}

  • 例题：
    1. 事件 AA = “两枚骰子点数之和至少为 10”：
      • 符合条件的样本点有：(4,6),(5,5),(5,6),(6,4),(6,5),(6,6)(4,6), (5,5), (5,6), (6,4), (6,5), (6,6)，共 6 个。
      • P[A]=636=16P[A] = \frac{6}{36} = \frac{1}{6}。
    2. 事件 BB = “至少出现一个 6”：
      • 符合条件的样本点有：第一枚为 6 的情况（6个），第二枚为 6 的情况（6个），排除重复的 (6,6)(6,6)，共 6+6−1=116+6-1 = 11 个。
      • P[B]=1136P[B] = \frac{11}{36}。

3.3 洗牌问题 (Card Shuffling)

将 nn 张不同的牌彻底洗匀。

  • 样本空间 Ω\Omega 为这 nn 张牌的所有排列组合，因此大小 ∣Ω∣=n!|\Omega| = n!。
  • 由于洗牌是完全随机的，所以这是一种均匀概率空间，每一种具体排列出现的概率均为 1n!\frac{1}{n!}。
  • 应用场景：随机分发 nn 个学生的作业，每个人随机分到一份，这就是该模型的典型应用。

3.4 德州扑克手牌 (Poker Hands)

从一副 52 张的标牌中随机抽取 5 张手牌（无放回，不计顺序）。

  • 样本空间大小为：

    ∣Ω∣=(525)=52×51×50×49×485×4×3×2×1=2,598,960|\Omega| = \binom{52}{5} = \frac{52 \times 51 \times 50 \times 49 \times 48}{5 \times 4 \times 3 \times 2 \times 1} = 2,598,960

  • 例题：求拿到同花手牌（Flush，5张牌花色全部相同）的概率：

    • 步骤 1：选择一种花色，共有 44 种选法。

    • 步骤 2：从该花色的 13 张牌中任选 5 张，有 (135)\binom{13}{5} 种选法。

    • 步骤 3：计算同花手牌的数量：

      ∣A∣=4×(135)=4×13×12×11×10×95×4×3×2×1=4×1287=5148|A| = 4 \times \binom{13}{5} = 4 \times \frac{13 \times 12 \times 11 \times 10 \times 9}{5 \times 4 \times 3 \times 2 \times 1} = 4 \times 1287 = 5148

    • 步骤 4：求概率：

      P[Flush]=4×(135)(525)=51482598960≈0.002(约为 0.2%)P[\text{Flush}] = \frac{4 \times \binom{13}{5}}{\binom{52}{5}} = \frac{5148}{2598960} \approx 0.002 \quad (\text{约为 } 0.2\%)

3.5 球与箱子 (Balls and Bins)

将 mm 个有标记的球随机扔进 nn 个有标记的箱子中。每个球落入任何一个箱子的概率相同且相互独立。

  • 因为每个球都有 nn 种箱子选择，总共有 mm 个球，所以样本空间大小 ∣Ω∣=nm|\Omega| = n^m。这是一个均匀概率空间。

  • 例题：将 20 个球放入 10 个箱子中（m=20,n=10m=20, n=10）。

    1. 事件 AA = “1号箱子是空的”：

      • 这意味着所有的 20 个球都只能落在剩下的 9 个箱子中。

      • 符合条件的样本数：9209^{20}。

      • 计算概率：

        P[A]=9201020=(910)20≈0.12P[A] = \frac{9^{20}}{10^{20}} = \left(\frac{9}{10}\right)^{20} \approx 0.12

    2. 事件 BB = “1号箱子中至少有 1 个球”：

      • 💡 手写笔记思路：从补集 (Complement) 的视角思考！

      • “至少有 1 个”的对立面就是“完全没有”（即事件 AA）。所以事件 BB 是事件 AA 的补集，即 B=A‾B = \overline{A}。

      • 根据补集概率公式：

        P[B]=1−P[A]=1−(910)20≈1−0.12=0.88P[B] = 1 - P[A] = 1 - \left(\frac{9}{10}\right)^{20} \approx 1 - 0.12 = 0.88

  • 一般化公式推导（将 mm 个球放入 nn 个箱子）：

    P[某个特定箱子为空]=(1−1n)mP[\text{某个特定箱子为空}] = \left(1 - \frac{1}{n}\right)^m

    P[某个特定箱子非空]=1−(1−1n)mP[\text{某个特定箱子非空}] = 1 - \left(1 - \frac{1}{n}\right)^m

3.6 生日悖论 (Birthday Paradox)

💡 手写笔记思路延伸：球与箱子模型可以完美应用到生日问题上。 我们将“人”视作“球”（数量为 mm），将一年的“365天”视作“箱子”（数量为 n=365n = 365）。

  • 问题：在一个有 mm 个人的房间里，至少有两个人生日相同的概率是多少？

  • 分析：定义事件 AA = “至少有两个人生日相同”。直接计算 AA 包含的组合非常繁琐，我们采用补集视角：求其对立事件 A‾\overline{A} = “所有 mm 个人的生日互不相同”（即无碰撞地放入箱子）。

    • 第 1 个人的生日有 365 种选择；

    • 第 2 个人的生日为了不与前者冲突，有 364 种选择；

    • ……

    • 第 mm 个人的生日有 365−m+1365 - m + 1 种选择。

    • 因此，所有人生日均不相同的方案数为：

      ∣A‾∣=365×364×⋯×(365−m+1)|\overline{A}| = 365 \times 364 \times \dots \times (365 - m + 1)

  • 计算概率：

    P[A‾]=∣A‾∣∣Ω∣=365×364×⋯×(365−m+1)365mP[\overline{A}] = \frac{|\overline{A}|}{|\Omega|} = \frac{365 \times 364 \times \dots \times (365 - m + 1)}{365^m}

    P[A]=1−P[A‾]=1−365×364×⋯×(365−m+1)365mP[A] = 1 - P[\overline{A}] = 1 - \frac{365 \times 364 \times \dots \times (365 - m + 1)}{365^m}

  • 直觉与科学的碰撞：

    • 当人数 m=23m = 23 时，至少两人同一天生日的概率 P[A]>50%P[A] > 50\%！
    • 当人数 m=60m = 60 时，概率 P[A]>99%P[A] > 99\%！ 这之所以被称为“悖论”，是因为人类直觉上容易把“有人和我生日相同”（概率极低）与“房间里任意两个人生日相同”混淆。

4. 三门问题（Monty Hall Problem）深度剖析

针对你在手写笔记最后提到的难点：“其实我还是不能理解三门问题的证明”。我们在这里用两种方式——直观分组法与严谨数学推导为你进行彻底的复习。

4.1 游戏规则重温

image-20260522110056227

  1. 场上有三扇门（1、2、3号门）。一扇门后是大奖汽车，另外两扇门后是山羊。
  2. 你先选定一扇门（例如 1 号门），此时该门不打开。
  3. 主持人 Carol（她知道大奖在哪个门后）必须从剩下的两扇门中，打开一扇后面是山羊的门。
  4. 此时，场上还剩两扇没打开的门（你选的 1 号门，和另一扇没开的门）。
  5. Carol 问你：“你要坚持原来的选择，还是选择换门 (Switch)？”
  6. 核心疑问：换门真的会提高中奖率吗？还是两扇门中奖率各占 50%50\%？

4.2 直观物理图解：为什么换门概率是 2/3？

我们不套用任何数学公式，通过物理直觉进行分组：

  1. 初始选择阶段：
    • 你选择 1 号门。此时，你把三扇门分成了两个阵营：
      • 【你选的门】（A组）：只有 1 号门，中奖率是 13\frac{1}{3}。
      • 【剩下的门】（B组）：包含 2、3 号门。这两扇门作为一个整体，中奖率是 23\frac{2}{3}。
  2. 主持人的“透底”操作：
    • 主持人 Carol 从 B 组（2、3号门）中，挑出了一扇绝对有山羊的门并当众打开。
    • 关键点来了：Carol 的这个动作，并没有改变 B 组整体拥有 23\frac{2}{3} 中奖率的物理事实。因为她事先知道底牌，所以不论你选了什么，她总能从 B 组挑出一只山羊。
    • 既然 B 组的中奖总概率依然是 23\frac{2}{3}，而 B 组中有一扇门已经被排除（概率归 0），那么B 组中剩下那一扇未打开的门，就瞬间独自继承了整个 B 组 23\frac{2}{3} 的中奖概率！
    • 而你手里一直握着的 A 组（1号门），它的概率自始至终被锁死在最初的 13\frac{1}{3}，没有任何变化。
    • 结论：选择“换门”，你的中奖率会立刻从 13\frac{1}{3} 飙升到 23\frac{2}{3}！

极简场景穷举表（假设你初始选择 1 号门）：

汽车真实位置你的初始选择主持人 Carol 必须打开的门如果你坚持（不换）如果你换门（Switch）
1号门1号门（对）2号门 或 3号门（羊）中奖 (Win)得到山羊 (Lose)
2号门1号门（错）只能开 3号门（羊）得到山羊 (Lose)中奖 (Win)
3号门1号门（错）只能开 2号门（羊）得到山羊 (Lose)中奖 (Win)

从上表可以清晰看出：

  • 只要你一开始选错了（概率为 23\frac{2}{3}），由于主持人的排除法，换门就必定会赢。
  • 只有当你一开始选对了（概率为 13\frac{1}{3}），换门才会输。
  • 所以，“换门就赢”的概率等同于“一开始选错”的概率，即 23\frac{2}{3}。

4.3 严谨概率空间四步法证明

为了逻辑的完美闭环，我们用笔记前两章学到的“概率空间四步法”进行严格推导：

第一步：构建样本空间 Ω\Omega

我们将每一次游戏的结果表示为一个三元组 (i,j,k)(i, j, k)：

  • i∈{1,2,3}i \in \{1, 2, 3\} 表示汽车的实际位置。
  • j∈{1,2,3}j \in \{1, 2, 3\} 表示参赛者的初始选择。
  • k∈{1,2,3}k \in \{1, 2, 3\} 表示主持人 Carol 打开的门。

根据规则，Carol 不能开大奖门（k≠ik \neq i），也不能开参赛者选的门（k≠jk \neq j）。因此，剔除不可能的情况后，样本空间 Ω\Omega 刚好包含 12 个样本点。

第二步：为每个样本点分配概率

我们假设：

  • 大奖随机放在三扇门后，概率各为 13\frac{1}{3}。
  • 参赛者随机选门，概率各为 13\frac{1}{3}。
  • Carol 开门的规则：如果 i≠ji \ne j（初始选错），Carol 只能开剩下唯一有山羊的门（概率为 1）；如果 i=ji = j（初始选对），Carol 可以在剩下两扇门中随机开一扇（概率各为 12\frac{1}{2}）。

因此，这 12 个样本点的概率分配如下：

  1. 当初始选错时 (i≠ji \ne j)，共有 6 种情况： 例如 (2,1,3)(2, 1, 3) （车在2，人选1，Carol开3）：

    P[(2,1,3)]=13(车)×13(人)×1(Carol无选择)=19P[(2, 1, 3)] = \frac{1}{3} (\text{车}) \times \frac{1}{3} (\text{人}) \times 1 (\text{Carol无选择}) = \frac{1}{9}

    同理，(3,1,2),(1,2,3),(3,2,1),(1,3,2),(2,3,1)(3, 1, 2), (1, 2, 3), (3, 2, 1), (1, 3, 2), (2, 3, 1) 这 6 个样本点的概率均为 19\frac{1}{9}。

  2. 当初始选对时 (i=ji = j)，共有 6 种情况： 例如 (1,1,2)(1, 1, 2) （车在1，人选1，Carol开2）：

    P[(1,1,2)]=13(车)×13(人)×12(Carol二选一)=118P[(1, 1, 2)] = \frac{1}{3} (\text{车}) \times \frac{1}{3} (\text{人}) \times \frac{1}{2} (\text{Carol二选一}) = \frac{1}{18}

    同理，(1,1,3),(2,2,1),(2,2,3),(3,3,1),(3,3,2)(1, 1, 3), (2, 2, 1), (2, 2, 3), (3, 3, 1), (3, 3, 2) 这 6 个样本点的概率均为 118\frac{1}{18}。

合规性检查：

∑ω∈ΩP[ω]=(6×19)+(6×118)=23+13=1(概率和为 1，完美！)\sum_{\omega \in \Omega} P[\omega] = \left(6 \times \frac{1}{9}\right) + \left(6 \times \frac{1}{18}\right) = \frac{2}{3} + \frac{1}{3} = 1 \quad (\text{概率和为 1，完美！})

第三步：定义我们关心的事件

我们采用“换门 (Switch)”策略。 定义事件 WW = “通过换门策略赢得汽车”。 在什么情况下换门能赢？ 只要你的初始选择 jj 不是汽车所在的门 ii（即初始选错，i≠ji \ne j），Carol 就会把另一扇藏有山羊的门打开，此时你只要换门，就必定换到藏有汽车的门。 因此，换门能赢的事件 WW 对应的正是所有满足 i≠ji \ne j 的样本点集合：

W={(2,1,3),(3,1,2),(1,2,3),(3,2,1),(1,3,2),(2,3,1)}W = \{(2, 1, 3), (3, 1, 2), (1, 2, 3), (3, 2, 1), (1, 3, 2), (2, 3, 1)\}

第四步：计算事件概率

将事件 WW 包含的所有样本点概率进行累加：

P[W]=P[(2,1,3)]+P[(3,1,2)]+P[(1,2,3)]+P[(3,2,1)]+P[(1,3,2)]+P[(2,3,1)]P[W] = P[(2,1,3)] + P[(3,1,2)] + P[(1,2,3)] + P[(3,2,1)] + P[(1,3,2)] + P[(2,3,1)]

P[W]=19+19+19+19+19+19=6×19=23P[W] = \frac{1}{9} + \frac{1}{9} + \frac{1}{9} + \frac{1}{9} + \frac{1}{9} + \frac{1}{9} = 6 \times \frac{1}{9} = \frac{2}{3}

而如果你选择“坚持不换门 (Stick)”策略（事件 WstickW_{\text{stick}}，对应初始选对的情况 i=ji = j）：

P[Wstick]=6×118=13P[W_{\text{stick}}] = 6 \times \frac{1}{18} = \frac{1}{3}

严谨数学证明达成！ 换门的中奖概率（23\frac{2}{3}）确确实实是不换门（13\frac{1}{3}）的两倍。

5. 离散概率解题通用模板：“黄金四步法”

无论未来遇到多么复杂、多么反直觉的概率难题，只要回归最基本的定义，按照以下四个步骤进行，就能确保万无一失：

① 明确样本空间 Ω (所有可能结果的集合)
       ↓
② 为每个样本点 ω 分配概率 P[ω] (确保非负且总和为 1)
       ↓
③ 找准目标事件 A (确定满足条件的样本点子集)
       ↓
④ 概率求和：P[A] = ∑ P[ω] (若为均匀空间，可简化为计数比值 |A| / |Ω|)

牢记这套系统化方法，概率论的世界将不再迷茫！