Lecture 20: Expectations & Linearity（期望与线性性）

目录 · ← l20 · l22 →

Lecture 20: Expectations & Linearity（期望与线性性）

概述

上一讲（Lecture 19）我们定义了随机变量 (random variable) 并给出了它的分布 (distribution)，即完整的信息载体 $\{(a, \Pr[X=a])\}$。但完整的分布往往既算不出来、也不好看懂：20 个学生随机交换作业时固定点的分布，原则上要枚举 $20! \approx 2.4\times 10^{18}$ 个样本点。本讲的目标是用一个数字摘要代替整个分布，这个摘要就是期望 (expectation)。

本讲的核心工具是指示随机变量 (indicator random variable) 与期望的线性性 (linearity of expectation)。核心结论只有一句话：$\mathbb{E}[X+Y]=\mathbb{E}[X]+\mathbb{E}[Y]$，而且完全不需要 $X$ 与 $Y$ 独立。这条”免费午餐”是整门 CS70 后半段最有用的技术：把一个”全局复杂”的随机量（总碰撞数、最大负载、集齐优惠券的次数）拆成许多”局部简单”的指示变量之和，逐项求期望再相加。本讲将用它一次性拿下三大经典应用：二项分布的期望、收集者问题 (coupon collector)、哈希与负载均衡 (hashing / load balancing)。

核心概念的直观解释

期望（Expectation / Expected Value / Mean / Average）

• 定义：设 $X$ 是取值集合为 $A$ 的离散随机变量。$X$ 的期望定义为

也就是说：把每个可能取值乘上它发生的概率，再把所有项加起来。等价地，用下标 $f(x)$ 表示概率质量函数时写作 $\mathbb{E}[X] = \sum_x x\, f(x)$。

• 直观解释（”它是什么意思？”）：期望是概率加权的平均值。它回答的问题不是你这一次实验会得到什么，而是”如果我把这套实验重复成千上万次，平均下来每个结果是多少”。三种等价的心理图像：

  1. 长期平均：掷一枚公平硬币，正面记 $+1$、反面记 $-1$。单次结果永远是 $\pm1$，但掷 $10^6$ 次后把结果平均，会稳定在 $0$ 附近——这个 $0$ 就是期望。这就是 Lecture 23 大数定律要精确化的直觉。
  2. 物理质心：把概率分布想象成一块木板，在位置 $a$ 处放上质量 $\Pr[X=a]$。整块木板的重心（平衡点）恰好在 $x=\mathbb{E}[X]$ 处。这就是官方 Note 中那个”木制剪影的重心”图景：质量大的地方把平衡点拉过去。
  3. 加权平均的推广：普通平均是每个取值权相等（各 $1/n$）；期望允许不同取值有不同的权重，权重就是概率，且权重之和必须为 $1$。

• 具体示例：掷一枚公平骰子，$X$ 是朝上的点数。$X$ 以概率 $1/6$ 取 $1,2,\dots,6$，于是

• 注意一：期望不必是 $X$ 实际可能取到的值。 上例中 $X$ 永远取不到 $3.5$——骰子没有面朝上写着 $3.5$。期望是分布的”平衡点”，而平衡点可以落在两个支撑点中间。这与”最大值”、”众数”这类必须取到的统计量截然不同。
• 注意二：期望可能不存在（为无穷）。 官方 Note 有一条技术注记：定义式里的级数必须绝对收敛，即 $\sum_{a}\vert a\vert \Pr[X=a]<\infty$，期望才良定义。反例：设 $X$ 以概率 $2^{-k}$ 取值 $2^k$（$k=1,2,3,\dots$）。先验证这是合法分布：$\sum_{k\ge1}2^{-k}=1$ ✔。但

这个随机变量每次取到的都是有限的数，但期望是无穷大——这正是”圣彼得堡悖论”类赌博的形态。本讲后续的所有结论都默认涉及的期望存在且有限。

指示随机变量（Indicator Random Variable）

• 定义：设 $A$ 是概率空间中的事件。$A$ 的指示随机变量 (indicator r.v.) 定义为

• 直观解释（”它是什么意思？”）：指示变量是”把’是/否’翻译成’1/0’“的开关。它是一个货真价实的随机变量（函数 $I_A:\Omega\to\{0,1\}\subseteq\mathbb{R}$），因而可以做加法、可以被求期望。它的期望算起来简单到近乎无脑：

这个观察看似平凡，却是整讲威力的来源。 原因在于：把一个”数数”型随机量写成指示变量之和后，求期望就退化成”把一堆概率加一加”——概率往往比分布好算得多。

• 具体示例：掷一枚公平骰子，$A=$”点数不小于 $5$”。则 $I_A$ 以概率 $2/6$ 取 $1$，以概率 $4/6$ 取 $0$，$\mathbb{E}[I_A]=\Pr[A]=1/3$。你不需要写出”$I_A$ 的分布”以外的任何东西。

  更典型的例子：设 $X_n$ 表示 $n$ 个学生随机交换作业后拿到自己作业的人数（即随机排列的固定点 (fixed point) 个数）。$X_n$ 的分布极其难算，但我们可以把它写成

于是 $\mathbb{E}[X_n]=\sum_i \mathbb{E}[I_i]=\sum_i \Pr[\text{学生 } i \text{ 拿回自己的作业}]=\sum_i \frac1n=n\cdot\frac1n=1$。无论 $n$ 多大，期望固定点个数恒为 $1$。

期望的线性性（Linearity of Expectation）

• 定义（陈述）：对同一个概率空间上的任意两个随机变量 $X,Y$，以及任意常数 $c\in\mathbb{R}$，

• 直观解释（”它是什么意思？”）：期望是”以概率为权重的求和”，而求和本身是线性的。既然 $\sum_\omega$ 可以逐项拆开、常数可以提出，那么先取期望再相加、和先相加再取期望，结果必然一样。

  但真正让这条定理”不平凡”的是它的附带条件为零：它不要求 $X\perp Y$，不要求同分布，不要求有限取值，甚至允许两个变量是同一个变量（$\mathbb{E}[X+X]=2\mathbb{E}[X]$）。对比一下：Lecture 19 学过的”独立事件才有的乘法法则”需要独立性，而这里的加法法则什么都不需要。这是概率论里罕见的”免费午餐”。

• 具体示例：两枚骰子的点数之和 $X=Y_1+Y_2$。单枚骰子 $\mathbb{E}[Y_1]=\mathbb{E}[Y_2]=7/2$。于是不用算 $X$ 的分布（那需要 11 项加和），直接得 $\mathbb{E}[X]=7/2+7/2=7$。若用定义硬算：$\mathbb{E}[X]=2\cdot\frac1{36}+3\cdot\frac2{36}+\cdots+12\cdot\frac1{36}=7$（脚本验算 ✔），费时数倍。

调和数（Harmonic Number）

• 定义：$H_n=\sum_{i=1}^{n}\frac1i=1+\frac12+\frac13+\cdots+\frac1n$，约定 $H_0=0$。
• 直观解释：它是”倒数之和”，增长极慢——大约与 $\ln n$ 同阶。收集者问题的答案恰好是 $nH_n$，所以 $H_n$ 的估计直接决定答案的量级。

• 具体示例：$H_1=1$，$H_2=1.5$，$H_3=\frac{11}{6}\approx1.8333$，$H_{10}\approx2.92897$（脚本精确值 $2.9289682539682538$），$H_{100}\approx5.18738$，$H_{1000}\approx7.48547$。

  精确的夹逼（用积分比较，见后文推导）：$\ln n < H_n < \ln n + 1$。更精细的近似是 $H_n\approx\ln n+\gamma$，其中 $\gamma\approx0.5772156649$ 是欧拉常数 (Euler’s constant)。数值验证：$n=10$ 时 $\ln 10+\gamma=2.3026+0.5772=2.8798$ 对比真值 $2.9290$；$n=100$ 时 $\ln100+\gamma=5.1824$ 对比真值 $5.1874$ —— 随 $n$ 增大越来越准。

