离散随机变量及其分布

从概率空间走向可计算的量：本讲把随机结果映射为实数，用分布律、期望与方差刻画离散随机变量的行为，并通过二项分布、几何分布、超几何分布、Balls-and-Bins 以及成对独立 vs 相互独立等核心模型，建立离散概率的算法直觉。

学习目标

先修回顾

离散随机变量、分布律与累积分布

设 \((\Omega, \mathcal{F}, \mathbb{P})\) 为概率空间。离散随机变量 \(X: \Omega \to \mathbb{R}\) 是一个只取有限个或可列个实数值的函数；我们通常关心它的分布律（probability mass function, PMF），定义为对每个 \(x \in \mathbb{R}\),

\[ p_X(x) = \mathbb{P}[X = x] = \sum_{\omega \in \Omega: X(\omega)=x} \mathbb{P}[\omega]. \]

PMF 必须满足非负性 \(p_X(x) \ge 0\) 与归一性 \(\sum_{x} p_X(x) = 1\)。反过来，任何满足这两条的函数都可定义一个离散分布。注意 PMF 是逐点概率，而不是区间概率：对离散随机变量，单点可正，但长度为零的区间概率为零只在连续情形成立。

累积分布函数（CDF）定义为 \(F_X(x) = \mathbb{P}[X \le x]\)，对离散随机变量它是右连续阶梯函数，跳跃高度恰好等于该点的 PMF 值。CDF 在 \(x \to -\infty\) 时趋于 0，在 \(x \to +\infty\) 时趋于 1。用 CDF 计算区间概率是常见技巧：

离散随机变量之间可以谈联合分布与独立性：\(X, Y\) 独立当且仅当 \(p_{X,Y}(x,y) = p_X(x)p_Y(y)\) 对所有 \(x, y\) 成立。独立性是逐点乘积，而不是事件层面的独立，尽管两者在自然构造下等价。

在 CS 70 的讨论与作业里，识别随机变量的定义域往往是第一步。例如投掷 \(n\) 次不均匀硬币，正面次数 \(X\) 的取值范围是 \(\{0, 1, \dots, n\}\)，而不是实数区间。把定义域写错会导致后续期望与方差计算全部错位。

期望、方差与指标随机变量

设离散随机变量 \(X\) 的取值集合为 \(\mathcal{X}\)。期望（期望值）定义为

只要级数绝对收敛就存在。期望是线性算子：对任意常数 \(a, b\) 与同分布上的随机变量 \(X, Y\)，

不需要 \(X, Y\) 独立。线性期望是 CS 70 计数与 Balls-and-Bins 问题的核心工具，因为它把复杂随机变量拆成简单随机变量之和。

方差定义为 \(\operatorname{Var}(X) = \mathbb{E}[(X - \mathbb{E}[X])^2]\)，等价于常用计算公式

方差衡量随机变量偏离期望的平方期望，具有性质 \(\operatorname{Var}(aX + b) = a^2 \operatorname{Var}(X)\)。当 \(X, Y\) 独立时，方差可加：

\[ \operatorname{Var}(X + Y) = \operatorname{Var}(X) + \operatorname{Var}(Y). \]

指标随机变量（indicator random variable）是取值为 0 或 1 的随机变量：对事件 \(A\)，定义 \(I_A(\omega) = 1\) 当 \(\omega \in A\)，否则为 0。它的期望就是事件概率：

把 \(X\) 写成指标之和，例如 \(X = \sum_{i=1}^n I_{A_i}\)，就能用线性期望直接算 \(\mathbb{E}[X] = \sum_i \mathbb{P}[A_i]\)，而无需先求出 \(X\) 的分布。这是 Monte Carlo 型计数问题（如 balls-into-bins 的空箱数、匹配问题成功数）的标准思路。

二项分布与几何分布

在 \(n\) 次独立伯努利试验中，每次成功概率为 \(p\)，则成功次数 \(X\) 服从二项分布，记 \(X \sim \operatorname{Binomial}(n, p)\)，其 PMF 为

