第7章 离散概率 (Discrete Probability)

一、导读

1.1 本章学习目标

完成本章学习后，你将能够：

理解概率空间、样本空间、事件的定义

掌握概率公理和基本性质

熟练计算条件概率和使用贝叶斯定理

理解独立性的概念并能判断事件是否独立

掌握随机变量的定义和期望值的计算

理解常见离散分布：均匀分布、二项分布、几何分布

掌握马尔可夫不等式和切比雪夫不等式

将概率思维应用于算法分析和风险评估

理解联合分布、边缘分布和条件分布的关系

掌握概率生成函数在分析中的应用

1.2 为什么本章如此重要

概率论是处理不确定性的数学工具，在计算机科学的各个领域都有应用。

在算法设计中：随机化算法（如快速排序的随机pivot选择）的性能分析需要概率。平均情况分析本质上也是概率计算。Las Vegas算法总是给出正确答案但运行时间是随机的；Monte Carlo算法运行时间确定但可能给出错误答案。

在机器学习中：朴素贝叶斯分类器、隐马尔可夫模型、概率图模型都基于概率论。深度学习中的dropout技术可以解释为一种集成学习的概率近似。强化学习中的探索-利用权衡本质上是概率决策问题。

在网络安全中：密码分析、入侵检测、风险评估都依赖概率模型。生日攻击利用概率论找到哈希碰撞；差分密码分析使用概率特征破解加密算法。

在系统设计中：队列理论用于性能建模；可靠性分析确保系统可用性。数据中心需要考虑服务器故障的概率；CDN需要优化内容分发的概率策略。

在游戏开发中：随机掉落、伤害计算、AI决策都需要概率。战利品箱的掉落率设计需要平衡玩家体验和收益；程序化内容生成使用概率方法创造多样性。

在数据科学中：统计推断、假设检验、置信区间都是概率的应用。A/B测试使用假设检验判断实验组和对照组的差异是否显著。

在区块链中：共识协议的安全性分析涉及概率；挖矿难度调整基于概率模型；双花攻击的成功概率需要精确计算。

在量子计算中：量子测量的结果本质上是概率性的；量子算法的成功概率需要分析。

1.3 核心问题引导

在学习本章之前，请思考以下问题：

抛一枚公平硬币10次，恰好5次正面的概率是多少？

如果某种疾病发病率是1%，检测准确率是99%，检测阳性的人真正患病的概率是多少？

什么是"独立"事件？抛硬币两次，第一次正面会影响第二次吗？

期望值一定是可能出现的结果吗？

为什么大数定律能保证赌场总是盈利？

如何用概率分析哈希冲突的可能性？

蒙特卡洛方法为什么能通过随机采样解决问题？

什么是条件概率？它与联合概率有什么区别？

为什么"罕见事件"的概率容易被高估或低估？

什么是概率悖论？如何解释它们？

二、核心概念详解

7.1 概率基础

概率空间

概率空间是一个三元组 (S, F, P)，其中：

• S 是样本空间（所有可能结果的集合）
• F 是事件域（S的子集的集合，通常是σ-代数）
• P 是概率函数，给每个事件分配一个[0,1]之间的数

对于离散概率空间，F可以是S的所有子集构成的幂集。

概率公理（柯尔莫哥洛夫公理）：

非负性：对任何事件E，P(E) ≥ 0

规范性：P(S) = 1

可列可加性：如果E₁, E₂, ... 两两不相交，则 P(∪Eᵢ) = ΣP(Eᵢ)

这些公理构成了现代概率论的基础，确保了概率计算的逻辑一致性。

基本概念

样本点：样本空间中的一个元素，也称为基本结果。

事件：样本空间的子集。简单事件只包含一个样本点；复合事件包含多个样本点。

概率质量函数（PMF）：对于离散随机变量X，p(x) = P(X = x)。PMF满足：

• p(x) ≥ 0 对所有x
• Σₓ p(x) = 1

累积分布函数（CDF）：F(x) = P(X ≤ x)。CDF是单调非减的，且 lim_{x→-∞} F(x) = 0，lim_{x→∞} F(x) = 1。

基本性质

加法公式的推导：A ∪ B 可以分解为三个互斥部分：A\B、A∩B、B\A。因此：

P(A ∪ B) = P(A\B) + P(A∩B) + P(B\A)

= [P(A\B) + P(A∩B)] + [P(B\A) + P(A∩B)] - P(A∩B)

= P(A) + P(B) - P(A∩B)

等可能结果模型

如果样本空间有n个等可能结果，事件E包含m个结果，则：

$$P(E) = \frac{m}{n} = \frac{|E|}{|S|}$$

这是古典概型的核心公式，适用于公平骰子、抽牌等问题。

示例：从一副52张扑克牌中随机抽取一张，抽到A的概率是多少？

解：样本空间大小|S| = 52。事件"抽到A"包含4个结果（四种花色）。因此 P = 4/52 = 1/13。

7.2 条件概率与独立性

条件概率

定义：在事件F发生的条件下，事件E发生的概率为：

$$P(E|F) = \frac{P(E \cap F)}{P(F)}$$

前提是 P(F) > 0。

直觉：已知F发生后，样本空间缩小为F，我们需要计算E∩F在F中的比例。这相当于在F这个"新世界"中重新计算概率。

乘法法则：P(E ∩ F) = P(E|F) · P(F) = P(F|E) · P(E)

