第8章 离散概率 (Discrete Probability)
一、导读
8.1 本章学习目标
在本章结束时，你将能够：
- 理解概率空间的定义和基本公理
- 计算条件概率和运用贝叶斯定理
- 理解随机变量及其分布
- 计算期望值和方差
- 掌握常见离散分布：均匀分布、二项分布、几何分布等
- 应用概率方法分析随机算法
- 理解大数定律和切比雪夫不等式
- 使用指示随机变量简化期望计算
- 理解马尔可夫不等式和切尔诺夫界
- 掌握概率生成函数在算法分析中的应用
- 理解熵和信息论的基本概念
8.2 为什么本章如此重要
概率论是计算机科学的核心基础之一。从算法分析到机器学习，从密码学到网络协议，概率思维无处不在。
对于程序员而言，掌握离散概率意味着能够：
分析随机算法：快速排序、哈希表、随机采样等
设计鲁棒系统：处理不确定性和噪声
理解机器学习：概率模型、贝叶斯推断、神经网络
评估风险：系统可靠性、故障率分析
优化性能：排队论、负载平衡、缓存策略
密码学安全：随机数生成、安全性证明
量化不确定性：在数据分析和决策中提供置信度
《具体数学》将离散概率放在后期章节，是因为它综合运用了前面所学的求和、二项式系数、特殊数等工具。概率论为这些纯数学工具提供了丰富的应用场景。例如，调和数出现在快速排序的平均情况分析中，二项式系数用于计算二项分布的概率，斯特林数用于分析哈希表的冲突。
概率思维不仅是一种数学技能，更是一种思维方式。它帮助我们在不确定的世界中做出理性决策，量化风险，优化资源分配。在现代数据驱动的世界中，概率素养已成为程序员的必备技能。
8.3 核心问题引导
概率空间的三个要素是什么？
条件概率的定义是什么？贝叶斯定理如何推导？
随机变量的期望值如何计算？有什么性质？
方差的含义是什么？如何计算？
二项分布和几何分布的区别是什么？
切比雪夫不等式的内容和应用是什么？
如何用概率方法分析算法的平均情况复杂度？
指示随机变量为何如此有用？
大数定律和中心极限定理的直观含义是什么？
熵在信息论中的意义是什么？
二、核心概念详解
8.1 概率空间
定义
概率空间是一个三元组 (Ω, F, P)，其中：
- Ω 是样本空间，所有可能结果的集合
- F 是事件域，Ω 的子集的集合（满足σ-代数性质）
- P 是概率测度，满足以下公理：
1. P(E) ≥ 0 对所有 E ∈ F
2. P(Ω) = 1
3. 对互斥事件 E₁, E₂, ...，有 $P(\bigcup_i E_i) = \sum_i P(E_i)$
通俗地说：Ω 是所有可能结果的列表，F 是我们关心的事件的集合，P 给每个事件分配一个0到1之间的概率值。
在离散情况下，Ω 是有限或可数无限的。此时，概率由概率质量函数（PMF）p(ω) = P({ω}) 完全确定，满足：
$$\sum_{\omega \in \Omega} p(\omega) = 1$$
对任意事件 $E \subseteq \Omega$，有 $P(E) = \sum_{\omega \in E} p(\omega)$。
示例：掷骰子
Ω = {1, 2, 3, 4, 5, 6}，如果是公平骰子，则 p(i) = 1/6 对所有 i。
事件"掷出偶数"：E = {2, 4, 6}，P(E) = 3/6 = 1/2。
事件"掷出质数"：E = {2, 3, 5}，P(E) = 3/6 = 1/2。
事件"掷出大于4的数"：E = {5, 6}，P(E) = 2/6 = 1/3。
示例：抛硬币两次
Ω = {HH, HT, TH, TT}，如果是公平硬币，每个结果的概率为 1/4。
事件"至少一次正面"：E = {HH, HT, TH}，P(E) = 3/4。
事件"两次结果相同"：E = {HH, TT}，P(E) = 1/2。
更复杂的示例：考虑一个随机算法，如随机快速排序。样本空间是所有可能的随机选择序列。每个序列对应一个执行路径，其概率取决于随机选择的分布。
概率的基本性质
补集规则：P(A') = 1 - P(A)
加法公式：P(A ∪ B) = P(A) + P(B) - P(A ∩ B)
单调性：如果 A ⊆ B，则 P(A) ≤ P(B)
布尔不等式：P(∪ᵢ Aᵢ) ≤ Σᵢ P(Aᵢ)
8.2 条件概率与独立性
条件概率
定义：在事件 B 发生的条件下，事件 A 发生的概率为：
$$P(A|B) = \frac{P(A \cap B)}{P(B)}$$
前提是 P(B) > 0。
直观理解：已知 B 发生后，样本空间缩小为 B，A ∩ B 在 B 中的相对比例就是条件概率。
示例：掷两个公平骰子，已知点数之和为7，求第一个骰子为4的概率。
设 A = "第一个骰子为4"，B = "点数之和为7"。
P(B) = 6/36 = 1/6（因为有 (1,6),(2,5),(3,4),(4,3),(5,2),(6,1) 共6种）。
P(A ∩ B) = P((4,3)) = 1/36。
P(A|B) = (1/36) / (1/6) = 1/6。
直觉解释：条件概率反映了新信息如何更新我们的信念。当我们得知 B 发生时，我们排除了所有 B 不发生的情况，然后在剩余的情况中重新计算 A 的比例。
乘法法则
由条件概率定义可得：
$$P(A \cap B) = P(A|B)P(B) = P(B|A)P(A)$$
推广到多个事件：
$$P(A_1 \cap A_2 \cap \cdots \cap A_n) = P(A_1)P(A_2|A_1)P(A_3|A_1 \cap A_2)\cdots P(A_n|A_1 \cap \cdots \cap A_{n-1})$$
应用：抽牌问题。从52张牌中依次抽出3张A的概率：
$$P = \frac{4}{52} \times \frac{3}{51} \times \frac{2}{50} = \frac{1}{5525}$$
另一个应用：蒙特卡洛树搜索中，路径概率的计算。
全概率公式
如果 B₁, B₂, ..., Bₖ 是样本空间的一个划分（互斥且穷尽），则对任意事件 A：
$$P(A) = \sum_{i=1}^{k} P(A|B_i)P(B_i)$$
证明：$A = A \cap \Omega = A \cap (\bigcup_i B_i) = \bigcup_i (A \cap B_i)$，且各 A ∩ Bᵢ 互斥。
应用示例：假设某疾病有三种亚型，患病率分别为 P(B₁)=0.01, P(B₂)=0.02, P(B₃)=0.03。检测对各亚型的阳性率分别为 P(A|B₁)=0.95, P(A|B₂)=0.90, P(A|B₃)=0.85。则总体阳性率为：
P(A) = 0.95×0.01 + 0.90×0.02 + 0.85×0.03 = 0.0505
贝叶斯定理
贝叶斯定理（Bayes' Theorem）：
$$P(A|B) = \frac{P(B|A)P(A)}{P(B)}$$
如果 B₁, B₂, ..., Bₖ 是样本空间的一个划分，则对任意事件 A：
$$P(B_i|A) = \frac{P(A|B_i)P(B_i)}{\sum_{j=1}^{k} P(A|B_j)P(B_j)}$$
应用：医学诊断、垃圾邮件过滤、机器学习中的分类问题。
示例：某种疾病的患病率为1%，检测的准确率为99%（即患病者检测阳性的概率为99%，未患病者检测阴性的概率为99%）。如果某人检测阳性，他实际患病的概率是多少？
设 D = "患病"，T = "检测阳性"。
- P(D) = 0.01
- P(T|D) = 0.99
- P(T|¬D) = 0.01（假阳性）
P(T) = P(T|D)P(D) + P(T|¬D)P(¬D) = 0.99×0.01 + 0.01×0.99 = 0.0198
$$P(D|T) = \frac{P(T|D)P(D)}{P(T)} = \frac{0.99 \times 0.01}{0.0198} = 0.5$$
只有50%！这就是为什么一次阳性检测通常需要复检。即使检测准确率很高，由于疾病本身很罕见，阳性预测值仍然不高。
贝叶斯思维的启示：
先验概率（base rate）很重要，不能忽视
新证据应该用来更新信念，而不是替代先验
罕见事件的检测需要极高的特异性才有实用价值
独立性
定义：事件 A 和 B 是独立的，如果 P(A ∩ B) = P(A)P(B)。
等价地，A 和 B 独立当且仅当 P(A|B) = P(A)（假设 P(B) > 0）。
直观理解：B 的发生不影响 A 的概率。
注意：互斥事件（A ∩ B = ∅）通常不是独立的，除非其中一个概率为0。因为如果 A 和 B 互斥且都非零概率，则 P(A|B) = 0 ≠ P(A)。
多个事件的独立性：事件 A₁, A₂, ..., Aₙ 是相互独立的，如果对任意子集 {i₁, ..., iₖ}，有：
$$P(A_{i_1} \cap \cdots \cap A_{i_k}) = P(A_{i_1})\cdots P(A_{i_k})$$
pairwise独立 vs 相互独立：两两独立不一定意味着相互独立。例如，抛两枚硬币，设 A="第一枚正面"，B="第二枚正面"，C="两枚结果相同"。则 A,B,C 两两独立，但不相互独立（因为 P(A∩B∩C) = 1/4 ≠ 1/8）。
8.3 随机变量
定义
随机变量 X 是从样本空间 Ω 到实数集 R 的函数：X: Ω → R。
随机变量将每个结果映射为一个数值，使得我们可以进行数学运算。
示例：掷两个骰子，Ω = {(i,j) : 1 ≤ i,j ≤ 6}。定义 X(i,j) = i+j 为点数之和。X 是一个随机变量，取值范围为 {2, 3, ..., 12}。
概率分布
随机变量 X 的概率质量函数（PMF）定义为：
$$p_X(x) = P(X = x) = P(\{\omega \in \Omega : X(\omega) = x\})$$
累积分布函数（CDF）定义为：
$$F_X(x) = P(X \leq x) = \sum_{t \leq x} p_X(t)$$
性质：
0 ≤ F_X(x) ≤ 1
F_X 是非递减函数
lim_{x→-∞} F_X(x) = 0，lim_{x→∞} F_X(x) = 1
8.4 期望值
定义
随机变量 X 的期望值（Expected Value）定义为：
$$E[X] = \sum_{x} x \cdot p_X(x)$$
前提是级数绝对收敛。
直观理解：期望值是长期平均结果。如果重复实验很多次，取平均值，这个平均值会趋近于期望值。
线性性质
期望值的线性性质是最重要的性质之一：
$$E[aX + bY] = aE[X] + bE[Y]$$
其中 a, b 是常数，X, Y 是随机变量。
关键：线性性质不需要 X 和 Y 独立！这对简化计算非常有用。
推论：$E[\sum_{i=1}^n X_i] = \sum_{i=1}^n E[X_i]$。
示例：掷 n 个公平骰子，点数之和的期望值为 n × 3.5 = 3.5n。
示例：掷骰子
公平骰子的期望值：
$$E[X] = \sum_{i=1}^{6} i \cdot \frac{1}{6} = \frac{1+2+3+4+5+6}{6} = \frac{21}{6} = 3.5$$
指示随机变量
指示随机变量 I_A 定义为：
$$I_A = \begin{cases} 1 & \text{if } A \text{ 发生} \\ 0 & \text{otherwise} \end{cases}$$
其期望值为：
$$E[I_A] = 1 \cdot P(A) + 0 \cdot P(\neg A) = P(A)$$
这个简单的观察是许多概率计算的基础。
示例：n 次伯努利试验中成功的次数 X = I₁ + I₂ + ... + Iₙ，其中 Iᵢ 是第 i 次试验成功的指示变量。
$$E[X] = \sum_{i=1}^{n} E[I_i] = \sum_{i=1}^{n} p = np$$
这正是二项分布的期望值。
示例：优惠券收集问题。有 n 种优惠券，每次随机获得一种，问收集齐所有种类的期望次数。
设 X 为总次数，Xᵢ 为从收集到 i-1 种到收集到 i 种所需的额外次数。则 X = X₁ + X₂ + ... + Xₙ。
当已有 i-1 种时，获得新种类的概率为 $\frac{n-(i-1)}{n} = \frac{n-i+1}{n}$。所以 Xᵢ 服从几何分布，参数为 $\frac{n-i+1}{n}$，期望为 $\frac{n}{n-i+1}$。
$$E[X] = \sum_{i=1}^{n} E[X_i] = \sum_{i=1}^{n} \frac{n}{n-i+1} = n \sum_{k=1}^{n} \frac{1}{k} = n H_n \approx n(\ln n + \gamma)$$
其中 γ ≈ 0.577 是欧拉常数。
更多指示变量应用：
- 图中边的数量期望
- 哈希表冲突次数期望
- 随机排列中不动点数量期望
8.5 方差与标准差
定义
随机变量 X 的方差定义为：
$$Var(X) = E[(X - E[X])^2] = E[X^2] - (E[X])^2$$
标准差是方差的平方根：$\sigma_X = \sqrt{Var(X)}$。
直观理解：方差衡量随机变量的"分散程度"。方差越大，结果越不可预测。
性质
$Var(aX + b) = a^2 Var(X)$
如果 X 和 Y 独立，则 $Var(X + Y) = Var(X) + Var(Y)$
更一般地，$Var(\sum X_i) = \sum Var(X_i) + 2\sum_{i<j} Cov(X_i, X_j)$
协方差：$Cov(X,Y) = E[(X-E[X])(Y-E[Y])] = E[XY] - E[X]E[Y]$
示例：掷骰子
公平骰子的方差：
$$E[X^2] = \sum_{i=1}^{6} i^2 \cdot \frac{1}{6} = \frac{1+4+9+16+25+36}{6} = \frac{91}{6}$$
$$Var(X) = E[X^2] - (E[X])^2 = \frac{91}{6} - (3.5)^2 = \frac{91}{6} - \frac{49}{4} = \frac{182-147}{12} = \frac{35}{12} \approx 2.917$$
标准差 σ ≈ 1.708。
8.6 常见离散分布
均匀分布
如果 X 在 {1, 2, ..., n} 上均匀分布，则 p_X(k) = 1/n。
- $E[X] = \frac{n+1}{2}$
- $Var(X) = \frac{n^2-1}{12}$
应用：随机数生成、随机抽样。
伯努利分布
伯努利试验：成功概率为 p，失败概率为 1-p。
X ~ Bernoulli(p)：
- P(X=1) = p, P(X=0) = 1-p
- $E[X] = p$
- $Var(X) = p(1-p)$
应用：单次随机试验建模。
二项分布
定义：n 次独立伯努利试验，每次成功概率为 p，成功次数 X 服从二项分布 B(n, p)：
$$P(X = k) = \binom{n}{k} p^k (1-p)^{n-k}$$
- $E[X] = np$
- $Var(X) = np(1-p)$
示例：抛10次硬币，正面朝上的次数服从 B(10, 0.5)。
形状：当 p=0.5 时对称；当 p≠0.5 时偏斜。
近似：当 n 很大时，二项分布可以用正态分布近似（中心极限定理）。
应用：质量控制、A/B测试、民意调查。
几何分布
定义：首次成功所需的伯努利试验次数 X 服从几何分布 Geo(p)：
$$P(X = k) = (1-p)^{k-1} p, \quad k = 1, 2, 3, \ldots$$
- $E[X] = \frac{1}{p}$
- $Var(X) = \frac{1-p}{p^2}$
示例：抛硬币直到第一次正面朝上，所需次数的期望是 1/p = 2（公平硬币）。
无记忆性：P(X > m+n | X > m) = P(X > n)。这是几何分布独有的性质。
证明：$P(X > k) = (1-p)^k$，所以 $P(X > m+n | X > m) = \frac{(1-p)^{m+n}}{(1-p)^m} = (1-p)^n = P(X > n)$。
应用：等待时间建模、重试机制分析。
负二项分布
定义：第 r 次成功所需的伯努利试验次数 X 服从负二项分布 NB(r, p)：
$$P(X = k) = \binom{k-1}{r-1} p^r (1-p)^{k-r}, \quad k = r, r+1, \ldots$$
- $E[X] = \frac{r}{p}$
- $Var(X) = \frac{r(1-p)}{p^2}$
当 r=1 时退化为几何分布。
应用：多次成功所需的试验次数建模。
泊松分布
定义：单位时间内事件发生次数 X 服从泊松分布 Poisson(λ)：
$$P(X = k) = \frac{\lambda^k e^{-\lambda}}{k!}, \quad k = 0, 1, 2, \ldots$$
- $E[X] = \lambda$
- $Var(X) = \lambda$
应用：稀有事件的计数，如网站访问量、电话呼叫数、放射性衰变等。
与二项分布的关系：当 n→∞, p→0, np=λ 固定时，B(n,p) 趋近于 Poisson(λ)。
证明思路：$\binom{n}{k} p^k (1-p)^{n-k} = \frac{n(n-1)\cdots(n-k+1)}{k!} (\frac{\lambda}{n})^k (1-\frac{\lambda}{n})^{n-k}$，当 n→∞ 时趋近于 $\frac{\lambda^k e^{-\lambda}}{k!}$。
泊松过程：如果事件以恒定速率 λ 随机发生，则在时间 t 内发生的事件数服从 Poisson(λt)。
超几何分布
定义：从 N 个物品（其中 K 个是"成功"）中不放回地抽取 n 个，成功次数 X 服从超几何分布：
$$P(X = k) = \frac{\binom{K}{k}\binom{N-K}{n-k}}{\binom{N}{n}}$$
- $E[X] = n\frac{K}{N}$
- $Var(X) = n\frac{K}{N}\frac{N-K}{N}\frac{N-n}{N-1}$
与二项分布的区别：超几何分布是不放回抽样，二项分布是放回抽样。当 N 很大时，两者近似相等。
应用：质量控制（批次检验）、扑克牌概率。
8.7 重要不等式
马尔可夫不等式
定理：如果 X ≥ 0 且 E[X] = μ，则对任意 a > 0：
$$P(X \geq a) \leq \frac{\mu}{a}$$
证明：$E[X] \geq a \cdot P(X \geq a)$，所以 $P(X \geq a) \leq E[X]/a$。
直观理解：非负随机变量取大值的概率受其期望的限制。
应用：如果某程序平均运行时间为 10 秒，则运行时间超过 100 秒的概率不超过 10%。
切比雪夫不等式
定理：对任意随机变量 X 和任意 k > 0：
$$P(|X - E[X]| \geq k\sigma) \leq \frac{1}{k^2}$$
其中 σ 是标准差。
证明：应用马尔可夫不等式于 Y = (X-E[X])²。
应用：估计随机变量偏离期望的概率上界。
示例：如果某随机变量的标准差为 2，则它偏离期望超过 6 的概率不超过 1/9 ≈ 11.1%。
单边切比雪夫不等式（坎泰利不等式）：
$$P(X - E[X] \geq k\sigma) \leq \frac{1}{1+k^2}$$
切尔诺夫界
切尔诺夫界（Chernoff Bound）给出了更紧的尾部概率上界。
对于独立伯努利试验的和 X，有：
$$P(X \geq (1+\delta)\mu) \leq \left(\frac{e^\delta}{(1+\delta)^{1+\delta}}\right)^\mu$$
这比切比雪夫不等式紧得多，但要求独立性。
简化形式（对于 0 < δ < 1）：
$$P(X \geq (1+\delta)\mu) \leq e^{-\delta^2\mu/3}$$
应用：负载均衡、随机化算法分析、机器学习理论。
8.8 大数定律
弱大数定律：设 X₁, X₂, ... 是独立同分布的随机变量，E[Xᵢ] = μ。则样本均值 $\bar{X}_n = \frac{1}{n}\sum_{i=1}^n X_i$ 依概率收敛于 μ：
$$\lim_{n\to\infty} P(|\bar{X}_n - \mu| \geq \epsilon) = 0$$
直观理解：随着样本量增加，样本均值越来越接近总体均值。
应用：蒙特卡洛模拟、频率估计、保险精算。
强大数定律：样本均值几乎必然收敛于 μ：
$$P(\lim_{n\to\infty} \bar{X}_n = \mu) = 1$$
8.9 熵与信息论
熵（Entropy）是信息论的核心概念，衡量随机变量的不确定性。
定义：离散随机变量 X 的熵为：
$$H(X) = -\sum_x p_X(x) \log_2 p_X(x)$$
性质：
H(X) ≥ 0
当 X 均匀分布时熵最大
当 X 是确定性变量时熵为 0
应用：数据压缩、密码学、机器学习特征选择。
联合熵：$H(X,Y) = -\sum_{x,y} p(x,y) \log_2 p(x,y)$
条件熵：$H(X|Y) = H(X,Y) - H(Y)$
互信息：$I(X;Y) = H(X) - H(X|Y) = H(Y) - H(Y|X)$
三、程序员的视角
8.1 在算法分析中的应用
随机算法分析
- 快速排序：平均比较次数为 2n ln n ≈ 1.39n log₂ n。使用指示随机变量可以简洁地推导。
设 Iᵢⱼ 为指示变量，表示元素 i 和 j 是否被比较过。则总比较次数 C = Σᵢ<ⱼ Iᵢⱼ。
$$E[C] = \sum_{i<j} E[I_{ij}] = \sum_{i<j} P(i \text{ and } j \text{ are compared})$$
可以证明 $P(i \text{ and } j \text{ are compared}) = \frac{2}{j-i+1}$，因此：
$$E[C] = \sum_{i<j} \frac{2}{j-i+1} \approx 2n \ln n$$
- 哈希表：在简单均匀散列假设下，期望查找时间为 O(1)。链地址法的期望链长为 n/m（装载因子）。
- 随机采样：Reservoir Sampling 算法可以在 O(n) 时间内从数据流中随机抽取 k 个样本。
负载均衡
使用概率方法分析 balls-and-bins 问题：将 n 个球随机放入 n 个箱子，最大负载的期望是 Θ(log n / log log n)。
证明思路：使用切尔诺夫界和并集界限。
布隆过滤器
布隆过滤器使用多个哈希函数将元素映射到位数组。误报率可以通过概率分析精确计算。
如果位数组大小为 m，哈希函数数量为 k，插入 n 个元素，则误报率约为 $(1-e^{-kn/m})^k$。
最优 k 值为 $\frac{m}{n}\ln 2$，此时误报率约为 $(0.6185)^{m/n}$。
8.2 常见陷阱
陷阱1：期望的线性性质的误用
线性性质总是成立，但 $E[XY] = E[X]E[Y]$ 仅在 X, Y 独立时成立。
反例：设 X 为掷骰子的结果，Y = 7-X。则 E[X]=3.5, E[Y]=3.5，但 E[XY] ≠ E[X]E[Y]。
陷阱2：小概率事件的忽视
即使概率很小，在大量重复实验中也可能发生。例如，彩票中奖概率极低，但由于购买人数众多，总会有人中奖。
生日悖论：23人中至少两人生日相同的概率超过50%。这是因为配对数量为 $\binom{23}{2}=253$，远大于23。
陷阱3：条件概率的混淆
P(A|B) ≠ P(B|A)。这是常见的逻辑错误，称为"检察官谬误"。
示例：如果某种疾病的患者中有90%出现某症状，并不意味着出现该症状的人中有90%患病。
陷阱4：独立性的错误假设
许多实际问题中，事件之间并非独立。错误假设独立性会导致错误的结论。
示例：股票价格变化通常不是独立的，存在自相关性。
8.3 与其他领域的联系
- 机器学习：贝叶斯分类器、概率图模型、强化学习
- 密码学：随机数生成、安全性分析、差分隐私
- 网络：排队论、拥塞控制、路由协议
- 金融：风险评估、期权定价、投资组合优化
- 物理学：统计力学、量子力学
四、代码实战
8.1 概率计算库
import math
from collections import defaultdict
import random
import numpy as np
class DiscreteProbability:
"""离散概率工具"""
@staticmethod
def binomial_pmf(n, p, k):
"""二项分布 PMF: P(X=k)"""
return math.comb(n, k) * p**k * (1-p)**(n-k)
@staticmethod
def geometric_pmf(p, k):
"""几何分布 PMF: P(X=k)"""
return (1-p)**(k-1) * p
@staticmethod
def poisson_pmf(lam, k):
"""泊松分布 PMF: P(X=k)"""
return lam**k * math.exp(-lam) / math.factorial(k)
@staticmethod
def hypergeometric_pmf(N, K, n, k):
"""超几何分布 PMF"""
return (math.comb(K, k) * math.comb(N-K, n-k)) / math.comb(N, n)
@staticmethod
def expected_value(values, probabilities):
"""计算期望值"""
return sum(v * p for v, p in zip(values, probabilities))
@staticmethod
def variance(values, probabilities):
"""计算方差"""
mu = DiscreteProbability.expected_value(values, probabilities)
return sum((v - mu)**2 * p for v, p in zip(values, probabilities))
@staticmethod
def bayes_theorem(p_a, p_b_given_a, p_b_given_not_a):
"""贝叶斯定理: P(A|B)"""
p_b = p_b_given_a * p_a + p_b_given_not_a * (1 - p_a)
return p_b_given_a * p_a / p_b
@staticmethod
def markov_inequality(mu, a):
"""马尔可夫不等式: P(X >= a) <= mu/a"""
return mu / a
@staticmethod
def chebyshev_inequality(sigma, k):
"""切比雪夫不等式: P(|X-mu| >= k*sigma) <= 1/k^2"""
return 1 / k**2
@staticmethod
def chernoff_bound(mu, delta):
"""切尔诺夫界: P(X >= (1+delta)*mu) <= exp(-delta^2*mu/3)"""
if 0 < delta < 1:
return math.exp(-delta**2 * mu / 3)
else:
# 通用形式
return (math.exp(delta) / (1+delta)**(1+delta))**mu
@staticmethod
def entropy(probs):
"""计算熵"""
return -sum(p * math.log2(p) for p in probs if p > 0)
@staticmethod
def simulate_dice_roll(n_simulations=10000):
"""模拟掷骰子"""
results = defaultdict(int)
for _ in range(n_simulations):
roll = random.randint(1, 6)
results[roll] += 1
# 转换为概率
total = sum(results.values())
pmf = {k: v/total for k, v in results.items()}
return pmf
@staticmethod
def coupon_collector_simulation(n, n_trials=1000):
"""模拟优惠券收集问题"""
total_trials = 0
for _ in range(n_trials):
collected = set()
count = 0
while len(collected) < n:
coupon = random.randint(1, n)
collected.add(coupon)
count += 1
total_trials += count
return total_trials / n_trials
@staticmethod
def birthday_paradox(n_people, n_days=365):
"""计算生日悖论概率"""
# P(至少两人同生日) = 1 - P(所有人生日不同)
p_all_different = 1.0
for i in range(n_people):
p_all_different *= (n_days - i) / n_days
return 1 - p_all_different
# 测试
dp = DiscreteProbability()
print("=== 离散概率测试 ===")
# 二项分布
print("\n二项分布 B(10, 0.5):")
for k in range(11):
prob = dp.binomial_pmf(10, 0.5, k)
print(f"P(X={k}) = {prob:.4f}")
# 几何分布
print("\n几何分布 Geo(0.3):")
for k in range(1, 11):
prob = dp.geometric_pmf(0.3, k)
print(f"P(X={k}) = {prob:.4f}")
# 泊松分布
print("\n泊松分布 Poisson(3):")
for k in range(10):
prob = dp.poisson_pmf(3, k)
print(f"P(X={k}) = {prob:.4f}")
# 贝叶斯定理
print("\n贝叶斯定理示例:")
p_disease = 0.01
p_positive_given_disease = 0.99
p_positive_given_healthy = 0.01
p_disease_given_positive = dp.bayes_theorem(
p_disease, p_positive_given_disease, p_positive_given_healthy
)
print(f"P(患病|阳性) = {p_disease_given_positive:.4f}")
# 不等式
print("\n不等式示例:")
print(f"马尔可夫: P(X >= 10) <= {dp.markov_inequality(5, 10):.4f}")
print(f"切比雪夫: P(|X-mu| >= 3*sigma) <= {dp.chebyshev_inequality(1, 3):.4f}")
print(f"切尔诺夫: P(X >= 1.5*mu) <= {dp.chernoff_bound(100, 0.5):.6f}")
# 模拟掷骰子
print("\n模拟掷骰子10000次:")
pmf = dp.simulate_dice_roll()
for face in sorted(pmf.keys()):
print(f"P(X={face}) ≈ {pmf[face]:.4f}")
# 优惠券收集问题
print("\n优惠券收集问题 (n=10):")
simulated = dp.coupon_collector_simulation(10, 1000)
theoretical = 10 * sum(1.0/k for k in range(1, 11))
print(f"模拟结果: {simulated:.2f}")
print(f"理论值: {theoretical:.2f}")
# 生日悖论
print("\n生日悖论:")
for n in [20, 23, 30, 50]:
p = dp.birthday_paradox(n)
print(f"{n}人: P = {p:.4f}")
# 熵
print("\n熵计算:")
uniform_probs = [0.25, 0.25, 0.25, 0.25]
biased_probs = [0.5, 0.25, 0.15, 0.1]
print(f"均匀分布熵: {dp.entropy(uniform_probs):.4f}")
print(f"偏斜分布熵: {dp.entropy(biased_probs):.4f}")8.2 快速排序的平均情况分析
def quicksort_expected_comparisons(n):
"""
计算快速排序的期望比较次数
E[C(n)] = 2(n+1)H_n - 4n ≈ 2n ln n
"""
H_n = sum(1.0/k for k in range(1, n+1))
return 2 * (n + 1) * H_n - 4 * n
print("\n快速排序期望比较次数:")
for n in [10, 100, 1000]:
expected = quicksort_expected_comparisons(n)
approx = 2 * n * math.log(n)
print(f"n={n}: 精确={expected:.2f}, 近似={approx:.2f}")8.3 蒙特卡洛估算 π
def monte_carlo_pi(n_samples=1000000):
"""使用蒙特卡洛方法估算 π"""
inside = 0
for _ in range(n_samples):
x, y = random.random(), random.random()
if x**2 + y**2 <= 1:
inside += 1
return 4 * inside / n_samples
estimated_pi = monte_carlo_pi()
print(f"\n蒙特卡洛估算 π (100万样本): {estimated_pi:.6f}")
print(f"真实值: {math.pi:.6f}")8.4 布隆过滤器误报率分析
def bloom_filter_false_positive(m, n, k):
"""
计算布隆过滤器误报率
m: 位数组大小
n: 插入元素数量
k: 哈希函数数量
"""
p_bit_zero = (1 - 1/m)**(k*n)
p_bit_one = 1 - p_bit_zero
false_positive = p_bit_one**k
return false_positive
def optimal_k(m, n):
"""计算最优哈希函数数量"""
return round((m/n) * math.log(2))
# 测试
m = 1000000 # 1M bits
n = 100000 # 100K elements
k_opt = optimal_k(m, n)
fp_rate = bloom_filter_false_positive(m, n, k_opt)
print(f"\n布隆过滤器分析:")
print(f"位数组大小: {m} bits")
print(f"元素数量: {n}")
print(f"最优哈希函数数: {k_opt}")
print(f"误报率: {fp_rate:.6f}")五、深入思考
5.1 历史背景
概率论起源于帕斯卡和费马关于赌博问题的通信。拉普拉斯将其系统化，柯尔莫哥洛夫建立了公理化基础。贝叶斯定理以托马斯·贝叶斯命名，但他在生前并未发表。切尔诺夫界由赫尔曼·切尔诺夫在1950年代提出。
香农在1948年创立了信息论，引入熵作为信息量的度量。这一思想深刻影响了通信、数据压缩和密码学。
5.2 未解决的问题
随机性的本质：什么是真正的随机？伪随机数能否替代真随机数？
概率证明：如何用概率方法证明存在性？
高维概率：高维空间中的概率现象有何特殊性？
随机算法的去随机化：能否将随机算法转化为确定性算法而不损失效率？
5.3 延伸阅读
《Introduction to Probability》 - Blitzstein & Hwang
《具体数学》第8章 - Graham, Knuth, Patashnik
《Probability and Computing》 - Mitzenmacher & Upfal
《The Art of Computer Programming, Vol. 2》 - Donald Knuth
《Elements of Information Theory》 - Cover & Thomas
六、实验笔记
实验一：蒙特卡洛模拟
目标：使用蒙特卡洛方法估算 π 的值。
步骤：
在单位正方形内随机生成点
统计落在单位圆内的点的比例
比例 × 4 ≈ π
扩展：尝试不同的样本量，观察精度变化。分析收敛速度（应为 O(1/√n)）。
实验二：生日悖论验证
目标：通过模拟验证生日悖论：23人中至少两人生日相同的概率超过50%。
步骤：
生成大量23人的群体
检查每个群体中是否有生日相同的人
统计比例
理论值：$P = 1 - \frac{365!}{(365-23)! \cdot 365^{23}} \approx 0.507$
实验三：赌徒破产问题
目标：模拟赌徒破产问题，验证理论概率。
问题：赌徒有 i 元，目标是达到 N 元，每局赢1元概率为 p，输1元概率为 q=1-p。求破产概率。
理论结果：如果 p ≠ q，破产概率为 $\frac{(q/p)^N - (q/p)^i}{(q/p)^N - 1}$。
实验四：中心极限定理验证
目标：通过模拟验证中心极限定理。
步骤：
从任意分布（如均匀分布）中抽取大量样本
计算样本均值
重复多次，绘制样本均值的分布
验证其近似正态分布
七、本章小结
关键公式：
- 期望值：$E[X] = \sum x \cdot p_X(x)$
- 方差：$Var(X) = E[X^2] - (E[X])^2$
- 贝叶斯定理：$P(A|B) = \frac{P(B|A)P(A)}{P(B)}$
- 切比雪夫不等式：$P(|X-\mu| \geq k\sigma) \leq \frac{1}{k^2}$
- 熵：$H(X) = -\sum p_X(x) \log_2 p_X(x)$
核心分布：
二项分布：B(n, p)，E[X]=np
几何分布：Geo(p)，E[X]=1/p
泊松分布：Poisson(λ)，E[X]=Var(X)=λ
超几何分布：不放回抽样
实用技巧：
- 使用指示随机变量简化期望计算
- 线性性质不需要独立性
- 马尔可夫和切比雪夫不等式提供尾部 bound
- 切尔诺夫界提供更紧的 bound（要求独立性）
- 熵衡量不确定性，在信息论中有广泛应用
八、习题
基础题
习题 8.1：计算掷两个公平骰子点数之和的期望值。
提示：使用线性性质或直接计算。
解答：E[X] = 7。
习题 8.2：如果 X ~ B(100, 0.3)，计算 E[X] 和 Var(X)。
提示：直接使用公式。
解答：E[X] = 30, Var(X) = 21。
习题 8.3：抛一枚公平硬币，直到出现连续两次正面。求期望抛掷次数。
提示：设状态为"无连续正面"、"一次正面"，建立方程。
解答：E[X] = 6。
进阶题
习题 8.4：[ME] 证明几何分布的期望值为 1/p。
提示：使用 $E[X] = \sum_{k=1}^{\infty} k(1-p)^{k-1}p$，求和。
习题 8.5：[ME] 使用切比雪夫不等式估计 P(|X-μ| ≥ 3σ)。
提示：直接代入 k=3。
解答：≤ 1/9 ≈ 0.111。
习题 8.6：[ME] 有 n 个人参加派对，每个人随机带一件礼物并随机交换。求没有人拿到自己礼物的概率（错排问题）。
提示：使用容斥原理，概率趋近于 1/e。
解答：$P = \sum_{k=0}^{n} \frac{(-1)^k}{k!} \approx \frac{1}{e}$。
挑战题
习题 8.7：[HM25] 推导泊松分布作为二项分布的极限。
提示：令 n→∞, p=λ/n，计算 $\lim_{n\to\infty} \binom{n}{k}(\lambda/n)^k(1-\lambda/n)^{n-k}$。
习题 8.8：[HM30] 分析随机快速排序的期望比较次数。
提示：使用指示随机变量 Iᵢⱼ 表示元素 i 和 j 是否被比较过。
习题 8.9：[HM35] 证明切尔诺夫界的简化形式：$P(X \geq (1+\delta)\mu) \leq e^{-\delta^2\mu/3}$（对于 0 < δ < 1）。
提示：使用泰勒展开近似 $\frac{e^\delta}{(1+\delta)^{1+\delta}}$。
习题 8.10：[HM40] 研究概率方法在组合数学中的应用，证明存在性定理。
提示：参考 Erdős 的概率方法，如 Ramsey 数的下界。
习题 8.11：[HM20] 计算两个独立泊松随机变量之和的分布。
提示：使用卷积或概率生成函数。
解答：如果 X ~ Poisson(λ₁), Y ~ Poisson(λ₂)，则 X+Y ~ Poisson(λ₁+λ₂)。
本章完