指示变量分解的”总—分”结构可以画成这样（以”$m$ 个球投 $n$ 个箱，数空箱数”为例）：

   全局难算的量:  Y = "有多少个箱子是空的"
   ─────────────────────────────────────────────────────────────
   Y =  I_1  +  I_2  +  I_3  + ... +  I_n
        │       │       │              │
        │       │       │              └─ I_n = 1 若箱 n 为空, 否则 0
        │       │       └──────────────── I_3 = 1 若箱 3 为空, 否则 0
        │       └──────────────────────── I_2 = 1 若箱 2 为空, 否则 0
        └──────────────────────────────── I_1 = 1 若箱 1 为空, 否则 0

   每个 I_j 只看"一个箱子"，完全不管别的箱子 → 期望好算:
        E[I_j] = Pr[箱 j 为空] = (1 - 1/n)^m

   线性性把 n 个局部期望加回来（不需要各 I_j 独立！）:
        E[Y] = E[I_1] + ... + E[I_n] = n (1 - 1/n)^m
   ─────────────────────────────────────────────────────────────
   同一个招式换个"拆分单位"就得到别的结果:
        • 拆成"每个球" → E[箱 1 里的球数] = m/n
        • 拆成"每个键对"→ E[碰撞对数] = C(m,2) / n
        • 拆成"每个阶段"→ E[集齐券的盒数] = n H_n     (见下图)

如下是把”集齐 $n$ 张券所需的总盒数”切成 $n$ 个阶段（这是收集者问题的分解图，取 $n=7$）：

   时间轴（每格 = 买一盒谷物，格子里写的是抽到的券号；n = 7）

   盒号:   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
   券号:   3   3   7   7   7   1   7   4   4   7   2   7   7   5   6
   阶段:   1   1   2   2   2   3   3   4   4   4   5   5   5   6   7
           ^       ^           ^       ^           ^           ^   ^

   每个 ^ 标记"抽到一张新券"的那一盒 —— 它同时终结上一阶段、开启下一阶段。
   未被标记的格子抽到的是"重券"（已经在手里的券），它们只是把当前阶段拉长。
   第 1 段末尾的 ^ (盒1, 券3) 是全新; 第 2 段末尾的 ^ (盒3, 券7) 也是全新;
   而盒 4、5 的券 7 则是重券 —— 它们把第 3 段从 1 盒拉长到了 3 盒。

   阶段 i | 覆盖盒号 | 开始时已集齐 | 剩下没见过 |  p_i  |  X_i
   -------+----------+--------------+------------+-------+-----
      1   |   1      |      0 种    |    7 种    |  7/7  |   1
      2   |  2 - 3   |      1 种    |    6 种    |  6/7  |   2
      3   |  4 - 6   |      2 种    |    5 种    |  5/7  |   3
      4   |  7 - 8   |      3 种    |    4 种    |  4/7  |   2
      5   |  9 - 11  |      4 种    |    3 种    |  3/7  |   3
      6   | 12 - 14  |      5 种    |    2 种    |  2/7  |   3
      7   | 15       |      6 种    |    1 种    |  1/7  |   1
   -------+----------+--------------+------------+-------+-----
   校验:  T = X_1+...+X_7 = 1+2+3+2+3+3+1 = 15 = 买盒总数 ✔

   X_i ~ Geometric(p_i)，其中 p_i = (n - i + 1)/n
   期望: E[T] = sum_i 1/p_i = 7(1/7+1/6+1/5+1/4+1/3+1/2+1/1) = 7 H_7 ≈ 18.15
   一般: E[T] = n H_n ≈ n ln n

球的投箱模型（Balls and Bins）

• 定义：把 $m$ 个球独立地、均匀随机地投入 $n$ 个箱子，即每个球独立地以概率 $1/n$ 落入任意指定的箱子。样本空间大小 $n^m$，每个样本点概率 $n^{-m}$。
• 直观解释：这是概率论里最万能的”建模母版”。哈希（键=球，表槽=箱）、负载均衡（作业=球，处理器=箱）、收集者问题（买到的卡片=球，$n$ 种卡片=箱）、生日悖论（人=球，365 天=箱）全都是它的换皮。
• 具体示例：”第 1 个箱子恰好有 $k$ 个球”这一事件的概率是 $\binom{m}{k}(1/n)^k(1-1/n)^{m-k}$，即 $\mathrm{Bin}(m,1/n)$ ——把”球是否落入箱 1”看成抛 $m$ 次偏置硬币。

LOTUS（无意识统计学家定律，Law of the Unconscious Statistician）

• 定义：对随机变量 $X$ 与函数 $g$，

• 直观解释：要求 $\mathbb{E}[g(X)]$，你不必要先把 $g(X)$ 的分布算出来。直接拿 $X$ 的分布在 $g$ 的值域上”按 $g$ 的取值分组”相加即可。它叫”无意识”定律，是因为使用者常常在没意识到自己用了它的情况下就这么算了。
• 具体示例：骰子 $X$，求 $\mathbb{E}[X^2]$。用 LOTUS：$\mathbb{E}[X^2]=\frac16(1+4+9+16+25+36)=\frac{91}{6}\approx15.1667$（脚本验算 ✔）。若先求 $X^2$ 的分布：$X^2$ 以 $1/6$ 取 $1$，$1/6$ 取 $4$，…，其实结果一样，但多绕了一圈。

完整证明与推导（核心）

本讲的核心证明有五组：期望的样本点求和式、线性性、二项分布的期望（两种算法对比）、独立则乘积期望可乘、以及收集者问题与空箱期望的指示变量分解。

定理 20.1（期望的两种等价写法）：设 $X$ 是概率空间 $(\Omega,\Pr)$ 上的离散随机变量。则

其中 $A$ 是 $X$ 的取值集合。

证明策略：双计数 / 交换求和次序。第一种写法按”$X$ 的取值”分组，第二种写法按”样本点”分组。两者是对同一些项做了不同的分组方式，可以用”把每个 $a\cdot\Pr[X=a]$ 中的 $\Pr[X=a]$ 展开成若干 $\Pr[\omega]$ 之和”来打通。选择这个策略，是因为后面证明线性性时，样本点形式能让 $(X+Y)(\omega)=X(\omega)+Y(\omega)$ 这一步变得毫无障碍。

逐步推导：

• 第一步：由定义，$\Pr[X=a]$ 是把所有满足 $X(\omega)=a$ 的样本点概率加起来，即 $\Pr[X=a]=\sum_{\omega:\,X(\omega)=a}\Pr[\omega]$。（依据：概率的可加性 + $\{X=a\}$ 是事件。）
• 第二步：代入定义式：

• 第三步：把外层乘数 $a$ 移入内层求和：$=\sum_{a\in A}\sum_{\omega:\,X(\omega)=a}a\cdot\Pr[\omega]$。（依据：分配律。）
• 第四步：在内层，$\omega$ 满足 $X(\omega)=a$，所以 $a$ 可以换成 $X(\omega)$：$=\sum_{a\in A}\sum_{\omega:\,X(\omega)=a}X(\omega)\cdot\Pr[\omega]$。
• 第五步：关键一步。因为 $X$ 是函数，每个 $\omega\in\Omega$ 属于恰好一个事件 $\{X=a\}$。所以”先按 $a$ 分组、组内遍历 $\omega$”与”直接遍历所有 $\omega$”加起来的是同一批项，每项恰好出现一次：