推广（链式法则）：对于n个事件：

$$P(E_1 \cap E_2 \cap \cdots \cap E_n) = P(E_1) \cdot P(E_2|E_1) \cdot P(E_3|E_1 \cap E_2) \cdots P(E_n|E_1 \cap \cdots \cap E_{n-1})$$

应用示例：从一副52张牌中不放回地抽取两张，两张都是A的概率是多少？

解：设E₁="第一张是A"，E₂="第二张是A"。

P(E₁) = 4/52 = 1/13

P(E₂|E₁) = 3/51 = 1/17（因为已经抽走了一张A）

P(E₁ ∩ E₂) = P(E₁) · P(E₂|E₁) = (1/13) × (1/17) = 1/221

全概率公式

如果事件B₁, B₂, ..., Bₙ构成样本空间的一个划分（互斥且并为S），则对任意事件A：

$$P(A) = \sum_{i=1}^{n} P(A|B_i) \cdot P(B_i)$$

证明：A = A ∩ S = A ∩ (∪Bᵢ) = ∪(A ∩ Bᵢ)。由于Bᵢ互斥，A∩Bᵢ也互斥。因此：

P(A) = Σ P(A ∩ Bᵢ) = Σ P(A|Bᵢ)P(Bᵢ) ∎

应用：全概率公式常用于将复杂问题分解为简单情况。

示例：某工厂有三台机器生产产品，机器A生产50%，B生产30%，C生产20%。次品率分别为A:2%，B:3%，C:5%。随机抽取一件产品，它是次品的概率是多少？

解：设D="产品是次品"。

P(D) = P(D|A)P(A) + P(D|B)P(B) + P(D|C)P(C)

= 0.02×0.5 + 0.03×0.3 + 0.05×0.2

= 0.01 + 0.009 + 0.01 = 0.029

贝叶斯定理

$$P(E|F) = \frac{P(F|E) \cdot P(E)}{P(F)}$$

扩展形式（当F可以分解为互斥事件E₁, E₂, ..., Eₙ时）：

$$P(E_i|F) = \frac{P(F|E_i) \cdot P(E_i)}{\sum_{j=1}^{n} P(F|E_j) \cdot P(E_j)}$$

术语：

• P(E)：先验概率（prior），观察到证据前的信念
• P(E|F)：后验概率（posterior），观察到证据后的更新信念
• P(F|E)：似然（likelihood），在E为真时观察到F的概率
• P(F)：证据（evidence），归一化常数

直觉：贝叶斯定理告诉我们如何根据新证据更新信念。后验概率正比于先验概率乘以似然。

应用示例：医学检测

假设：

• 疾病发病率 P(D) = 0.01
• 检测灵敏度 P(+|D) = 0.99（有病检测为阳性的概率）
• 检测特异性 P(-|¬D) = 0.99（没病检测为阴性的概率）

问：检测为阳性的人真正患病的概率 P(D|+) 是多少？

解：

• P(+|¬D) = 1 - 0.99 = 0.01（假阳性率）
• P(+) = P(+|D)P(D) + P(+|¬D)P(¬D) = 0.99×0.01 + 0.01×0.99 = 0.0198
• P(D|+) = P(+|D)P(D)/P(+) = 0.99×0.01/0.0198 = 0.5

即使检测准确率为99%，阳性预测值只有50%！这是因为疾病很罕见，假阳性数量与真阳性相当。

进一步分析：如果一个人检测为阳性，再次检测仍为阳性，他真正患病的概率是多少？

解：第一次检测阳性后，患病的后验概率为0.5。这成为第二次检测的先验概率。

P(D|++) = P(+|D)P(D|+)/[P(+|D)P(D|+) + P(+|¬D)P(¬D|+)]

= 0.99×0.5 / (0.99×0.5 + 0.01×0.5)

= 0.495 / 0.5 = 0.99

两次阳性后，患病概率跃升至99%！这说明了重复测试的重要性。

贝叶斯思维：贝叶斯定理不仅是一个数学公式，更是一种思维方式。它强调：

信念应该是概率性的，而非确定性的

新证据应该用来更新信念，而非完全替换

先验信息很重要，不应忽视

独立性

定义：事件E和F是独立的，如果 P(E ∩ F) = P(E) · P(F)。

等价地：P(E|F) = P(E)（已知F发生不改变E的概率）。

注意：互斥事件通常不是独立的！如果E和F互斥且都有正概率，则 P(E∩F) = 0，但 P(E)·P(F) > 0。互斥意味着"强烈相关"——知道一个发生就知道另一个不发生。

相互独立：事件E₁, E₂, ..., Eₙ是相互独立的，如果对任意子集 {E_{i₁}, ..., E_{iₖ}}，有：

$$P(E_{i_1} \cap \cdots \cap E_{i_k}) = P(E_{i_1}) \cdots P(E_{i_k})$$

两两独立 vs 相互独立：两两独立（每对事件独立）不一定意味着相互独立。

反例：抛两枚公平硬币。设E₁="第一枚正面"，E₂="第二枚正面"，E₃="两枚结果相同"。