\[ \mathbb{P}[X = k] = \binom{n}{k} p^k (1-p)^{n-k}, \quad k = 0, 1, \dots, n. \]

期望 \(\mathbb{E}[X] = np\)、方差 \(\operatorname{Var}(X) = np(1-p)\) 可由上节 indicator 方法直接得到。二项分布是 CS 70 讨论 9A「Head Count」的核心：投掷正面概率为 \(2/5\) 的硬币 20 次，正面数即 \(\operatorname{Binomial}(20, 2/5)\)。作业 09 第 6 题（航模测试）则展示了二项分布在多天独立筛选中的迭代：若每架飞机每天成功概率为 \(p\)，则 \(t\) 天后存活数为 \(\operatorname{Binomial}(n, p^t)\)。

几何分布描述的是「首次成功所需的试验次数」。设每次成功概率为 \(p\)，试验独立，则首次成功出现在第 \(k\) 次的概率为

这是以 \(\{1, 2, 3, \dots\}\) 为定义域的几何分布（注意也有以 \(\{0, 1, 2, \dots\}\) 定义的版本，差一次平移）。它的期望为 \(\mathbb{E}[X] = 1/p\)，方差为 \(\operatorname{Var}(X) = (1-p)/p^2\)，可通过等比数列求和或母函数推导。

几何分布最重要的性质是无记忆性（memorylessness）：对任意正整数 \(k, m\),

直觉上，已经失败了 \(m\) 次不会影响后续仍需等待的时间分布。这是几何分布独有的特征（在离散分布中，只有几何分布具有无记忆性），也是讨论 9B 第 1 题的核心考点。

超几何分布与 Balls-and-Bins

超几何分布描述无放回抽样中的成功次数：总体含 \(N\) 个元素，其中 \(M\) 个为「成功」。从中无放回抽取 \(n\) 个，成功数 \(X\) 满足

\[ \mathbb{E}[X] = n \cdot \frac{M}{N}, \quad \operatorname{Var}(X) = n \cdot \frac{M}{N} \left(1 - \frac{M}{N}\right) \cdot \frac{N-n}{N-1}. \]

期望与有放回（二项）情形相同，但方差多了一个有限总体修正因子 \((N-n)/(N-1) < 1\)，反映无放回抽样减少了波动。当 \(N\) 远大于 \(n\) 时，超几何近似于二项分布。讨论 8B「复活节彩蛋」与作业 09「对称弹珠」都是超几何背景的典型题。

Balls-and-Bins 把 \(m\) 个球独立、均匀地投入 \(n\) 个编号箱。基本问题包括：指定箱空着的概率、至少 \(k\) 个箱空着的概率、最大负载等。当 \(m = n\) 时，指定某箱为空的概率是

前 \(k\) 个指定箱全空的概率为 \((1 - k/n)^n\)。讨论 9A 第 1 题进一步用 Union Bound 估计「至少 \(k\) 箱空」的概率上界：设 \(A_i\) 为第 \(i\) 组 \(k\) 箱全空的事件，共有 \(m = \binom{n}{k}\) 组，则

\[ \mathbb{P}[\text{至少 } k \text{ 箱空}] = \mathbb{P}\left[\bigcup_{i=1}^m A_i\right] \le m \cdot \left(1 - \frac{k}{n}\right)^n = \binom{n}{k}\left(1 - \frac{k}{n}\right)^n. \]

Union Bound 的优势是避免复杂依赖，劣势是给的只是上界，不一定紧。

关键辨析：Balls-and-Bins 默认每次投球独立且均匀，对应「有放回、顺序重要」的样本空间，大小为 \(n^m\)。这与「stars and bars」的非均匀分布截然不同——后者每种组合（occupancy numbers）等可能，但每次投球不再独立。CS 70 明确要求区分这两种抽样机制。