【证明机制解说】：整个证明的”灵光一现”在第五步，而它的合法性完全依赖于”$X$ 是函数”这一事实——正因为 $X$ 给每个 $\omega$ 唯一指定了一个值，事件族 $\{\{X=a\}\}_{a\in A}$ 才构成 $\Omega$ 的一个划分。如果 $X$ 不是函数（比如一个 $\omega$ 对应两个 $a$），第四步到第五步就会出现重复计数，等式立刻崩塌。这也解释了官方 Note 反复提醒的”随机变量既不随机也不是变量，它是一个函数”——这条性质的第一次真正派上用场就是这里。

另外要留意：样本点形式虽然让证明方便，但一般不适合计算，因为 $\vert \Omega\vert $ 常常是天文数字（$20!$ 级别）。计算的活还是要交给定义式或线性性。

定理 20.2（指示随机变量的期望）：对任意事件 $A$，$\mathbb{E}[I_A]=\Pr[A]$。

证明策略：直接证明。只需把 $I_A$ 的定义代进期望定义式，$0$ 项自动消失。

逐步推导：

• 第一步：$I_A$ 只取 $0,1$ 两个值，故 $\mathbb{E}[I_A]=\sum_{a\in\{0,1\}}a\Pr[I_A=a]$。
• 第二步：$=0\cdot\Pr[I_A=0]+1\cdot\Pr[I_A=1]=\Pr[I_A=1]$。（依据：$0$ 乘以任何数得 $0$。）
• 第三步：事件 $\{I_A=1\}$ 与事件 $A$ 是同一个集合（$I_A(\omega)=1\iff\omega\in A$），故 $\Pr[I_A=1]=\Pr[A]$。$\blacksquare$

【证明机制解说】：这是全讲最短的证明，却也是最该背下来的一条。它的价值在于把”求期望”这个看起来需要完整分布的操作，降级为”求一个概率”。后面所有指示变量技巧都是这条定理的流水线作业。

定理 20.3（期望的线性性，Linearity of Expectation）：对同一概率空间上的任意随机变量 $X,Y$ 与任意常数 $c$，

证明策略：直接证明 + 交换求和次序（严格说是把有限和拆项）。关键是使用定理 20.1 的样本点形式，因为在样本点层面 $(X+Y)(\omega)=X(\omega)+Y(\omega)$ 是逐点成立的实数等式，而定义式层面 $\Pr[X+Y=s]$ 却需要卷积，非常难拆。这正是选择样本点形式的理由。

逐步推导：

• 第一步：反复用定理 20.1 的样本点形式。

• 第二步：按随机变量加法的定义，$(X+Y)(\omega)=X(\omega)+Y(\omega)$。（依据：随机变量的加法是逐点定义的，与函数的加法相同。）

• 第三步：把每个乘积拆成两项。

（依据：$\sum_\omega(a_\omega+b_\omega)=\sum_\omega a_\omega+\sum_\omega b_\omega$，即加法对求和的分配律。这一步不涉及任何概率论假设。）

• 第四步：两个和分别就是 $\mathbb{E}[X]$ 与 $\mathbb{E}[Y]$（再用一次定理 20.1），故 $\mathbb{E}[X+Y]=\mathbb{E}[X]+\mathbb{E}[Y]$。
• 第五步（数乘部分）：$\mathbb{E}[cX]=\sum_\omega (cX)(\omega)\Pr[\omega]=\sum_\omega c\cdot X(\omega)\Pr[\omega]=c\sum_\omega X(\omega)\Pr[\omega]=c\,\mathbb{E}[X]$。（依据：常数可以从求和中提出。）$\blacksquare$

【证明机制解说】：请仔细回看上面的推导，从头到尾没有出现”独立”这两个字，也没有出现任何形如 $\Pr[A\cap B]=\Pr[A]\Pr[B]$ 的式子。 这不是遗漏，而是本质：线性性是纯代数的事实，它只依赖”期望 = 逐点加权求和”这一表达形式，而加权求和天然是线性的。独立性是一条乘积法则（$\Pr[A\cap B]=\Pr[A]\Pr[B]$），它管的是交集、是乘法；期望的线性性管的是并集、是加法。两者属于不同的运算通道，不要混为一谈。

一个容易被忽略但很能说明问题的推论：取 $Y=X$（同一个随机变量），得 $\mathbb{E}[2X]=\mathbb{E}[X]+\mathbb{E}[X]=2\mathbb{E}[X]$。这里 $X$ 与 $X$ 当然不独立（它和自己的相关系数是 $1$），线性性照样成立。这就是”不需要独立”的最干净证据。

定理 20.4（线性性推广到 $n$ 个随机变量）：对任意随机变量 $X_1,\dots,X_n$ 与常数 $c_1,\dots,c_n$，

证明策略：对 $n$ 做归纳法 (induction)。因为定理 20.3 已经给出两个变量的情形，正好可以作为归纳步骤的”引擎”；基础情形 $n=1$ 平凡。选归纳法而不用”直接展开求和”是为了让每一步的依据都落在已证结论上，避免重复劳动。

逐步推导：

• 基础情形 $n=1$：$\mathbb{E}[c_1X_1]=c_1\mathbb{E}[X_1]$，由定理 20.3 的数乘部分直接成立。✔
• 归纳假设：设命题对 $n-1$ 个随机变量成立，即 $\mathbb{E}\big[\sum_{i=1}^{n-1}c_iX_i\big]=\sum_{i=1}^{n-1}c_i\mathbb{E}[X_i]$。
• 归纳步骤：把 $n$ 项拆成”前 $n-1$ 项之和”加”第 $n$ 项”。令 $S=\sum_{i=1}^{n-1}c_iX_i$，则

• 再用一次归纳假设处理 $\mathbb{E}[S]$，用定理 20.3 的数乘部分处理 $\mathbb{E}[c_nX_n]$：

【证明机制解说】：注意归纳步骤里 $\mathbb{E}[S+c_nX_n]$ 用定理 20.3 时，$S$ 与 $X_n$ 是任意两个随机变量（可能是相关的、可能是同一个），定理 20.3 依然无条件适用——这就是为什么归纳能一路推下去而不需要任何额外假设。若线性性需要独立性，归纳步骤就必须假设 $S\perp X_n$，而 $S$ 是前 $n-1$ 项的混合，”$S$ 与 $X_n$ 独立”远比”每个 $X_i$ 两两独立”更强，定理也就大幅削弱了。

反例（条件不可省的另一面）：既然加法不需要独立性，那”乘法也线性”是不是也成立？即 $\mathbb{E}[XY]=\mathbb{E}[X]\mathbb{E}[Y]$？不成立。取 $X\sim\mathrm{Bernoulli}(1/2)$，令 $Y=X$（同一个变量）。则 $XY=X^2=X$，$\mathbb{E}[XY]=\mathbb{E}[X]=1/2$，而 $\mathbb{E}[X]\mathbb{E}[Y]=(1/2)^2=1/4$。$1/2\ne1/4$（脚本验算 ✔）。同理 $\mathbb{E}[1/X]\ne1/E[X]$：取 $X$ 以概率 $1/2$ 取 $1$、概率 $1/2$ 取 $2$，则 $\mathbb{E}[1/X]=\frac12\cdot1+\frac12\cdot\frac12=\frac34$，而 $1/\mathbb{E}[X]=1/1.5=\frac23$，两者不等。线性性只管”和差与常数倍”，绝不可越界用到乘积、倒数、平方上。

定理 20.5（二项分布的期望）：设 $X\sim\mathrm{Bin}(n,p)$，则 $\mathbb{E}[X]=np$。

证明策略：指示变量分解 + 线性性（主算法）；同时给出定义式直接求和作为对照算法，用”繁琐程度”凸显线性性的价值。这是本讲的旗舰例子。