• P(E₁) = P(E₂) = P(E₃) = 1/2
• P(E₁∩E₂) = 1/4 = P(E₁)P(E₂)，所以E₁和E₂独立
• P(E₁∩E₃) = 1/4 = P(E₁)P(E₃)，所以E₁和E₃独立
• P(E₂∩E₃) = 1/4 = P(E₂)P(E₃)，所以E₂和E₃独立
• 但 P(E₁∩E₂∩E₃) = 1/4 ≠ 1/8 = P(E₁)P(E₂)P(E₃)

所以这三个事件两两独立但不相互独立。

独立性的应用：

• 系统可靠性：如果组件独立失效，系统可靠度可以计算
• 并行算法：独立任务的执行时间分析
• 随机抽样：样本之间的独立性保证统计推断的有效性

7.3 随机变量与期望

随机变量

随机变量X是从样本空间到实数的函数。它将随机结果量化为数值。

离散随机变量：取值范围是有限或可数无限的。

概率分布：列出X的所有可能取值及其概率。可以用表格、公式或图形表示。

指示随机变量：I_E = 1 如果事件E发生，否则为0。P(I_E = 1) = P(E)。

期望值

定义：离散随机变量X的期望值为：

$$E[X] = \sum_{x} x \cdot P(X = x)$$

性质：

• 线性性：E[aX + bY] = aE[X] + bE[Y]（无论X和Y是否独立）
• 常数：E[c] = c
• 单调性：如果 X ≤ Y，则 E[X] ≤ E[Y]
• 非负性：如果 X ≥ 0，则 E[X] ≥ 0

线性性的重要性：期望的线性性不需要独立性假设，这使得它在分析复杂问题时非常强大。

示例：公平骰子的期望值

E[X] = 1×(1/6) + 2×(1/6) + 3×(1/6) + 4×(1/6) + 5×(1/6) + 6×(1/6) = 3.5

注意：3.5不是可能的结果，但它是长期平均值。

示例：掷两枚骰子，点数之和的期望值是多少？

解法1：直接计算。X的可能取值为2,3,...,12。

E[X] = 2×(1/36) + 3×(2/36) + ... + 12×(1/36) = 7

解法2：利用线性性。设X₁和X₂分别为两枚骰子的点数。

E[X₁ + X₂] = E[X₁] + E[X₂] = 3.5 + 3.5 = 7

解法2更简单，因为它避免了计算X的分布。

期望的解释：

• 长期平均：重复实验很多次，样本均值趋近期望值
• 重心：概率分布的"平衡点"
• 公平价格：在赌博中，期望值是公平的游戏价格

方差与标准差

定义：Var(X) = E[(X - E[X])²] = E[X²] - (E[X])²

标准差：σ = √Var(X)

性质：

• Var(aX + b) = a²Var(X)
• 如果X和Y独立，Var(X + Y) = Var(X) + Var(Y)
• Var(X) ≥ 0，等号成立当且仅当X是常数

解释：方差衡量随机变量偏离期望值的程度。标准差与原始数据有相同的单位，更容易解释。

示例：公平骰子的方差

E[X] = 3.5

E[X²] = 1²×(1/6) + 2²×(1/6) + ... + 6²×(1/6) = 91/6 ≈ 15.17

Var(X) = 91/6 - 3.5² = 91/6 - 49/4 = 35/12 ≈ 2.92

σ ≈ 1.71

协方差与相关系数

协方差：Cov(X,Y) = E[(X-E[X])(Y-E[Y])] = E[XY] - E[X]E[Y]

性质：

• 如果X和Y独立，Cov(X,Y) = 0（但反之不成立）
• Cov(X,X) = Var(X)
• Cov(aX+b, cY+d) = ac·Cov(X,Y)

相关系数：ρ(X,Y) = Cov(X,Y) / (σ_X σ_Y)

性质：-1 ≤ ρ ≤ 1。ρ=1表示完全正相关，ρ=-1表示完全负相关，ρ=0表示无线性相关。

7.4 常见离散分布

均匀分布

如果随机变量X在{1, 2, ..., n}上均匀分布，则 P(X = k) = 1/n。

• E[X] = (n+1)/2
• Var(X) = (n²-1)/12

应用：随机数生成、随机抽样、负载均衡。

二项分布

场景：n次独立的伯努利试验，每次成功概率为p。

X = 成功次数，则 X ~ Binomial(n, p)。

$$P(X = k) = \binom{n}{k} p^k (1-p)^{n-k}$$

• E[X] = np
• Var(X) = np(1-p)

推导期望：设Xᵢ为第i次试验的指示变量（成功为1，失败为0）。则 X = ΣXᵢ。

E[Xᵢ] = 1·p + 0·(1-p) = p

E[X] = E[ΣXᵢ] = ΣE[Xᵢ] = np

示例：抛10次公平硬币，正面次数的分布是 Binomial(10, 0.5)。

P(X=5) = C(10,5) × 0.5¹⁰ ≈ 0.246

形状：当np和n(1-p)都较大时，二项分布近似正态分布。

应用：质量控制（次品数）、民意调查（支持人数）、A/B测试（转化数）。

几何分布

场景：重复独立试验，直到第一次成功。

X = 首次成功所需的试验次数，成功概率为p。

$$P(X = k) = (1-p)^{k-1} p$$

• E[X] = 1/p
• Var(X) = (1-p)/p²

推导期望：

E[X] = Σ_{k=1}^{∞} k(1-p)^{k-1}p

令 q = 1-p。则 E[X] = p Σ_{k=1}^{∞} kq^{k-1}。