成对独立与相互独立

事件族 \(\{A_1, \dots, A_n\}\) 成对独立（pairwise independent）指对任意 \(i \neq j\)，\(\mathbb{P}[A_i \cap A_j] = \mathbb{P}[A_i]\mathbb{P}[A_j]\)。相互独立（mutual independence）则更强：要求对任意子集 \(S \subseteq \{1,\dots,n\}\),

\[ \mathbb{P}\left[\bigcap_{i \in S} A_i\right] = \prod_{i \in S} \mathbb{P}[A_i]. \]

成对独立不蕴含相互独立，这是 CS 70 独立性辨析的核心难点。讨论 9A 第 3 题给出了经典反例：掷两个公平骰子，设 \(A_1\) 为「第一骰为 1」、\(A_2\) 为「第二骰为 6」、\(A_3\) 为「两骰和为 7」。每个事件的概率都是 \(1/6\)，每对事件的交概率都是 \(1/36\)，故成对独立成立。但三者同时发生的概率为 \(1/36\)，而乘积为 \(1/216\)，故不相互独立。

独立性辨析的常见手法： 1. 验证定义：直接计算 \(\mathbb{P}[A \cap B]\) 与 \(\mathbb{P}[A]\mathbb{P}[B]\) 是否相等。 2. 极端情形：若 \(A\) 发生必然导致 \(B\) 发生（如「前两箱空」蕴含「第一箱空」），则只要 \(0 < \mathbb{P}[A] < 1\) 且 \(\mathbb{P}[B] < 1\)，两者必不独立。 3. 条件概率：检查 \(\mathbb{P}[A \mid B]\) 是否等于 \(\mathbb{P}[A]\)。若不相等，则不独立。

作业 09 第 3 题（Mario 硬币）进一步说明：随机取一枚硬币掷两次，两次正面事件 \(Y_1, Y_2\) 不独立，因为第一次正面提供了关于所选硬币偏倚的信息，从而影响第二次正面的概率。而随机取两枚不同硬币各掷一次，两次正面事件 \(X_1, X_2\) 同样不独立，因为第一次正面暗示第一枚硬币偏倚较高，从而影响第二枚硬币的分布（两枚不能相同）。两种情形都需用贝叶斯更新严格证明。

常见误区

无放回抽样的期望与有放回不同，因为每次抽取会改变组成。

期望相同：无放回抽 \(n\) 次抽到红球的期望仍是 \(n \cdot M/N\)。由对称性，每次抽到红球的边际概率都是 \(M/N\)，线性期望不要求独立。不同的是方差：无放回方差多一个有限总体修正因子 \((N-n)/(N-1)\)。

几何分布与二项分布都是伯努利试验的产物，因此性质可以互推。

二项分布计数固定 \(n\) 次试验中的成功次数，几何分布计数首次成功所需的试验次数。两者定义域、期望公式、方差公式都不同。几何分布独有的无记忆性在二项分布中没有对应。

成对独立就是相互独立，只是说法不同。

成对独立只要求任意两个事件独立，相互独立要求任意子集的交概率等于概率乘积。讨论 9A 第 3 题（两骰子、第一骰为 1、第二骰为 6、和为 7）是成对独立但非相互独立的经典反例。

Balls-and-Bins 中每种 occupancy 组合（stars and bars）等可能。

默认的 Balls-and-Bins 是球独立、均匀地投箱，对应「有放回、顺序重要」的样本空间（大小 \(n^m\)）。Stars and bars 给出的是组合数，但每种组合不等可能。混淆两者会导致概率计算错误。

方差总是可加的：\(\operatorname{Var}(X+Y) = \operatorname{Var}(X) + \operatorname{Var}(Y)\)。

方差可加性只在 \(X, Y\) 独立（或不相关）时成立。一般情形需加上 \(2\operatorname{Cov}(X,Y)\)。对无放回抽样的超几何分布，协方差为负，导致方差比二项情形更小。