逐步推导（算法一：指示变量法，3 行）：

• 第一步：把”抛 $n$ 次硬币数正面”这件事重新叙述为”数 $n$ 次伯努利试验中成功的次数”，从而写成

为什么这个等式成立？因为左边的 $X(\omega)$ 是”序列 $\omega$ 中正面的个数”，右边的 $\sum_i I_i(\omega)$ 恰好是”对每个位置检查一次，是正面就记 1”，两者数的是同一批东西。这与定理 20.1 第五步”$X$ 是函数”式的推理同源。

• 第二步：$\mathbb{E}[I_i]=\Pr[\text{第 } i \text{ 次为正面}]=p$。（依据：定理 20.2。）
• 第三步：$\mathbb{E}[X]=\sum_{i=1}^n\mathbb{E}[I_i]=\sum_{i=1}^n p=np$。（依据：定理 20.4。）$\blacksquare$

逐步推导（算法二：定义式直接求和，作为对照）：

• 第一步：由 Lecture 19 的结论，$\Pr[X=k]=\binom{n}{k}p^k(1-p)^{n-k}$，于是

• 第二步：$k=0$ 项为 $0$，从 $k=1$ 起求和。利用吸收恒等式 (absorption identity) $k\binom{n}{k}=n\binom{n-1}{k-1}$：

• 第三步：提出一个 $p$，并把 $p^{k-1}$、$(1-p)^{(n-1)-(k-1)}$ 重新配对；令 $j=k-1$：

• 第四步：右端的和恰好是 $\mathrm{Bin}(n-1,p)$ 全部概率之和，由归一性等于 $1$（这本身是二项式定理的一个概率证明）。故 $\mathbb{E}[X]=np$。$\blacksquare$

数值对照：$n=5,p=0.3$。算法二求和：$\sum_{k=0}^{5}k\binom5k 0.3^k0.7^{5-k}=1.5000000000$；算法一：$np=1.5$。脚本验算完全一致 ✔。

【证明机制解说】：算法一的关键在于换一个”记账方式”。原来的记法是”先按正面的总个数分组，再数每组有多少样本点”——这需要 $\binom nk$，于是要跟阶乘搏斗。新的记法是”按位置逐个数”——每个位置贡献一个 $0/1$，期望就是它的概率。换个记账方式，同一个量就从”需要组合恒等式”变成”只需要把 $n$ 个 $p$ 加起来”。 这也是官方 Note 说”用定义会更难”的确切含义：不是不能做，而是做完之后你还得额外证明一个组合恒等式。

值得强调的是，算法一根本不需要 $I_i$ 之间独立。这里 $I_1,\dots,I_n$ 确实独立（因为硬币抛掷独立），但即使不独立（比如从有限总体里不放回抽样，对应超几何分布），$\mathbb{E}[X]=np$ 这部分推导仍然成立——当然那时 $X$ 不再是二项分布。这正是线性性的”免费午餐”性质的又一次体现。

定理 20.6（LOTUS，无意识统计学家定律）：设 $X$ 是取值集合为 $\mathcal{X}$ 的离散随机变量，$g:\mathcal{X}\to\mathbb{R}$ 为任意函数。则

证明策略：按 $g$ 的取值分组求和（本质上是一次”划分式”双计数）。选这个策略是因为 $g$ 未必是单射，多个 $x$ 可能映到同一个 $y$，所以必须先按 $y$ 把 $x$ 归类。

逐步推导：

• 第一步：令 $Y=g(X)$。由随机变量的复合定义，$Y$ 是同一概率空间上的随机变量，$Y(\omega)=g(X(\omega))$。
• 第二步：求 $Y$ 的分布。事件 $\{Y=y\}$ 等价于 $\{X\in g^{-1}(y)\}$，其中 $g^{-1}(y)=\{x:g(x)=y\}$。故

注意：当 $g^{-1}(y)=\varnothing$ 时该和为 $0$，无碍。

• 第三步：代入期望定义式：

• 第四步：把 $y$ 移入内层，并在内层把 $y$ 换成 $g(x)$（因为内层所有 $x$ 都满足 $g(x)=y$）：

• 第五步：每个 $x\in\mathcal{X}$ 落在恰好一个集合 $g^{-1}(y)$ 中，所以即”遍历所有 $y$ 与其原像”等价于”直接遍历所有 $x$”，每项不重不漏：

【证明机制解说】：这个证明与定理 20.1 的第五步是同一个招式：用集合族的”划分”性质把双重求和压成单重求和。区别只在于，定理 20.1 划分的是样本空间 $\Omega$（按 $X$ 的取值），这里划分的是 $X$ 的取值集合 $\mathcal{X}$（按 $g$ 的取值）。“找一个划分”是概率论求和化简的通用套路，后面证明卷积公式时还会见到第三次。

LOTUS 的实际价值：它把 $\mathbb{E}[X^2]$、$\mathbb{E}[X(X-1)]$、$\mathbb{E}[e^{tX}]$ 这类量变成”直接在 $X$ 的分布上求和”，完全绕开求 $g(X)$ 的分布。Lecture 21–22 计算方差时会反复使用 $\mathbb{E}[X^2]=\sum_x x^2\Pr[X=x]$。

定理 20.7（独立的随机变量，乘积期望可乘）：若 $X\perp Y$（独立），则 $\mathbb{E}[XY]=\mathbb{E}[X]\,\mathbb{E}[Y]$。反之不成立。

证明策略：直接证明 + 分离双重求和。核心是使用联合分布 (joint distribution) 与独立性的定义 $\Pr[X=a,Y=b]=\Pr[X=a]\Pr[Y=b]$，把二重和拆成两个一重和的乘积。

逐步推导：

• 第一步：对函数 $g(a,b)=ab$ 使用 LOTUS 的二维版本（或直接用 $\mathbb{E}[XY]=\sum_{a,b}ab\Pr[X=a,Y=b]$，这本身可由定理 20.1 的样本点形式逐点推出）：

• 第二步：关键一步——用独立性把联合概率分解：

• 第三步：把 $a\Pr[X=a]$ 与 $b\Pr[Y=b]$ 分离。注意 $\Pr[X=a]$ 与内层指标 $b$ 无关，可提出内层：

• 第四步：内层就是 $\mathbb{E}[Y]$（与 $a$ 无关的常数），提出外层：

【证明机制解说】：第三步的分离之所以能成功，全靠第二步的分解把 $\Pr[X=a,Y=b]$ 变成了”只含 $a$ 的因子 × 只含 $b$ 的因子”。这是可分离性 (separability) 的标准用法：二重和若能写成 $u_a v_b$ 的形式，就能拆成两个一重和的乘积。请把这条与定理 20.3 的证明对照——那里我们没有做任何分解，而是逐点相加。两个证明的形状完全不同，因为它们处理的运算不同（加法 vs 乘法）。

反例（反之不成立）：存在 $X,Y$ 不独立但 $\mathbb{E}[XY]=\mathbb{E}[X]\mathbb{E}[Y]$。取 $X$ 在 $\{-1,0,1\}$ 上均匀分布，令 $Y=\vert X\vert $。

• $Y$ 完全由 $X$ 决定（$X=1\Rightarrow Y=1$），显然不独立。
• $\mathbb{E}[X]=\frac13(-1)+\frac13(0)+\frac13(1)=0$。
• $\mathbb{E}[Y]=\frac13(1)+\frac13(0)+\frac13(1)=\frac23$。