我们知道 Σ_{k=0}^{∞} q^k = 1/(1-q) = 1/p。对两边求导：

Σ_{k=1}^{∞} kq^{k-1} = 1/(1-q)² = 1/p²

因此 E[X] = p × 1/p² = 1/p ∎

无记忆性：P(X > m+n | X > m) = P(X > n)

解释：已经失败了m次，再失败n次的概率等于从一开始就失败n次的概率。过去的失败不影响未来。

应用：网络重传、抽奖、首次通过时间。

泊松分布

场景：单位时间内事件发生的次数，平均发生率为λ。

$$P(X = k) = \frac{\lambda^k e^{-\lambda}}{k!}$$

• E[X] = λ
• Var(X) = λ

与二项分布的关系：当n很大、p很小、np=λ时，Binomial(n,p) ≈ Poisson(λ)。

推导：lim_{n→∞} C(n,k)p^k(1-p)^{n-k} = λ^k e^{-λ}/k!（其中 p = λ/n）

应用：网站访问量、电话呼叫数、放射性衰变、排队论。

示例：某网站平均每分钟有10次访问。下一分钟恰好有15次访问的概率是多少？

解：X ~ Poisson(10)。

P(X=15) = 10¹⁵ e^{-10} / 15! ≈ 0.0347

负二项分布

场景：重复独立试验，直到获得r次成功。

X = 所需试验次数，成功概率为p。

$$P(X = k) = \binom{k-1}{r-1} p^r (1-p)^{k-r}$$

• E[X] = r/p
• Var(X) = r(1-p)/p²

解释：第k次试验必须是第r次成功（概率p），前k-1次试验中有r-1次成功（二项系数）。

特例：当r=1时，负二项分布退化为几何分布。

超几何分布

场景：从N个物品中不放回地抽取n个，其中M个是"成功"的。

X = 抽到的成功物品数。

$$P(X = k) = \frac{\binom{M}{k}\binom{N-M}{n-k}}{\binom{N}{n}}$$

• E[X] = nM/N
• Var(X) = n(M/N)(1-M/N)(N-n)/(N-1)

与二项分布的区别：超几何分布是不放回抽样，二项分布是放回抽样。当N很大时，两者近似相等。

应用：质量控制（批次检验）、彩票、捕获-再捕获估计种群大小。

7.5 概率不等式

马尔可夫不等式

如果X是非负随机变量，a > 0，则：

$$P(X \geq a) \leq \frac{E[X]}{a}$$

证明：考虑指示变量 I = 1 如果 X ≥ a，否则 I = 0。

则 aI ≤ X（因为如果I=1则X≥a，如果I=0则aI=0≤X）。

取期望：aE[I] ≤ E[X]。

但 E[I] = P(I=1) = P(X ≥ a)。

因此 aP(X ≥ a) ≤ E[X]，即 P(X ≥ a) ≤ E[X]/a ∎

直觉：如果平均值很小，取大值的概率也小。

示例：如果某系统的平均响应时间为100ms，那么响应时间超过500ms的概率最多是多少？

解：由马尔可夫不等式，P(X ≥ 500) ≤ 100/500 = 0.2 = 20%。

局限性：马尔可夫不等式给出的界限通常比较宽松，因为它只使用了期望值信息。

切比雪夫不等式

对于任意随机变量X和k > 0：

$$P(|X - E[X]| \geq k) \leq \frac{Var(X)}{k^2}$$

等价形式：P(|X - E[X]| ≥ kσ) ≤ 1/k²，其中σ是标准差。

证明：令 Y = (X - E[X])²。则 Y ≥ 0。

P(|X - E[X]| ≥ k) = P(Y ≥ k²)。

由马尔可夫不等式：P(Y ≥ k²) ≤ E[Y]/k² = Var(X)/k² ∎

应用：至少95%的数据落在均值±2标准差范围内（实际上对于正态分布是95%，但切比雪夫只保证至少75%）。

示例：某考试的平均分是70，标准差是10。分数在50到90之间的学生比例至少是多少？

解：50到90之间即距离均值不超过20 = 2σ。

由切比雪夫不等式：P(|X-70| ≥ 20) ≤ 1/4 = 25%。

因此 P(50 ≤ X ≤ 90) = P(|X-70| < 20) ≥ 75%。

优势：切比雪夫不等式适用于任何分布，不需要知道具体分布形式。

切尔诺夫界（Chernoff Bound）

对于独立伯努利试验的和X（二项分布），切尔诺夫界给出了更紧的界限：

$$P(X \geq (1+\delta)\mu) \leq \left(\frac{e^\delta}{(1+\delta)^{1+\delta}}\right)^\mu$$

其中 μ = E[X]，δ > 0。

特点：切尔诺夫界是指数级的，比切比雪夫的多项式界限更紧。

应用： randomized algorithms analysis, load balancing, concentration of measure.

7.6 大数定律

弱大数定律：对于独立同分布的随机变量X₁, X₂, ...，样本均值依概率收敛于期望值。

即：$\bar{X}_n = \frac{1}{n}\sum_{i=1}^{n} X_i \rightarrow E[X]$（当 n → ∞）

形式化：对任意 ε > 0，lim_{n→∞} P(|X̄ₙ - E[X]| ≥ ε) = 0。

证明思路（使用切比雪夫不等式）：

E[X̄ₙ] = E[X]

Var(X̄ₙ) = Var(X)/n

由切比雪夫不等式：

P(|X̄ₙ - E[X]| ≥ ε) ≤ Var(X̄ₙ)/ε² = Var(X)/(nε²)

当 n → ∞ 时，右边趋于0。∎

应用：蒙特卡洛模拟、民意调查、质量控制。

误解澄清：大数定律不意味着"补偿效应"。如果抛硬币连续出现10次正面，下一次仍然是50%正面。大数定律说的是长期平均会趋近期望，而不是短期偏差会被"纠正"。

强大数定律：样本均值几乎必然收敛于期望值（更强的收敛形式）。

7.7 联合分布与条件分布

联合分布

对于两个离散随机变量X和Y，联合概率质量函数为：

p(x,y) = P(X = x, Y = y)

性质：

• p(x,y) ≥ 0
• Σₓ Σᵧ p(x,y) = 1

边缘分布

从联合分布得到单个变量的分布：

p_X(x) = Σᵧ p(x,y)

p_Y(y) = Σₓ p(x,y)

条件分布

给定Y=y时X的条件分布：

p_{X|Y}(x|y) = P(X=x | Y=y) = p(x,y) / p_Y(y)

独立性

X和Y独立当且仅当 p(x,y) = p_X(x) · p_Y(y) 对所有x,y。

等价地：p_{X|Y}(x|y) = p_X(x)（条件分布等于边缘分布）。

7.8 概率生成函数

定义：离散随机变量X的概率生成函数（PGF）为：

G_X(s) = E[s^X] = Σ_{k=0}^{∞} P(X=k) s^k

性质：

• G_X(1) = 1
• G'_X(1) = E[X]
• G''_X(1) + G'_X(1) - [G'_X(1)]² = Var(X)

常见分布的PGF：

• 伯努利(p)：G(s) = 1-p + ps
• 二项(n,p)：G(s) = (1-p + ps)^n
• 泊松(λ)：G(s) = e^{λ(s-1)}
• 几何(p)：G(s) = ps / (1-(1-p)s)

应用：PGF可以用于求解随机变量的和的分布，特别是独立随机变量之和的PGF等于各PGF的乘积。

三、程序员的视角

3.1 在计算机科学中的应用

随机化算法

• 快速排序：随机选择pivot，期望时间 O(n log n)
• 哈希：随机哈希函数减少冲突
• 素性测试：米勒-拉宾测试是概率性的
• 最小割：Karger算法使用随机收缩
• 近似计数：使用蒙特卡洛方法估计#P问题

机器学习

• 朴素贝叶斯：基于贝叶斯定理的分类器
• A/B测试：统计显著性检验
• 强化学习：探索-利用权衡（ε-greedy、UCB）
• dropout：训练时的随机失活可以解释为集成学习

系统性能

• 队列理论：M/M/1队列的平均等待时间
• 负载均衡：随机分配任务的期望最大负载
• 缓存命中率：LRU策略的分析
• 可靠性：系统可用性的概率计算

网络安全

• 生日攻击：找到哈希碰撞需要约 2^{n/2} 次尝试
• 密码分析：差分密码分析使用概率特征
• 入侵检测：异常检测的概率阈值

3.2 常见陷阱与误区

赌徒谬误

认为过去的结果会影响未来独立事件的概率。例如："已经连续5次正面，下次一定是反面！"实际上每次抛硬币都是独立的。

正确理解：独立事件的未来概率不受过去影响。但如果是"至少一次正面"这样的复合事件，过去的结果确实会影响剩余需要的试验次数。

基础率忽视

在贝叶斯推理中忽视先验概率（基础率）。如前面的医学检测例子。

例子：恐怖分子检测。即使检测准确率很高，由于恐怖分子极其罕见，被检测为恐怖分子的人绝大多数是无辜的。

期望值的误解

期望值不一定是可能的结果，也不一定是"典型"结果。例如，彩票的期望值可能是负的，但仍有人中奖。

圣彼得堡悖论：一个游戏的期望收益是无限的，但人们只愿意支付有限的金额参与。这是因为效用函数不是线性的。

相关性不等于因果性

两个变量相关并不意味着一个导致另一个。可能存在混杂变量或纯粹是巧合。

例子：冰淇淋销量与溺水事故正相关，但这不是因为吃冰淇淋导致溺水，而是因为夏天两者都增加。

小样本偏差

小样本的统计结果可能不可靠。大数定律需要足够大的样本才能生效。

3.3 与其他层级的联系

• 硬件层：热噪声产生真随机数；量子随机数生成器
• 操作系统层：/dev/random 收集熵；进程调度的随机化
• 网络层：随机退避算法避免碰撞；随机路由
• 应用层：推荐系统的多样性；A/B测试框架

四、代码实战

7.1 概率计算工具

"""
离散概率计算工具
"""

import math
from collections import Counter
import random


def binomial_probability(n, p, k):
    """
    计算二项分布 P(X = k)
    
    参数:
        n: 试验次数
        p: 每次成功概率
        k: 成功次数
    """
    return math.comb(n, k) * (p ** k) * ((1 - p) ** (n - k))


def geometric_probability(p, k):
    """
    计算几何分布 P(X = k)
    
    参数:
        p: 成功概率
        k: 首次成功所需的试验次数
    """
    return (1 - p) ** (k - 1) * p