• $\mathbb{E}[XY]=\mathbb{E}[X\cdot\vert X\vert ]=\frac13(-1)+\frac13(0)+\frac13(1)=0$。

  于是 $\mathbb{E}[XY]=0=0\cdot\frac23=\mathbb{E}[X]\mathbb{E}[Y]$ 成立，但 $X$ 与 $Y$ 不独立（脚本验算 ✔）。逐格检查也能看出：$\Pr[X=0,Y=0]=\frac13$，而 $\Pr[X=0]\Pr[Y=0]=\frac13\cdot\frac13=\frac19\ne\frac13$。

结论：$\mathbb{E}[XY]=\mathbb{E}[X]\mathbb{E}[Y]$ 是独立的必要不充分条件的”影子”——它是独立性的一个推论，不是等价刻画（等价刻画要靠 Lecture 22 的协方差/相关性，且即便 $\operatorname{Cov}=0$ 也仍不等价于独立）。

定理 20.8（收集者问题，Coupon Collector）：设有 $n$ 种优惠券，每买一盒谷物随机得到其中一种（均匀、独立）。设 $T$ 为集齐全部 $n$ 种所需盒数。则

证明策略：指示变量分解的升级版——按”阶段”分解 (staged decomposition)。$T$ 不能直接写成 $n$ 个指示变量之和（它是”次数”而非”计数”），但可以写成 $n$ 个几何随机变量之和，每个阶段是一个独立的”等第一次成功”过程。然后对各阶段用几何分布的期望 $1/p$，最后用线性性相加。

逐步推导：

• 第一步：划分阶段。 定义”第 $i$ 阶段”为：已经集齐了 $i-1$ 种不同的券之后，从那一刻起，直到第一次买到第 $i$ 种新券为止所购买的盒数。令 $X_i$ 为该阶段消耗的盒数。因为一条完整的购买记录被这些阶段首尾相接地切成 $n$ 段，故

（$i=1$ 时”已有 0 种”，第一盒必然是新的，故 $X_1=1$ 必然发生。）

• 第二步：确定各阶段的成功概率。 进入第 $i$ 阶段时已有 $i-1$ 种不同的券，此时还有 $n-(i-1)=n-i+1$ 种是”新的”。每次买盒独立均匀，所以买到新券的概率为

具体列出 $n=10$ 时的 $p_i$：$p_1=1,\ p_2=0.9,\ p_3=0.8,\ p_4=0.7,\ p_5=0.6,\ p_6=0.5,\ p_7=0.4,\ p_8=0.3,\ p_9=0.2,\ p_{10}=0.1$。

• 第三步：识别几何分布。 在阶段 $i$ 内的每一次购买，都可看作一次”成功概率 $p_i$”的伯努利试验，且各次独立。$X_i$ 就是”直到首次成功所需的试验次数”，故

（依据：Lecture 19 关于几何分布的结论 $\mathbb{E}[X]=1/p$，可由尾和公式 $\mathbb{E}[X]=\sum_{i\ge1}\Pr[X\ge i]=\sum_{i\ge1}(1-p)^{i-1}=1/p$ 得出。）

• 第四步：用线性性相加。 注意各 $X_i$ 之间并不独立吗？其实各阶段面对的是同一批券的状态，但因为每个阶段的成功概率只取决于”已集齐的种类数”（这是确定性的 $i-1$，不随机），阶段的划分是确定性的，所以每个 $X_i$ 的分布确实就是 $\mathrm{Geometric}(p_i)$，而且线性性连独立性都不需要，可以直接相加：

最后一步做了换元 $j=n-i+1$（当 $i$ 从 $1$ 走到 $n$，$j$ 从 $n$ 走到 $1$，恰好遍历 $1,\dots,n$）。

• 第五步：估计调和数。 用积分比较（见下）得 $\ln n<H_n<\ln n+1$，故

更精细的近似是 $H_n\approx\ln n+\gamma$（$\gamma\approx0.5772$），给出 $\mathbb{E}[T]\approx n(\ln n+\gamma)$。$\blacksquare$

调和数夹逼的推导：对 $x\in[k,k+1]$ 有 $\frac{1}{k+1}\le\frac1x\le\frac1k$。在 $[k,k+1]$ 上积分得 $\frac{1}{k+1}\le\int_k^{k+1}\frac{dx}{x}\le\frac1k$。对 $k=1,\dots,n-1$ 求和：

即 $\ln n<H_n$；另一侧用 $\int_1^{n+1}\frac{dx}{x}=\ln(n+1)$ 与右不等式得 $H_n\le 1+\ln n$。合起来即 $\ln n<H_n<\ln n+1$ ✔（数值校验：$n=1000$ 时 $6.9078<7.4855<7.9078$ ✔）。

脚本验算（必做）：理论值 $\mathbb{E}[T]=nH_n$ 与 Monte Carlo 模拟（每种 $n$ 跑 $2\times10^5$ 次实验）：

另有 $n=100$ 时 $nH_{100}=518.7378$，而 $n(\ln n+\gamma)=518.24$，近似极好（官方 Note 也给出”约 518 盒”）✔。

$n=10$ 的逐阶段累积期望表（脚本精确计算）：

注意这个表的”形状”：期望消耗几乎全部集中在最后几个阶段——集齐 9 种只花了约 $19.29$ 盒，而最后一种还要再等 $10$ 盒。这种”末尾长尾”是所有收集类任务的通用规律。

【证明机制解说】：收集者问题的分解与二项分布的分解形状相同、通道不同：二项分布是”$n$ 个指示变量计数相加”，收集者是”$n$ 个几何变量时长相加”。共同点是——都在找”把总时间/总量切成确定性小片”的划分方式。这里的关键洞察是：虽然券的种类是随机的，但”已集齐 $i-1$ 种”这个阶段标签是确定性的，因此每段的成功概率固定为 $p_i$，几何分布的结论可以原样套用。如果阶段划分本身依赖随机结果（比如”直到某张特定券出现为止”），这个分解就会失效。

定理 20.9（空箱数目的期望）：把 $m$ 个球独立均匀地投入 $n$ 个箱。设 $Y$ 为空箱个数，则

特别地，当 $m=n$ 时 $\mathbb{E}[Y]=n(1-1/n)^n\approx n/e\approx0.368n$。

证明策略：指示变量分解 + 线性性——这是”把全局复杂量拆成局部简单量之和”的教科书示范。直接求 $Y$ 的分布是灾难性的（官方 Note 说”这个分布可怕到难以想象”），但期望可以一行搞定。

逐步推导：

• 第一步：为每个箱子配一个指示变量：

为什么这个等式恒成立？对任何样本点 $\omega$，”空箱个数”就是”在 $n$ 个箱子里逐一检查、是空箱就记 1 的分值之和”。这与定理 20.1 第五步的”函数性”论证同构。

• 第二步：求单个期望。第 $j$ 箱为空 $\iff$ 所有 $m$ 个球都躲开了它。每个球躲开第 $j$ 箱的概率是 $1-1/n$，且各球独立，故

（依据：定理 20.2 + 独立事件乘积法则。这里确实用到了球的独立性——因为要算的是一个交事件的概率——这与前面”线性性不需要独立”并不矛盾：独立性的需求出现在”算单个指示变量的期望”这一步，而不是”把期望加起来”那一步。）

• 第三步：线性性求和：

• 第四步（$m=n$ 时的渐近）：由标准极限 $(1+c/n)^n\to e^{c}$（取 $c=-1$）得 $(1-1/n)^n\to1/e$，故 $\mathbb{E}[Y]\approx n/e\approx0.368n$。官方 Note 提醒这个近似对小 $n$ 也很好用：$n=20$ 时 $(1-1/20)^{20}\approx0.3585$，已经离 $1/e\approx0.3679$ 不远。

数值验算：

（模拟 $2\times10^4$ 次，脚本验证 ✔。”投 $1000$ 个球进 $1000$ 个箱，期望约 $368$ 个空箱”与官方 Note 完全一致。）

推论：非空箱数的期望为 $n-\mathbb{E}[Y]=n\big[1-(1-1/n)^n\big]$。$n=m=10$ 时是 $10-3.4868=6.5132$ 个非空箱——也就是说，投 $10$ 个球进 $10$ 个箱，平均有 $3.5$ 个箱子白白空着。

定理 20.10（哈希碰撞数的期望）：设 $m$ 个键独立均匀地哈希到 $n$ 个槽位。设 $C$ 为发生碰撞的无序键对数目（即落在同一槽位的键对）。则

特别地，当 $m=n$ 时 $\mathbb{E}[C]=\frac{n(n-1)}{2n}=\frac{n-1}{2}$。

证明策略：按”对”（pair）做指示变量。$C$ 是”键对”的函数而非”键”的函数，所以指示变量要下在对上。这体现了指示变量技巧的灵活性：你可以自由选择”用什么单位来分解”。

逐步推导：

• 第一步：把 $\binom m2$ 个键对任意编号为 $1,2,\dots,\binom m2$。令 $C_i$ 表示”第 $i$ 个键对的两个键落在同一槽位”这一事件，取

• 第二步：对任意一个固定键对（比如键 $u$ 与键 $v$），求 $\Pr[C_i]$。先看键 $u$ 落在哪一槽（任意，无约束），再看键 $v$：$v$ 独立均匀地落在 $n$ 个槽中，恰有一个槽与 $u$ 相同，故

• 第三步：线性性求和：

数值验算：$m=n=10$ 时 $\mathbb{E}[C]=\frac{10\cdot9}{2\cdot10}=4.5$；$m=n=100$ 时 $49.5$；$m=n=1000$ 时 $499.5$（脚本 ✔）。一般地 $\mathbb{E}[C]=\frac{n-1}{2}\approx n/2$：哪怕把 $n$ 个键塞进 $n$ 个槽，平均也只有约 $n/2$ 对碰撞——碰撞的数量与”表的规模”同阶，而不是与”可能的对数 $\binom n2$”同阶。这是后面负载均衡分析能有好结果的根本原因。

【证明机制解说】：这里有一个非常值得警惕的细节——各个 $I_{C_i}$ 绝不独立。若键对 $(u,v)$ 碰撞且 $(v,w)$ 碰撞，则 $(u,w)$ 必然碰撞（三个键同槽），这是一条强相关的推理链。但我们完全不需要它们独立，因为线性性无条件成立。这就是”免费午餐”在本讲中最闪耀的一次应用：相关性强到极致，期望照样可以直接相加。如果这里错以为”需要独立”，整条路就走不通了。

哈希的容量问题（哈希表能存多少键）：设碰撞概率容忍度为 $\varepsilon\in(0,1)$，问最多能存多少键使”无碰撞”概率 $\ge1-\varepsilon$？

• 思路一：联合界 (union bound)。 令 $A$ 为”至少存在一对碰撞”，则 $A=\bigcup_{i=1}^{\binom m2}C_i$。由 Lecture 18 的联合界 $\Pr[\bigcup_i C_i]\le\sum_i\Pr[C_i]$，

要 $\Pr[A]\le\varepsilon$，只需 $\frac{m^2}{2n}\le\varepsilon$，即 $m\le\sqrt{2\varepsilon n}$。取 $\varepsilon=1/2$ 得 $m\le\sqrt n$。结论：要让”无碰撞”以高概率成立，哈希表大小需约为待存集合大小的平方。

• 思路二：精确计算 + 对数近似。 无碰撞 $\iff$ $m$ 个球落入 $m$ 个不同的箱。计数有利样本点：第 1 个球有 $n$ 种选择，第 2 个球有 $n-1$ 种（不能与第 1 个同箱），……，第 $m$ 个球有 $n-m+1$ 种。故

取对数（合法：$\ln$ 可逆且单调）：

其中用了泰勒展开 $\ln(1-x)=-x-\frac{x^2}{2}-\frac{x^3}{3}-\cdots\approx-x$（对小的 $x$）。于是

要 $e^{-m^2/(2n)}\ge1-\varepsilon$，即 $\frac{m^2}{2n}\le\ln\frac{1}{1-\varepsilon}$，故

$\varepsilon=1/2$ 时系数为 $\sqrt{2\ln2}=\sqrt{1.38629}=1.1774$，即 $m\approx1.177\sqrt n$。$\varepsilon=1/20$ 时系数 $\sqrt{2\ln(20/19)}=\sqrt{0.10259}=0.3203$，即 $m\approx0.32\sqrt n$。

数值验算（脚本精确枚举）：

与官方 Note 的表完全吻合。另：生日悖论对应的正是 $n=365$ 的情形——精确算得 $\Pr[\text{至少一对同生日}]$ 在 $m=23$ 时为 $0.5073>1/2$，$m=60$ 时为 $0.9941>0.99$ ✔。直觉上”$23/365\approx6\%$”完全错，因为碰撞是成对事件，对数是 $\binom m2\sim m^2/2$，随 $m$ 平方增长。

临界值 $m_0=O(\sqrt n)$ 不可改进：既然精确式也给出 $m\approx1.177\sqrt n$，联合界给出的 $O(\sqrt n)$ 阶就是最优阶——存在碰撞的概率本质上是 $\Theta(m^2/n)$，这是”$\binom m2$ 个对数 × 每对 $1/n$”结构的必然结果。这也再次印证 $\mathbb{E}[C]=\binom m2/n$ 这条期望公式的深刻：碰撞数量的期望就是那个”本质上决定一切”的量。

负载均衡（Load Balancing）：$m=n$ 个作业随机指派到 $n$ 个处理器，求最小 $k$ 使 $\Pr[\text{最大负载}\ge k]\le1/2$。

证明策略：“不问难题，先问简单题”——不直接分析”最大负载”这个依赖全部 $n$ 个箱子的复杂事件 $A_k$，而是先分析单个箱子的负载事件 $A_k(j)=\{$第 $j$ 箱负载 $\ge k\}$，再用联合界把单个箱子的结论搬回全局。这个”换问题”的思路是工程概率论的核心美学。

逐步推导（粗界）：

• 第一步：把目标拆解。注意 $A_k=\bigcup_{j=1}^n A_k(j)$（只要存在某个箱子负载 $\ge k$，最大负载就 $\ge k$）。由联合界，

最后一步用了对称性：$n$ 个箱子完全同构。

• 第二步：归约到”只需单箱概率小到 $1/(2n)$”。若能让 $\Pr[A_k(1)]\le\frac{1}{2n}$，则 $\Pr[A_k]\le n\cdot\frac{1}{2n}=\frac12$ ✔。
• 第三步：再次使用联合界，这次用在”哪些球在箱 1 里”。若箱 1 有 $\ge k$ 个球，则存在某个含 $k$ 个球的集合 $S$ 使 $S$ 中所有球都落在箱 1。故 $\{A_k(1)\}\subseteq\bigcup_{\vert S\vert =k}B_S$，其中 $B_S=\{$所有 $S$ 中球都落进箱 1$\}$。于是

（最后一个等式：每个 $B_S$ 是 $k$ 个确定球同落箱 1，概率为 $(1/n)^k$；共有 $\binom nk$ 个 $S$。）

• 第四步：化简并用 Stirling 估计。注意

要 $\Pr[A_k(1)]\le\frac{1}{2n}$，只需 $\frac{1}{k!}\le\frac1{2n}$，即 $k!\ge2n$。用 Stirling 近似 $\ln k!\approx k\ln k-k$（更精确的写法是 $\ln k!\ge k\ln k-k$），令其 $\approx\ln(2n)$，解得

• 第五步（更紧的界）。 用二项分布的精确表达：