def poisson_probability(lam, k):
    """
    计算泊松分布 P(X = k)
    
    参数:
        lam: 平均发生率 λ
        k: 事件发生次数
    """
    return (lam ** k) * math.exp(-lam) / math.factorial(k)


def bayes_theorem(p_e_given_h, p_h, p_e_given_not_h):
    """
    贝叶斯定理
    
    参数:
        p_e_given_h: P(E|H)
        p_h: P(H)
        p_e_given_not_h: P(E|¬H)
    
    返回: P(H|E)
    """
    p_e = p_e_given_h * p_h + p_e_given_not_h * (1 - p_h)
    return (p_e_given_h * p_h) / p_e


def simulate_coin_toss(num_tosses=10, num_trials=10000):
    """
    模拟抛硬币实验
    
    返回: 正面次数的分布
    """
    results = []
    
    for _ in range(num_trials):
        heads = sum(random.choice([0, 1]) for _ in range(num_tosses))
        results.append(heads)
    
    counter = Counter(results)
    distribution = {k: v / num_trials for k, v in sorted(counter.items())}
    
    return distribution


def expected_value(values, probabilities):
    """
    计算期望值
    
    参数:
        values: 可能取值列表
        probabilities: 对应概率列表
    
    返回: 期望值
    """
    return sum(v * p for v, p in zip(values, probabilities))


def variance(values, probabilities):
    """
    计算方差
    
    参数:
        values: 可能取值列表
        probabilities: 对应概率列表
    
    返回: 方差
    """
    exp_val = expected_value(values, probabilities)
    return sum((v - exp_val) ** 2 * p for v, p in zip(values, probabilities))


def demonstrate_probability():
    """演示概率计算"""
    
    print("=== 二项分布 ===")
    n, p = 10, 0.5
    print(f"Binomial(n={n}, p={p})")
    print(f"{'k':>4} {'P(X=k)':>10}")
    print("-" * 20)
    
    for k in range(n + 1):
        prob = binomial_probability(n, p, k)
        print(f"{k:>4} {prob:>10.4f}")
    
    print(f"\n期望值: {n * p}")
    print(f"方差: {n * p * (1 - p)}")
    
    print("\n=== 贝叶斯定理：医学检测 ===")
    
    p_disease = 0.01  # 发病率
    p_positive_given_disease = 0.99  # 灵敏度
    p_negative_given_healthy = 0.99  # 特异性
    p_positive_given_healthy = 1 - p_negative_given_healthy
    
    p_disease_given_positive = bayes_theorem(
        p_positive_given_disease,
        p_disease,
        p_positive_given_healthy
    )
    
    print(f"发病率: {p_disease}")
    print(f"灵敏度: {p_positive_given_disease}")
    print(f"特异性: {p_negative_given_healthy}")
    print(f"P(患病|阳性) = {p_disease_given_positive:.4f}")
    
    print("\n=== 几何分布 ===")
    p = 0.3
    print(f"Geometric(p={p})")
    print(f"期望首次成功所需试验次数: {1/p:.2f}")
    
    for k in range(1, 6):
        prob = geometric_probability(p, k)
        print(f"  P(X={k}) = {prob:.4f}")
    
    print("\n=== 泊松分布 ===")
    lam = 5
    print(f"Poisson(λ={lam})")
    print(f"期望值: {lam}")
    
    for k in range(0, 11):
        prob = poisson_probability(lam, k)
        print(f"  P(X={k}) = {prob:.4f}")
    
    print("\n=== 模拟验证 ===")
    dist = simulate_coin_toss(10, 100000)
    print("抛10次硬币的模拟分布（10万次试验）:")
    for k, prob in sorted(dist.items()):
        theoretical = binomial_probability(10, 0.5, k)
        print(f"  {k}: 模拟={prob:.4f}, 理论={theoretical:.4f}")


if __name__ == "__main__":
    demonstrate_probability()

7.2 蒙特卡洛模拟

"""
蒙特卡洛方法：通过随机采样估计概率和期望
"""

import random
import math


def estimate_pi(num_samples=1000000):
    """
    通过蒙特卡洛方法估计π
    
    在单位正方形内随机撒点，落在内切圆内的比例约为 π/4
    """
    inside_circle = 0
    
    for _ in range(num_samples):
        x, y = random.random(), random.random()
        if x**2 + y**2 <= 1:
            inside_circle += 1
    
    pi_estimate = 4 * inside_circle / num_samples
    return pi_estimate


def estimate_expected_value(func, distribution_sampler, num_samples=100000):
    """
    估计随机变量函数的期望值
    
    参数:
        func: 函数 f(x)
        distribution_sampler: 采样函数，返回随机样本
        num_samples: 采样次数
    
    返回: E[f(X)] 的估计
    """
    total = 0
    
    for _ in range(num_samples):
        x = distribution_sampler()
        total += func(x)
    
    return total / num_samples


def birthday_problem_simulation(num_people=23, num_trials=10000):
    """
    模拟生日问题
    
    返回: 至少两人生日相同的概率估计
    """
    matches = 0
    
    for _ in range(num_trials):
        birthdays = [random.randint(1, 365) for _ in range(num_people)]
        if len(birthdays) != len(set(birthdays)):
            matches += 1
    
    return matches / num_trials