其中第三步用了标准估计 $\binom nj\le(ne/j)^j$，并把 $(1-1/n)^{n-j}\le1$ 丢掉（丢掉只会放大上界，是合法的”松绑”）；第四步把所有项按几何级数（公比 $\le e/k$，要求 $k\ge2e$）放大。于是要 $\Pr[A_k(1)]\le\frac{1}{2n}$，只需

两边取对数：$k(\ln k-1)\ge\ln(4n)$。数表验算：

更简单的可读估计是 $k\approx\ln(4n)$（对 $n\ge405$ 就够用）；$n$ 极大时用 $k\approx\frac{2\ln n}{\ln\ln n}$ 更贴切。$\blacksquare$

数值验算与界有多松：对 $n=1000$，界给出 $k\le8$；Monte Carlo 模拟（$2\times10^4$ 次）显示 $\Pr[\text{最大负载}\ge k]$ 为

即真实临界值约为 $k=6$（$\Pr[\max\ge6]=0.4435\le1/2$，故 $\Pr[\max\le5]=0.5565\ge1/2$），而我们的上界给出的是 $k\le8$。界是保守的（诚实但偏松），因为推导中用了两次联合界 + 一次 Stirling + 一次几何级数放大，每步都往”更安全”的方向走。模拟的均值也是佐证：$n=1000$ 时最大负载均值 $5.515$，中位数 $5$，$95$ 分位 $7$——所有值都远小于 $\ln n\approx6.9$ 的粗估量级，更远小于 $n$。

工程结论（官方 Note 的”卖点”）：美国人口约 $3.5$ 亿。寄出 $3.5$ 亿封地址完全随机的广告邮件，则以至少 $1/2$ 的概率，全国没有任何一个人收到超过约十来封。这就是”随机化 + 事后容忍波动”相对于”中心化精确调度”的威力：零通信开销，最坏负载只是 $\Theta(\ln n/\ln\ln n)$。

与经典问题的联系

1. 哈希表（Hash Table）的容量设计

• 实际背景：哈希表把键从大宇宙 $U$（比如全美 2.5 亿人名）映射到小表 $T$（$n$ 个槽），冲突的键挂在同一槽的链表里。$\textsc{Delete}$ 与 $\textsc{Member}$ 的耗时正比于链表长度，所以链长（= 负载）是性能命脉。
• 数学建模：把”哈希函数打乱输入”建模为随机函数——每个键独立均匀地落到某个槽。这就是球的投箱模型。
• 方案设计与正确性：若要求”无冲突”以概率 $\ge1-\varepsilon$ 成立，则 $m\le\sqrt{2\ln\frac1{1-\varepsilon}}\sqrt n=O(\sqrt n)$（定理 20.10 之后的分析），且这个 $O(\sqrt n)$ 阶是紧的（生日悖论现象）。实践中不这么用——因为负载均衡分析告诉我们，即使 $m=n$，最大链长也只有 $\Theta(\ln n/\ln\ln n)$，于是”允许冲突 + 链表/开放寻址”的方案远比”把表放大到 $n^2$”经济。
• 期望的用处：定理 20.10 直接给出 $\mathbb{E}[\text{碰撞对数}]=\binom m2/n$，用一个两行的计算替代了原本需要对所有 $n^m$ 种落点计数的工作。

2. 分布式系统的负载均衡（Load Balancing）与”随机复用”

• 实际背景：$m$ 个作业、$n$ 个处理器，精确均分需要中心调度器或大量通信，代价高昂。
• 数学建模：每个作业独立均匀随机选处理器，即投箱模型。
• 方案与保证：不通信，最大负载以至少 $1/2$ 概率不超过 $k_0$，其中 $k_0$ 由 $(e/k)^k\le1/(4n)$ 定出，对 $n=10^6$ 只有 $k_0=11$，对 $n=10^9$ 也只有十几。
• 推广视野：CS70 官方 Note 指出这是随机复用 (stochastic multiplexing) 的雏形——”潜在需求总量巨大，但实际同时到达的需求是随机的”，因此可以超售资源。官方提到 EECS 122/168 与 EECS 126 会深入展开。这就是”概率让你可以不为最坏情况买单”的工程哲学。

3. 纠错码的冗余量选择（与 Lecture 19 的呼应）

• 实际背景：把 $n$ 个包编成 $n+k$ 个包，使收到任意 $n$ 个即可重建原数据（Lecture 8 的纠错码）。
• 数学建模：若每个包独立地以概率 $p$ 丢失，则收到的包数 $X\sim\mathrm{Bin}(n+k,1-p)$。
• 方案设计：成功解码概率为 $\Pr[X\ge n]=\sum_{i=n}^{n+k}\binom{n+k}{i}(1-p)^ip^{n+k-i}$。给定 $n,p$，选 $k$ 使该概率 $\ge0.99$。
• 本讲的作用：一旦用定理 20.5 知道 $\mathbb{E}[X]=(n+k)(1-p)$，就能立刻反推需要多少冗余：要让期望收到数至少 $n$，需 $(n+k)(1-p)\ge n$，即 $k\ge\frac{np}{1-p}$ ——一步给出 $k$ 的尺度，剩下的精调交给 Lecture 23 的集中不等式（切尔诺夫界）来做。

4. 算法分析中的”期望时间复杂度”

• 大量随机化算法（随机快排、哈希、随机游走采样）的复杂度都是以”指示变量 + 线性性”的方式分析的：把”比较次数”拆成”每一对元素是否被比较”，把”访问次数”拆成”每个位置是否被访问”。本讲的定理 20.2 与定理 20.10 是这套方法论的模板。

与其他讲次的关联

• 承接 Lecture 14（计数）/ Lecture 15（概率公理）：期望定义里的 $\sum_a a\Pr[X=a]$ 是”加权计数”；定理 20.8 的 $\binom nk$ 与定理 20.10 的 $\binom m2$ 直接来自 Lecture 14 的组合计数。定理 20.1 证明中”事件族 $\{X=a\}$ 构成样本空间的划分”用的正是 Lecture 15 建立的可加性公理。
• 承接 Lecture 18（独立性与事件组合）：定理 20.9 中算 $\Pr[\text{第 }j\text{ 箱为空}]=(1-1/n)^m$ 用的是 Lecture 18 的独立事件乘积法则；哈希容量分析的第一步用的正是 Lecture 18 的联合界 (union bound) $\Pr[\bigcup A_i]\le\sum\Pr[A_i]$。请注意区分：联合界用在这一步是”事件层面”，线性性用在期望求和是”随机变量层面”，两条通道互不干涉。
• 承接 Lecture 19（随机变量与离散分布）：本讲是 Lecture 19 的直接延续——19 讲回答”$X$ 的分布是什么”，20 讲回答”如何用一个数概括它”。定理 20.5 用的 $\mathrm{Bin}(n,p)$ 分布、定理 20.8 用的 $\mathrm{Geometric}(p)$ 期望 $1/p$（含尾和公式 $\mathbb{E}[X]=\sum_{i\ge1}\Pr[X\ge i]$），都在 Lecture 19 与配套 Note（Note 19）中建立。
• 通向 Lecture 21（联合分布与随机变量独立性）：定理 20.7 的证明已经提前使用了联合分布 $\Pr[X=a,Y=b]$ 与独立性的乘法分解，Lecture 21 将把这两个概念正式体系化，并给出卷积公式处理”独立随机变量之和”的分布。
• 通向 Lecture 22（方差与协方差）：Theorem 20.7 中那个”$\mathbb{E}[XY]-\mathbb{E}[X]\mathbb{E}[Y]$”的量正是协方差；Lecture 22 会证明 $\operatorname{Var}(X+Y)=\operatorname{Var}(X)+\operatorname{Var}(Y)+2\operatorname{Cov}(X,Y)$，并指出方差相加需要独立，而期望相加不需要——这个对比正是本讲最需要记住的分界线。
• 通向 Lecture 23（集中不等式）：本讲反复出现”期望不等于典型值”的伏笔（骰子期望 $3.5$ 取不到；随机游走 $\mathbb{E}[S_n]=0$ 但粒子跑得远）。官方 Note 明确说”期望有多典型”是后续要回答的重要问题——Lecture 23 的马尔可夫界 $\Pr[X\ge a]\le\mathbb{E}[X]/a$ 只需期望就能给出最粗的集中保证，切比雪夫界则需要 Lecture 22 的方差。
• 回连 Lecture 4–6（数论与密码）：哈希函数”模 $m$ 归约到槽位”正是 Lecture 4 的剩余类语言；”为什么模质数分布更均匀”也来自 $\mathbb{Z}_p$ 结构的整齐性。

关键要点

1. 期望 = 概率加权的平均值 = 分布的质心。定义式 $\mathbb{E}[X]=\sum_a a\Pr[X=a]$，等价的样本点式 $\mathbb{E}[X]=\sum_\omega X(\omega)\Pr[\omega]$。期望不必是 $X$ 能取到的值（骰子 $3.5$），也可能不存在（绝对收敛是前提）。
2. 指示变量定律 $\mathbb{E}[I_A]=\Pr[A]$ 是全部技巧的引擎。凡是”数某种东西有多少个”的随机量，都先努力写成 $\sum_i I_i$ 的形式；写出来后求期望就等于把一串概率加起来。
3. 线性性无条件成立：$\mathbb{E}[\sum_i c_iX_i]=\sum_i c_i\mathbb{E}[X_i]$，不需要任何独立性。这是整门课最锋利的免费午餐。相应地，它只管加法与常数倍：$\mathbb{E}[XY]\ne\mathbb{E}[X]\mathbb{E}[Y]$、$\mathbb{E}[1/X]\ne1/\mathbb{E}[X]$、$\mathbb{E}[g(X)]\ne g(\mathbb{E}[X])$（凸性不等式是另一回事）。
4. $\mathbb{E}[XY]=\mathbb{E}[X]\mathbb{E}[Y]$ 需要独立，且反向不成立。反过来，$\operatorname{Cov}(X,Y)=0$ 也不能推出独立（Lecture 22）。
5. 三大应用的具体公式必须能默写：
   • 二项分布 $\mathbb{E}[\mathrm{Bin}(n,p)]=np$（指示变量 3 行 vs 定义式代数一套）；
   • 收集者问题 $\mathbb{E}[T]=nH_n\approx n\ln n$（按阶段分解成 $n$ 个几何变量）；
   • 投箱模型 $\mathbb{E}[\text{空箱}]=n(1-1/n)^m\approx ne^{-m/n}$，$\mathbb{E}[\text{碰撞对}]=\binom m2/n$，哈希容量 $m\approx1.177\sqrt n$，最大负载 $\Theta(\ln n/\ln\ln n)$。
6. 黄金法则：“全局难算 ⇒ 拆成局部之和（指示变量），再逐项求期望”。拆分的单位（球、箱、键对、阶段）可以自由选择，选得好就两行解决，选不好就寸步难行。

常见误区与注意事项

1. 以为线性性需要独立性。 这是最高频、最致命的误解。$\mathbb{E}[X+Y]=\mathbb{E}[X]+\mathbb{E}[Y]$ 对任意 $X,Y$ 成立，包括 $Y=X$、包括强相关的变量。把”线性性”和”乘法法则”分清楚：加法通道免费，乘法通道收费（要用独立来付费）。
2. 把线性性滥用到了乘积上。 看到 $\mathbb{E}[(X_1+\cdots+X_n)^2]$ 就写成 $(\mathbb{E}[X_1]+\cdots+\mathbb{E}[X_n])^2$ —— 错。展开平方后交叉项 $\mathbb{E}[X_iX_j]$ 需要 Lecture 22 的工具（独立时才 $=\mathbb{E}[X_i]\mathbb{E}[X_j]$）。
3. 期望当作”必然值”。 骰子的期望是 $3.5$，但它一次都取不到；美国人均收入是中位数收入的两倍，但”平均人”不存在。期望是长期平均/质心，不是典型值。 判”某个取值会不会出现”必须看分布（支撑集），不能看期望。
4. 忘记期望可能发散。 在写 $\mathbb{E}[X]=\sum_a a\Pr[X=a]$ 并做代数变形前，先确认绝对收敛。反例见”注意二”中的 $X$ 以 $2^{-k}$ 取 $2^k$。
5. 以为 $\mathbb{E}[g(X)]=g(\mathbb{E}[X])$。 即”期望可以穿过函数”。这只有在 $g$ 是仿射函数（$g(x)=ax+b$）时才成立——这恰恰就是线性性的内容。对 $g(x)=x^2$、$g(x)=1/x$、$g(x)=e^x$ 一律不成立。取 $X$ 均匀在 $\{1,2\}$：$\mathbb{E}[X^2]=2.5$，$(\mathbb{E}[X])^2=2.25$。
6. 在求”指示变量的期望”时误以为也要用到变量独立性。 恰恰相反：算 $\mathbb{E}[I_j]=1-\Pr[\text{所有球躲开第 }j\text{ 箱}]$ 时用的是球之间的独立性（交事件概率分解），以及联合界那样的”和事件”上界。把”哪一步需要独立”与”哪一步不需要”对齐，是本章最需要练的手感。
7. 调和数的量级记错。 $H_n$ 是 $\Theta(\ln n)$，不是 $\Theta(\log_2 n)$（差一个常数因子 $\ln 2$），更不是 $\Theta(n)$。收集者问题的期望是 $n\ln n$ 而不是 $n^2$ 或 $n\log_2 n$。这个 $\ln$ vs $\log_2$ 的差别在 CS 语境里经常被忽略，但代进公式会差 $\ln2\approx0.693$ 倍。
8. 把最大化/最小化与期望交换。 $\mathbb{E}[\max_j L_j]\ge\max_j\mathbb{E}[L_j]$ 一般严格大于（$n=1000$ 时单箱期望是 $1$，但最大负载期望约 $5.5$）。“平均的最大” ≠ “最大的平均”，分析最大负载时必须走联合界那条路。

思考题（带答案）

Q1.（计算题） 把 $10$ 个球独立均匀地投入 $10$ 个箱。求：(a) 空箱数的期望；(b) 非空箱数的期望；(c) 发生碰撞的无序球对数目的期望；(d) 第 1 个箱恰好有 $3$ 个球的概率；(e) 第 1 个箱与第 2 个箱都为空箱的概率。

Q2.（概念/证明题） 判断下列命题真假，为真者给出证明，为假者给出反例：

(a) 若 $X,Y$ 是同一概率空间上的随机变量且 $\mathbb{E}[X+Y]=\mathbb{E}[X]+\mathbb{E}[Y]$，则 $X\perp Y$。

(b) 若 $X\perp Y$，则 $\mathbb{E}[X^2Y^2]=\mathbb{E}[X^2]\mathbb{E}[Y^2]$。

(c) 若 $\mathbb{E}[XY]=\mathbb{E}[X]\mathbb{E}[Y]$，则 $X\perp Y$。

(d) 对任意随机变量 $X$ 与任意 $n\ge1$，$\mathbb{E}[X^n]\ge(\mathbb{E}[X])^n$ 恒成立。

Q3.（概念题） 在收集者问题的推导中，各 $X_i$ 是否独立？这个问题的答案会影响 $\mathbb{E}[T]=nH_n$ 的正确性吗？请说明理由，并举一个”各阶段变量相关”的具体观察。