def monte_carlo_integration(func, a, b, num_samples=1000000):
    """
    通过蒙特卡洛方法估计定积分
    
    估计 ∫_a^b f(x) dx
    
    参数:
        func: 被积函数
        a: 积分下限
        b: 积分上限
        num_samples: 采样次数
    
    返回: 积分估计值
    """
    total = 0
    
    for _ in range(num_samples):
        x = random.uniform(a, b)
        total += func(x)
    
    return (b - a) * total / num_samples


def demonstrate_monte_carlo():
    """演示蒙特卡洛方法"""
    
    print("=== 估计 π ===")
    for samples in [10000, 100000, 1000000]:
        pi_est = estimate_pi(samples)
        error = abs(pi_est - math.pi)
        print(f"  采样 {samples:>10} 次: π ≈ {pi_est:.6f}, 误差: {error:.6f}")
    
    print("\n=== 生日问题 ===")
    for n in [10, 20, 23, 30, 50]:
        prob = birthday_problem_simulation(n, 5000)
        # 理论值
        prob_no_match = 1.0
        for i in range(n):
            prob_no_match *= (365 - i) / 365
        theoretical_prob = 1 - prob_no_match
        print(f"  {n}人: 模拟≈{prob:.4f}, 理论={theoretical_prob:.4f}")
    
    print("\n=== 估计期望值 ===")
    
    # 估计标准正态分布的绝对值的期望
    def absolute_value(x):
        return abs(x)
    
    def normal_sampler():
        return random.gauss(0, 1)
    
    est = estimate_expected_value(absolute_value, normal_sampler, 100000)
    theoretical = math.sqrt(2 / math.pi)
    
    print(f"  E[|Z|] where Z~N(0,1):")
    print(f"  估计值: {est:.4f}")
    print(f"  理论值: {theoretical:.4f}")
    
    print("\n=== 蒙特卡洛积分 ===")
    
    # 估计 ∫_0^1 x^2 dx = 1/3
    def square(x):
        return x ** 2
    
    est = monte_carlo_integration(square, 0, 1, 1000000)
    print(f"  ∫₀¹ x² dx ≈ {est:.6f} (理论值: 0.333333)")
    
    # 估计 ∫_0^1 e^(-x^2) dx
    def gaussian(x):
        return math.exp(-x ** 2)
    
    est = monte_carlo_integration(gaussian, 0, 1, 1000000)
    print(f"  ∫₀¹ e^(-x²) dx ≈ {est:.6f}")


if __name__ == "__main__":
    demonstrate_monte_carlo()

7.3 概率分布可视化

"""
概率分布可视化和分析
"""

import math


def print_distribution_bar_chart(prob_dict, title="概率分布"):
    """
    以文本条形图形式打印概率分布
    
    参数:
        prob_dict: {值: 概率} 字典
        title: 图表标题
    """
    print(f"\n=== {title} ===")
    
    max_prob = max(prob_dict.values())
    bar_width = 40
    
    for value, prob in sorted(prob_dict.items()):
        bar_length = int(bar_width * prob / max_prob)
        bar = '█' * bar_length
        print(f"  {value:>4}: {prob:.4f} {bar}")


def compare_distributions(dist1, dist2, name1="分布1", name2="分布2"):
    """
    比较两个分布
    
    参数:
        dist1, dist2: {值: 概率} 字典
        name1, name2: 分布名称
    """
    print(f"\n=== 分布比较: {name1} vs {name2} ===")
    print(f"{'值':>4} | {name1:>10} | {name2:>10} | {'差异':>10}")
    print("-" * 45)
    
    all_values = sorted(set(list(dist1.keys()) + list(dist2.keys())))
    
    for value in all_values:
        p1 = dist1.get(value, 0)
        p2 = dist2.get(value, 0)
        diff = abs(p1 - p2)
        print(f"{value:>4} | {p1:>10.4f} | {p2:>10.4f} | {diff:>10.4f}")


def compute_statistics(values, probabilities):
    """
    计算分布的统计量
    
    参数:
        values: 可能取值列表
        probabilities: 对应概率列表
    
    返回: 期望值、方差、标准差
    """
    exp_val = sum(v * p for v, p in zip(values, probabilities))
    var_val = sum((v - exp_val) ** 2 * p for v, p in zip(values, probabilities))
    std_val = math.sqrt(var_val)
    
    return exp_val, var_val, std_val


def demonstrate_distribution_analysis():
    """演示分布分析"""
    
    print("=== 二项分布不同参数的比较 ===")
    
    n = 20
    for p in [0.3, 0.5, 0.7]:
        dist = {}
        for k in range(n + 1):
            prob = math.comb(n, k) * (p ** k) * ((1 - p) ** (n - k))
            if prob > 0.001:  # 只显示显著概率
                dist[k] = prob
        
        exp_val = n * p
        var_val = n * p * (1 - p)
        
        print(f"\np={p}: E[X]={exp_val}, Var(X)={var_val:.2f}")
        print_distribution_bar_chart(dist, f"Binomial(n={n}, p={p})")


if __name__ == "__main__":
    demonstrate_distribution_analysis()

五、深入思考

5.1 历史背景

概率论起源于17世纪的赌博问题。布莱兹·帕斯卡和皮埃尔·德·费马通过通信解决了"点数分配问题"。雅各布·伯努利证明了大数定律，这是概率论的第一个极限定理。皮埃尔-西蒙·拉普拉斯发展了中心极限定理，并将概率论应用于天体力学和社会科学。

安德雷·柯尔莫哥洛夫在1933年建立了概率论的公理体系，将概率论置于坚实的数学基础之上。理查德·冯·米塞斯发展了频率学派观点。布鲁诺·德·菲内蒂发展了主观概率（贝叶斯学派）观点。

信息论之父克劳德·香农将概率论应用于信息传输，开创了现代通信理论。

5.2 前沿方向

• 概率编程：将概率模型嵌入编程语言（如Pyro、Stan、WebPPL）
• 贝叶斯深度学习：结合贝叶斯方法和神经网络，提供不确定性估计
• 差分隐私：在数据分析中保护个人隐私，通过添加噪声实现
• 随机矩阵理论：在高维统计、量子物理、金融中的应用
• 最优传输理论：研究概率分布之间的最优映射
• 因果推断：从观测数据中推断因果关系，超越相关性

5.3 延伸阅读

• 《Introduction to Probability》by Dimitri P. Bertsekas and John N. Tsitsiklis
• 《Probability and Computing》by Michael Mitzenmacher and Eli Upfal
• 《The Probabilistic Method》by Alon and Spencer
• 《Bayesian Data Analysis》by Gelman et al.
• 《Information Theory, Inference, and Learning Algorithms》by David MacKay

六、实验笔记

实验1：概率模拟器

目标：创建一个交互式概率实验模拟器。

任务：

实现抛硬币、掷骰子、抽牌等基本实验

统计频率分布并与理论值比较

可视化收敛过程（频率趋近概率）

支持自定义实验

实现置信区间计算

提交物：可运行的程序、可视化图表、收敛分析报告。

扩展挑战：

• 实现假设检验功能
• 支持多变量实验
• 实时可视化更新

实验2：贝叶斯推理实践

目标：应用贝叶斯定理解决实际问题。

任务：

实现朴素贝叶斯分类器

用真实数据集（如垃圾邮件过滤）测试

分析先验对结果的影响

讨论模型的局限性

实现拉普拉斯平滑处理零概率问题

提交物：源代码、实验报告、分类准确率、混淆矩阵。

扩展挑战：

• 比较不同先验的效果
• 实现半朴素贝叶斯（考虑特征间的相关性）
• 应用到文本分类以外的领域

实验3：蒙特卡洛方法探索

目标：深入理解蒙特卡洛方法的原理和应用。

任务：

实现多种蒙特卡洛积分方法

比较不同采样策略的效率

实现重要性采样

应用到实际问题的数值计算

提交物：源代码、效率比较报告、误差分析。

扩展挑战：

• 实现马尔可夫链蒙特卡洛（MCMC）
• 应用到高维积分
• 方差缩减技术研究

七、本章小结

本章介绍了离散概率的基础。概率空间由样本空间、事件域和概率函数组成，遵循柯尔莫哥洛夫公理。条件概率描述了已知某些信息时事件的概率，贝叶斯定理提供了更新信念的方法，是现代统计学和机器学习的核心工具。

独立性是概率论的核心概念，独立事件的联合概率等于边缘概率的乘积。但要注意，两两独立不一定意味着相互独立。

随机变量将结果量化，期望值是长期平均，方差衡量离散程度。期望的线性性是一个非常强大的工具，不需要独立性假设。

常见离散分布包括均匀分布、二项分布、几何分布、泊松分布等，每种分布对应特定的随机场景。理解这些分布的性质有助于选择合适的模型。

概率不等式（马尔可夫、切比雪夫、切尔诺夫）提供了无需知道完整分布就能给出的界限，在算法分析中特别有用。

大数定律保证了大量独立试验的平均值趋近期望值，这是蒙特卡洛方法的理论基础。但要注意，这不意味着"补偿效应"。

概率思维是一种重要的认知工具，帮助我们处理不确定性、做出理性决策。

八、习题

习题1（基础）：抛一枚公平硬币3次，求：

(a) 恰好2次正面的概率

(b) 至少1次正面的概率

(c) 全部相同的概率

(d) 给定第一次是正面，恰好2次正面的条件概率

习题2（基础）：从一副52张扑克牌中随机抽取2张，求两张都是A的概率。

习题3（中等）：某种疾病的发病率是0.1%，检测准确率为95%（即P(+|有病)=0.95, P(-|没病)=0.95）。如果某人检测为阳性，他真正患病的概率是多少？如果再次检测仍为阳性呢？

习题4（中等）：证明如果X ~ Binomial(n, p)，则 E[X] = np。

习题5（中等）：一个公平的六面骰子掷n次，求至少出现一次6的概率。n至少为多少时这个概率超过0.9？

习题6（较难）：使用切比雪夫不等式证明：对于任何随机变量X，P(|X - E[X]| ≥ 2σ) ≤ 1/4。并说明这个界限是否紧致。

习题7（较难）：设计一个蒙特卡洛算法估计定积分 ∫₀¹ e^(-x²) dx，并分析其收敛速度。

习题8（挑战）：研究并实现马尔可夫链的基本模拟，验证平稳分布的存在性。

习题9（挑战）：证明二项分布当n→∞, p固定时的正态近似（德莫弗-拉普拉斯定理的特殊情况）。

习题10（开放）：选择一个实际应用（如金融风险评估、网络流量分析、医疗诊断），建立概率模型并分析。包括：

• 问题描述和建模假设
• 使用的概率分布和参数估计
• 计算过程和结果
• 模型的局限性和改进方向