Appearance
概率论与数理统计
概念
前两篇讲的是"确定的数学"——微积分算出一条曲线的形状，线性代数算出一个变换的结果，给定了输入就有唯一输出。
这一篇要处理的是：
它不是"猜"——它是"用一套严格的规则，把不确定的事情量化成可以算的数"。
一篇拆成两个部分，问三个问题：
| 问题 | 属于 | 用什么回答 |
|---|---|---|
| ① 一个随机的量怎么描述？ | 概率论 | 随机变量 + 分布 + 期望/方差 |
| ② 拿到一堆数据，怎么反推背后的规律？ | 数理统计 | 点估计、区间估计、假设检验 |
| ③ "很多个小随机量加起来"会变成什么？ | 极限定理 | 大数定律、中心极限定理 |
为什么主线需要它——因为计算机里到处是"随机"和"平均"：
| 落点 | 概率在算什么 |
|---|---|
arch Cache | 命中率 H 是频率，平均访存时间 EAT 是期望 |
arch 性能评价 | "某程序平均 CPI"就是加权平均（离散期望） |
ds 散列表 | 平均查找长度 ASL 是期望（soft/12-index.md 也用它） |
os 调度与排队 | 服务时间服从指数分布；平均等待时间是一个积分（期望） |
net 可靠性 | 误码率、重传次数的分布 |
soft 机器学习 | 最大似然估计就是"选让数据最可能出现的参数" |
| 性能测量（本院） | 置信区间与显著性检验——"这个优化到底是不是真的快了" |
⚠️ 本篇的边界：讲"主线用到的那一层"——基本公式、常见分布、期望方差、点估计与区间估计、两个极限定理。 更深入的（回归分析、方差分析、抽样调查）只在需要时点一句。
本篇在主线上的位置：
math这门课三篇"通用工具"的最后一篇——离散数学给 L1，微积分给elec/auto，线性代数给soft，而概率统计给的是"性能评价"这整套方法论。 本站凡是出现"命中率""平均值""加速比"的地方，背后都是这一篇。
原理
一、概率的基本规则
样本空间 Ω：所有可能结果的集合；事件 A：Ω 的一个子集；概率 P(A)：给每个事件一个 [0,1] 的数。
三条公理：① P(A) ≥ 0；② P(Ω) = 1；③ 互不相容的事件之并的概率等于概率之和。 其余规则全部从这三条推出来。
四个必背公式：
| 公式 | 形式 |
|---|---|
| 加法 | P(A∪B) = P(A) + P(B) − P(A∩B)（与容斥原理同构，见 math/01-discrete.md） |
| 条件概率 | P(A∣B) = P(A∩B)/P(B)（P(B) > 0） |
| 乘法 | P(A∩B) = P(A∣B)P(B) = P(B∣A)P(A) |
| 全概率 | P(B) = Σᵢ P(B∣Aᵢ)P(Aᵢ)（Aᵢ 是完备事件组） |
贝叶斯公式（把条件反过来）：
读法："先验概率 P(Aᵢ) × 似然 P(B|Aᵢ)，再归一化。" 它的直觉是：
"结果出现了，回头修正我对原因的信念。" "检测呈阳性"不代表"一定有病"——因为"没病却呈阳性"的人可能远多于"有病且呈阳性"的人。 例 1 会把这个数算出来。
⚠️ 互斥与独立：这不是一回事（最高频的错）：
| 概念 | 定义 | 直觉 |
|---|---|---|
| 互斥（互不相容） | P(A∩B) = 0 | "不可能同时发生" |
| 独立 | P(A∩B) = P(A)P(B)，即 P(A∣B) = P(A) | "一个发生了，不改变另一个的概率" |
两个致命反例： ① 两个非零概率的互斥事件一定不独立——因为一个发生后另一个的概率变成 0，被改变了； ② 独立事件可以同时发生——"抛两次硬币都正面"是独立的，但不是互斥的。
一句话分辨：互斥是"集合关系"（交集为空），独立是"概率关系"（乘积分解）。
二、随机变量：期望与方差
随机变量 X：把每个结果映射成一个数的函数。 分两类：
| 类型 | 取值 | 描述方式 |
|---|---|---|
| 离散型 | 可数个值 | 分布律 P(X = xᵢ) = pᵢ |
| 连续型 | 区间上的值 | 密度函数 f(x)（P(X = x) = 0！） |
期望（均值）：
方差（离散程度）：
"平方的期望减去期望的平方"是最好用的计算公式。
四条线性性质（背下来，主线天天用）：
| 性质 | 形式 | 要不要独立 |
|---|---|---|
| 常数可提（期望） | E(aX + b) = aE(X) + b | 不要 |
| 和的期望 | E(X + Y) = E(X) + E(Y) | 不要（这是期望最强的性质） |
| 常数可提（方差） | Var(aX + b) = a² Var(X) | 不要（注意 b 不见了、a 要平方） |
| 和的方差 | Var(X + Y) = Var(X) + Var(Y) + 2\mathrm{Cov}(X,Y) | 独立时 Cov = 0 才可拆 |
最后一行是最高频的失分点："和的期望一定等于期望的和"，但"和的方差等于方差的和"只在独立（或不相关）时成立。 主线里的对应现象：两个部件串联的延迟是"直接相加"（确定性），而两个随机任务的等待时间相加时，波动会叠加——
os排队论里"波动叠加"就是Var(X+Y) = Var(X)+Var(Y)。
常用分布的期望与方差（这张表必须背下来）：
| 分布 | 记号 | 参数含义 | 期望 | 方差 |
|---|---|---|---|---|
| 0-1 分布 | B(1, p) | 一次试验成功概率 | p | p(1−p) |
| 二项分布 | B(n, p) | n 次独立试验的成功次数 | np | np(1−p) |
| 几何分布 | G(p) | 首次成功所需的试验次数 | 1/p | (1−p)/p² |
| 泊松分布 | P(λ) | 单位时间发生次数 | λ | λ |
| 均匀分布 | U(a,b) | 区间上等可能 | (a+b)/2 | (b−a)²/12 |
| 指数分布 | E(λ) | 等待时间的速率 | 1/λ | 1/λ² |
| 正态分布 | N(μ, σ²) | 均值与方差 | μ | σ² |
三个"务必记住其物理含义"的分布：
- 几何分布："试到成功为止要几次"；无记忆性（
P(X > m+n | X > m) = P(X > n)）——"已经等了很久"不等于"快来了"； - 泊松分布："
E = Var = λ"这一条非常独特——均值等于方差的分布不多；λ大时形状趋近正态； - 指数分布：
os里"服务时间/到达间隔"的标准假设——P(X > t) = e^{−λt}，这也是math/10-calculus.md里那个e的用武之地；同样无记忆。
正态分布的"三西格玛"（工程上的尺子）：
| 区间 | 覆盖概率 |
|---|---|
μ ± 1σ | 68.27% |
μ ± 2σ | 95.45% |
μ ± 3σ | 99.73% |
μ ± 1.96σ | 95.00%（置信区间的常客） |
三、大数定律与中心极限定理
大数定律（说的是"平均会稳定"）：
含义："试验次数多了，频率趋近期望"——这是"用模拟去验证概率"能成立的根本理由（本篇例 2、例 4 全靠它）。
中心极限定理（CLT，说的是"和会变成正态"）：
三条要害：
| 要害 | 内容 |
|---|---|
① 不要求 Xᵢ 是正态 | 只要独立同分布、方差有限，和多了一定像正态 |
② 收敛速度是 1/√n | X̄ 的标准差 = σ/√n——"想精确一倍，样本要四倍" |
| ③ 这是"平均值能当估计用"的依据 | 置信区间、A/B 测试、蒙特卡洛的误差，全由 1/√n 决定 |
1/√n是工程上最值钱的一条经验："多测 4 倍时间，误差才减半"——做性能基准测试、做蒙特卡洛积分，预算怎么分配，就看这个平方根。
四、数理统计：从样本反推总体
基本区分：
| 概念 | 含义 |
|---|---|
| 总体 | 我们想了解、但通常看不到全貌的那个分布 |
| 样本 | 实际观测到的 n 个独立同分布的数据 X₁…Xₙ |
| 统计量 | 样本的函数（如样本均值 X̄、样本方差 S²）——统计量本身也是随机变量 |
点估计两法：
| 方法 | 做法 | 例子（估 U(0, θ) 的 θ） |
|---|---|---|
| 矩估计 | 用样本矩 = 总体矩，解出参数 | E(X) = θ/2 = X̄ → θ̂ = 2X̄ |
| 最大似然（MLE） | 选让"观测到这批数据"的概率最大的参数 | θ̂ = max(X₁…Xₙ) |
评价估计量的三条标准：无偏（期望等于真值）、有效（方差更小）、一致（样本增多时收敛到真值）。
区间估计（比点估计更有用）——σ 已知时的均值置信区间：
95% 置信对应 z = 1.96。 读法要小心："反复抽样 100 次，约 95 次构造出的区间会盖住真值"——不是"真值有 95% 的概率落在这一次算出的区间里"。
假设检验五步：
| 步 | 内容 |
|---|---|
| ① | 提出原假设 H₀ 与备择假设 H₁ |
| ② | 选检验统计量（如 z = (X̄ − μ₀)/(σ/√n)） |
| ③ | 定显著性水平 α（常取 0.05）与拒绝域 |
| ④ | 算统计量的观测值 |
| ⑤ | 落在拒绝域就拒绝 H₀，否则"不拒绝"（不是"接受"） |
两类错误（务必分清）：
| 错误 | 含义 | 概率 | 记法 |
|---|---|---|---|
| 第一类（弃真） | H₀ 为真却拒绝 | α | "冤枉好人" |
| 第二类（取伪） | H₀ 为假却没拒绝 | β | "放过坏人" |
"α 与 β 不能同时变小，除非增大样本量"——这就是"为什么做实验要多测几组"。
五、概率统计在主线的五个落点
| 落点 | 具体算什么 |
|---|---|
arch Cache | 命中率 H → EAT = H·T_c + (1−H)·T_m |
arch 性能 | 平均 CPI 是加权平均 |
ds 散列表 | 平均查找长度 ASL 是期望 |
os 排队 | 服务时间指数分布；平均等待时间 = 期望 |
| 性能验收 | 置信区间与显著性检验 |
示例
例 1：贝叶斯——"检测呈阳性"到底意味着什么
python
import unicodedata
def w(s):
return sum(2 if unicodedata.east_asian_width(c) in "WF" else 1 for c in s)
def pad(s, n):
return s + " " * max(0, n - w(s))
SENS = 0.99 # 灵敏度：真有病时检出阳性的概率 P(+|D)
SPEC = 0.95 # 特异度：真没病时判阴性的概率 P(−|¬D)
def posterior(prior, sens=SENS, spec=SPEC):
p_pos = prior * sens + (1 - prior) * (1 - spec) # 全概率
return prior * sens / p_pos, p_pos # 贝叶斯
print("=== 主算例：患病率 1% ===")
prior = 0.01
p_post, p_pos = posterior(prior)
print(" 患病率（先验） P(D) = %.4f" % prior)
print(" 灵敏度 P(+|D) = %.4f" % SENS)
print(" 特异度 P(−|¬D) = %.4f → 假阳性率 P(+|¬D) = %.4f" % (SPEC, 1 - SPEC))
print()
print(" 全概率：P(+) = P(+|D)P(D) + P(+|¬D)P(¬D)")
print(" = %.4f × %.4f + %.4f × %.4f" % (SENS, prior, 1 - SPEC, 1 - prior))
print(" = %.6f + %.6f = %.6f" % (SENS * prior, (1 - SPEC) * (1 - prior), p_pos))
print(" 贝叶斯：P(D|+) = %.6f / %.6f = %.6f = %.2f%%" % (SENS * prior, p_pos, p_post, p_post * 100))
print(" ★ 阳性者里只有 %.2f%% 真的患病 —— 因为「1%% 里的 99%%」（%.4f）远小于" % (p_post * 100, SENS * prior))
print(" 「99%% 里的 5%%」（%.4f）：分母被假阳性撑大了" % ((1 - SPEC) * (1 - prior)))
print()
print("=== 先验变化时，后验怎么变 ===")
print(" " + pad("患病率 P(D)", 14) + pad("P(+)", 12) + pad("P(D|+)", 12) + "解读")
for prior in (0.001, 0.01, 0.10, 0.50, 0.90):
pp, ppos = posterior(prior)
note = "阳性几乎没意义" if pp < 0.1 else ("阳性较可信" if pp < 0.6 else "阳性基本确诊")
print(" " + pad("%.3f" % prior, 14) + pad("%.6f" % ppos, 12) + pad("%.4f" % pp, 12) + note)
print(" ★ 同一个检测，先验不同 → 后验天差地别：这就是「基础率谬误」")预期输出：
=== 主算例：患病率 1% ===
患病率（先验） P(D) = 0.0100
灵敏度 P(+|D) = 0.9900
特异度 P(−|¬D) = 0.9500 → 假阳性率 P(+|¬D) = 0.0500
全概率：P(+) = P(+|D)P(D) + P(+|¬D)P(¬D)
= 0.9900 × 0.0100 + 0.0500 × 0.9900
= 0.009900 + 0.049500 = 0.059400
贝叶斯：P(D|+) = 0.009900 / 0.059400 = 0.166667 = 16.67%
★ 阳性者里只有 16.67% 真的患病 —— 因为「1% 里的 99%」（0.0099）远小于
「99% 里的 5%」（0.0495）：分母被假阳性撑大了
=== 先验变化时，后验怎么变 ===
患病率 P(D) P(+) P(D|+) 解读
0.001 0.050940 0.0194 阳性几乎没意义
0.010 0.059400 0.1667 阳性较可信
0.100 0.144000 0.6875 阳性基本确诊
0.500 0.520000 0.9519 阳性基本确诊
0.900 0.896000 0.9944 阳性基本确诊
★ 同一个检测，先验不同 → 后验天差地别：这就是「基础率谬误」例 2：五个分布的期望与方差 + 模拟验证（大数定律）
python
import math, random, unicodedata
def w(s):
return sum(2 if unicodedata.east_asian_width(c) in "WF" else 1 for c in s)
def pad(s, n):
return s + " " * max(0, n - w(s))
random.seed(20260929)
N = 200000
def sim_bernoulli(p):
return 1 if random.random() < p else 0
def sim_binom(n, p):
return sum(sim_bernoulli(p) for _ in range(n))
def sim_geom(p):
k = 1
while random.random() >= p:
k += 1
return k
def sim_poisson(lam):
# Knuth 算法：连乘到小于 e^(-λ)
L, k, prod = math.exp(-lam), 0, 1.0
while True:
k += 1
prod *= random.random()
if prod <= L:
return k - 1
def sim_expon(lam):
return -math.log(1 - random.random()) / lam
def sim_uniform(a, b):
return a + (b - a) * random.random()
CASES = [
("B(1, 0.3)", lambda: sim_bernoulli(0.3), 0.3, 0.3 * 0.7),
("B(20, 0.3)", lambda: sim_binom(20, 0.3), 20 * 0.3, 20 * 0.3 * 0.7),
("G(0.2)", lambda: sim_geom(0.2), 1 / 0.2, (1 - 0.2) / 0.2 ** 2),
("P(3)", lambda: sim_poisson(3), 3.0, 3.0),
("E(2)", lambda: sim_expon(2), 1 / 2, 1 / 2 ** 2),
("U(0,1)", lambda: sim_uniform(0, 1), 0.5, 1 / 12),
]
print("=== 每个分布采样 %d 次，比较理论值与模拟值 ===" % N)
print(" " + pad("分布", 12) + pad("理论 E", 12) + pad("模拟 E", 12) + pad("理论 Var", 12)
+ pad("模拟 Var", 12) + "E 的相对误差")
for name, gen, th_e, th_v in CASES:
xs = [gen() for _ in range(N)]
m = sum(xs) / N
v = sum((x - m) ** 2 for x in xs) / N
print(" " + pad(name, 12) + pad("%.6f" % th_e, 12) + pad("%.6f" % m, 12)
+ pad("%.6f" % th_v, 12) + pad("%.6f" % v, 12)
+ "%.4f%%" % (abs(m - th_e) / th_e * 100 if th_e else 0))
print()
print(" ★ 模拟值与理论值都在小数点后第 2~3 位吻合 —— 这是大数定律在起作用（N = %d）" % N)
print(" ★ 注意 P(3) 的 E 与 Var 理论值都是 3；E(2) 的 Var = 1/4 = 0.25")
print(" ★ 模拟误差量级 ≈ 标准差/√N：以 B(20,0.3) 为例，sd = %.4f，sd/√N = %.6f"
% (math.sqrt(20 * 0.3 * 0.7), math.sqrt(20 * 0.3 * 0.7) / math.sqrt(N)))
print()
print("=== 几何分布的无记忆性（离散版） ===")
p = 0.2
print(" P(X > 3) = (1-p)^3 = %.6f" % (1 - p) ** 3)
print(" P(X > 5 | X > 3) = P(X > 2) = (1-p)^2 = %.6f" % (1 - p) ** 2)
print(" ★ 「已经等了 3 次」完全不影响「还要再等几次」—— 无记忆性")预期输出：
=== 每个分布采样 200000 次，比较理论值与模拟值 ===
分布 理论 E 模拟 E 理论 Var 模拟 Var E 的相对误差
B(1, 0.3) 0.300000 0.300940 0.210000 0.210375 0.3133%
B(20, 0.3) 6.000000 5.997925 4.200000 4.189821 0.0346%
G(0.2) 5.000000 5.013665 20.000000 20.312568 0.2733%
P(3) 3.000000 2.996650 3.000000 2.992639 0.1117%
E(2) 0.500000 0.498946 0.250000 0.247481 0.2107%
U(0,1) 0.500000 0.500481 0.083333 0.083505 0.0961%
★ 模拟值与理论值都在小数点后第 2~3 位吻合 —— 这是大数定律在起作用（N = 200000）
★ 注意 P(3) 的 E 与 Var 理论值都是 3；E(2) 的 Var = 1/4 = 0.25
★ 模拟误差量级 ≈ 标准差/√N：以 B(20,0.3) 为例，sd = 2.0494，sd/√N = 0.004583
=== 几何分布的无记忆性（离散版） ===
P(X > 3) = (1-p)^3 = 0.512000
P(X > 5 | X > 3) = P(X > 2) = (1-p)^2 = 0.640000
★ 「已经等了 3 次」完全不影响「还要再等几次」—— 无记忆性例 3：Cache 命中率与平均访存时间（arch 落点）
python
import unicodedata
def w(s):
return sum(2 if unicodedata.east_asian_width(c) in "WF" else 1 for c in s)
def pad(s, n):
return s + " " * max(0, n - w(s))
Tc, Tm = 1.0, 100.0 # Cache 命中时的访问时间 / 主存访问时间（ns）
def eat(H, tc=Tc, tm=Tm):
return H * tc + (1 - H) * tm
print("=== 平均访存时间 EAT = H·Tc + (1−H)·Tm（Tc = %g ns，Tm = %g ns） ===" % (Tc, Tm))
print(" " + pad("命中率 H", 12) + pad("未命中率", 12) + pad("EAT (ns)", 12) + pad("相对无 Cache", 16) + "比上一行的改善")
prev = None
for H in (0.90, 0.95, 0.99, 0.999):
e = eat(H)
gain = "—" if prev is None else "−%.4f ns" % (prev - e)
print(" " + pad("%.3f" % H, 12) + pad("%.3f" % (1 - H), 12) + pad("%.4f" % e, 12)
+ pad("%.4f 倍" % (Tm / e), 16) + gain)
prev = e
print(" 无 Cache（每次都访存）：%.4f ns" % Tm)
print()
print(" ★ 命中率 90%% → 95%%：EAT 从 %.4f 降到 %.4f，省 %.4f ns" % (eat(0.9), eat(0.95), eat(0.9) - eat(0.95)))
print(" 命中率 95%% → 99%%：省 %.4f ns；99%% → 99.9%%：只省 %.4f ns"
% (eat(0.95) - eat(0.99), eat(0.99) - eat(0.999)))
print(" → 边际收益递减，但「最后那一个 9」往往最贵（容量/相联度/代价都在这一档）")
print()
print("=== 反推：想让 EAT 不超过 2 ns，命中率至少要多少 ===")
target = 2.0
H_need = (Tm - target) / (Tm - Tc)
print(" 解 H·%.0f + (1−H)·%.0f ≤ %.1f ⇒ H ≥ (%.0f − %.1f)/(%.0f − %.0f) = %.6f"
% (Tc, Tm, target, Tm, target, Tm, Tc, H_need))
print(" 即命中率需 ≥ %.4f（约 %.2f%%），实际工程取 ≥ %.2f%% 留余量"
% (H_need, H_need * 100, 0.99 * 100))预期输出：
=== 平均访存时间 EAT = H·Tc + (1−H)·Tm（Tc = 1 ns，Tm = 100 ns） ===
命中率 H 未命中率 EAT (ns) 相对无 Cache 比上一行的改善
0.900 0.100 10.9000 9.1743 倍 —
0.950 0.050 5.9500 16.8067 倍 −4.9500 ns
0.990 0.010 1.9900 50.2513 倍 −3.9600 ns
0.999 0.001 1.0990 90.9918 倍 −0.8910 ns
无 Cache（每次都访存）：100.0000 ns
★ 命中率 90% → 95%：EAT 从 10.9000 降到 5.9500，省 4.9500 ns
命中率 95% → 99%：省 3.9600 ns；99% → 99.9%：只省 0.8910 ns
→ 边际收益递减，但「最后那一个 9」往往最贵（容量/相联度/代价都在这一档）
=== 反推：想让 EAT 不超过 2 ns，命中率至少要多少 ===
解 H·1 + (1−H)·100 ≤ 2.0 ⇒ H ≥ (100 − 2.0)/(100 − 1) = 0.989899
即命中率需 ≥ 0.9899（约 98.99%），实际工程取 ≥ 99.00% 留余量例 4：中心极限定理、1/√n 与蒙特卡洛
python
import math, random, unicodedata
def w(s):
return sum(2 if unicodedata.east_asian_width(c) in "WF" else 1 for c in s)
def pad(s, n):
return s + " " * max(0, n - w(s))
random.seed(42)
SIGMA = math.sqrt(1 / 12) # U(0,1) 的标准差 = 0.288675…
print("=== ① 样本均值的标准差 = σ/√n（CLT 的量化形式） ===")
print(" σ = 1/√12 = %.6f" % SIGMA)
print(" " + pad("n", 8) + pad("理论 σ/√n", 16) + pad("模拟 σ/√n", 16) + "相对误差")
M = 20000 # 每次模拟抽 20000 组样本
for n in (1, 2, 5, 30, 100):
means = []
for _ in range(M):
s = 0.0
for _ in range(n):
s += random.random()
means.append(s / n)
m = sum(means) / M
sd = math.sqrt(sum((x - m) ** 2 for x in means) / M)
th = SIGMA / math.sqrt(n)
print(" " + pad(str(n), 8) + pad("%.6f" % th, 16) + pad("%.6f" % sd, 16)
+ "%.3f%%" % (abs(sd - th) / th * 100))
print(" ★ n 从 1 增到 100（×100），σ/√n 缩小到 1/10（√100）—— 精度只按平方根换")
print(" ★ 这是 CLT 的量化形式：均值分布的「宽度」按 σ/√n 收缩；n 越大形状也越接近正态")
print(" （形状可用偏度/峰度或直方图再看一眼，本篇只验证「宽度」这一条最常用的结论）")
print()
print("=== ② 1/√n 的工程含义：想精确一倍，样本要四倍 ===")
print(" " + pad("样本量 n", 12) + pad("σ/√n", 14) + pad("相对 n=100", 14) + "要多少倍工作量")
base = SIGMA / 10
for n in (100, 400, 1600, 10000):
v = SIGMA / math.sqrt(n)
print(" " + pad(str(n), 12) + pad("%.6f" % v, 14) + pad("%.4f" % (v / base), 14)
+ "%.0f 倍" % (n / 100))
print(" ★ 误差减半 ⇒ 样本 ×4：性能基准测试的时长预算就是这么定的")
print()
print("=== ③ 蒙特卡洛估 π：误差也是 1/√N ===")
print(" " + pad("点数 N", 12) + pad("π 估计", 14) + pad("误差", 12) + pad("理论 sd", 12) + "误差/(理论 sd)")
for N in (1000, 10000, 100000, 1000000):
hit = 0
for _ in range(N):
x, y = random.random(), random.random()
if x * x + y * y <= 1.0:
hit += 1
est = 4.0 * hit / N
p = math.pi / 4
sd = 4.0 * math.sqrt(p * (1 - p) / N)
print(" " + pad(str(N), 12) + pad("%.6f" % est, 14) + pad("%.6f" % abs(est - math.pi), 12)
+ pad("%.6f" % sd, 12) + "%.3f" % (abs(est - math.pi) / sd))
print(" π = %.6f" % math.pi)
print(" ★ N 每增 10 倍，理论 sd 缩小 √10 ≈ %.3f 倍；实测误差就在 sd 的同一量级" % math.sqrt(10))预期输出：
=== ① 样本均值的标准差 = σ/√n（CLT 的量化形式） ===
σ = 1/√12 = 0.288675
n 理论 σ/√n 模拟 σ/√n 相对误差
1 0.288675 0.288769 0.032%
2 0.204124 0.204543 0.205%
5 0.129099 0.128802 0.231%
30 0.052705 0.052429 0.523%
100 0.028868 0.029022 0.536%
★ n 从 1 增到 100（×100），σ/√n 缩小到 1/10（√100）—— 精度只按平方根换
★ 这是 CLT 的量化形式：均值分布的「宽度」按 σ/√n 收缩；n 越大形状也越接近正态
（形状可用偏度/峰度或直方图再看一眼，本篇只验证「宽度」这一条最常用的结论）
=== ② 1/√n 的工程含义：想精确一倍，样本要四倍 ===
样本量 n σ/√n 相对 n=100 要多少倍工作量
100 0.028868 1.0000 1 倍
400 0.014434 0.5000 4 倍
1600 0.007217 0.2500 16 倍
10000 0.002887 0.1000 100 倍
★ 误差减半 ⇒ 样本 ×4：性能基准测试的时长预算就是这么定的
=== ③ 蒙特卡洛估 π：误差也是 1/√N ===
点数 N π 估计 误差 理论 sd 误差/(理论 sd)
1000 3.164000 0.022407 0.051930 0.431
10000 3.144000 0.002407 0.016422 0.147
100000 3.147440 0.005847 0.005193 1.126
1000000 3.139224 0.002369 0.001642 1.442
π = 3.141593
★ N 每增 10 倍，理论 sd 缩小 √10 ≈ 3.162 倍；实测误差就在 sd 的同一量级例 5：散列表平均查找长度（ds 落点）与置信区间
python
import math, random, unicodedata
def w(s):
return sum(2 if unicodedata.east_asian_width(c) in "WF" else 1 for c in s)
def pad(s, n):
return s + " " * max(0, n - w(s))
print("=== ① 链地址法：成功 ASL = 1 + α/2，不成功 ASL = α ===")
print(" " + pad("装填因子 α", 14) + pad("成功 ASL", 12) + pad("不成功 ASL", 14) + "说明")
for a in (0.25, 0.5, 0.75, 1.0, 2.0):
print(" " + pad("%.2f" % a, 14) + pad("%.4f" % (1 + a / 2), 12) + pad("%.4f" % a, 14)
+ ("链会变长，性能开始明显下滑" if a >= 1.0 else "工程推荐区间"))
print(" ★ 装填因子 α = 元素数 / 桶数；链地址法的成功 ASL 对 α 是线性的（1 + α/2）")
print()
print("=== ② 模拟验证（链地址法） ===")
random.seed(7)
M = 1000 # 桶数
for a in (0.5, 0.75):
N = int(M * a)
buckets = [[] for _ in range(M)]
for k in range(N):
buckets[random.randrange(M)].append(k)
total = sum(len(b) * (len(b) + 1) // 2 for b in buckets)
asl = total / N if N else 0
print(" α = %.2f（N = %d，M = %d）：模拟成功 ASL = %.4f，理论 1 + α/2 = %.4f"
% (a, N, M, asl, 1 + a / 2))
print(" ★ 一次成功查找的比较次数 = 「在链上的位置」（第 k 个元素比 k 次），")
print(" 把每条链的 1+2+…+L 累加再除以 N，就得到 1 + α/2")
print()
print("=== ③ 置信区间：抛 1000 次硬币出现 517 次正面，能说明硬币不公平吗 ===")
n, hits = 1000, 517
phat = hits / n
se = math.sqrt(phat * (1 - phat) / n)
z = 1.96
lo, hi = phat - z * se, phat + z * se
print(" 样本比例 p̂ = %d/%d = %.4f" % (hits, n, phat))
print(" 标准误 SE = √(p̂(1−p̂)/n) = √(%.6f×%.6f/%d) = %.6f" % (phat, 1 - phat, n, se))
print(" 95%% 置信区间 = p̂ ± 1.96·SE = %.4f ± %.6f = [%.4f, %.4f]" % (phat, z * se, lo, hi))
print(" 区间覆盖 0.5 吗？ %s" % ("是 → 证据不足以说硬币不公平" if lo <= 0.5 <= hi else "否 → 拒绝 H0"))
z_obs = (phat - 0.5) / se
print(" 检验 H0: p = 0.5：z = (p̂ − 0.5)/SE = %.4f，临界值 ±1.96" % z_obs)
bound = math.ceil((0.5 + z * se) * n)
print(" 要拒绝 H0，正面次数需 ≥ %d 或 ≤ %d；本次 %d 落在中间" % (bound, n - bound, hits))
verdict = "拒绝 H0（硬币不公平）" if abs(z_obs) > z else "不拒绝 H0（差异不显著）"
print(" → %s" % verdict)
print(" ★ 注意「不拒绝」≠「接受」：只能说证据不足，不能说硬币就是公平的")预期输出：
=== ① 链地址法：成功 ASL = 1 + α/2，不成功 ASL = α ===
装填因子 α 成功 ASL 不成功 ASL 说明
0.25 1.1250 0.2500 工程推荐区间
0.50 1.2500 0.5000 工程推荐区间
0.75 1.3750 0.7500 工程推荐区间
1.00 1.5000 1.0000 链会变长，性能开始明显下滑
2.00 2.0000 2.0000 链会变长，性能开始明显下滑
★ 装填因子 α = 元素数 / 桶数；链地址法的成功 ASL 对 α 是线性的（1 + α/2）
=== ② 模拟验证（链地址法） ===
α = 0.50（N = 500，M = 1000）：模拟成功 ASL = 1.2480，理论 1 + α/2 = 1.2500
α = 0.75（N = 750，M = 1000）：模拟成功 ASL = 1.3800，理论 1 + α/2 = 1.3750
★ 一次成功查找的比较次数 = 「在链上的位置」（第 k 个元素比 k 次），
把每条链的 1+2+…+L 累加再除以 N，就得到 1 + α/2
=== ③ 置信区间：抛 1000 次硬币出现 517 次正面，能说明硬币不公平吗 ===
样本比例 p̂ = 517/1000 = 0.5170
标准误 SE = √(p̂(1−p̂)/n) = √(0.517000×0.483000/1000) = 0.015802
95% 置信区间 = p̂ ± 1.96·SE = 0.5170 ± 0.030972 = [0.4860, 0.5480]
区间覆盖 0.5 吗？ 是 → 证据不足以说硬币不公平
检验 H0: p = 0.5：z = (p̂ − 0.5)/SE = 1.0758，临界值 ±1.96
要拒绝 H0，正面次数需 ≥ 531 或 ≤ 469；本次 517 落在中间
→ 不拒绝 H0（差异不显著）
★ 注意「不拒绝」≠「接受」：只能说证据不足，不能说硬币就是公平的考点
考点
1. 四个公式
- 加法：
P(A∪B) = P(A) + P(B) − P(A∩B)； - 条件：
P(A|B) = P(A∩B)/P(B)； - 乘法：
P(A∩B) = P(A|B)P(B)； - 全概率：
P(B) = Σ P(B|Aᵢ)P(Aᵢ)； - 贝叶斯：
P(Aᵢ|B) = P(B|Aᵢ)P(Aᵢ) / Σ P(B|Aⱼ)P(Aⱼ)（"先验 × 似然，再归一化"）。
2. 互斥 ≠ 独立（最高频易错）
| 定义 | 关系 | |
|---|---|---|
| 互斥 | P(A∩B) = 0 | 两个概率非零的互斥事件一定不独立 |
| 独立 | P(A∩B) = P(A)P(B) | 独立事件可以同时发生 |
"互斥看集合交集，独立看概率乘积。"
3. 期望与方差的四条性质
E(aX+b) = aE(X) + b（常数可提）；E(X+Y) = E(X) + E(Y)（无条件成立，最强的一条）；Var(aX+b) = a²Var(X)（b消失，a平方）；Var(X+Y) = Var(X) + Var(Y) + 2Cov(X,Y)（只有独立/不相关才能拆成两项）；- 计算式：
Var(X) = E(X²) − [E(X)]²。
4. 五个必背分布的 E 与 Var
| 分布 | E | Var |
|---|---|---|
B(1,p) | p | p(1−p) |
B(n,p) | np | np(1−p) |
G(p) | 1/p | (1−p)/p² |
P(λ) | λ | λ |
U(a,b) | (a+b)/2 | (b−a)²/12 |
E(λ) | 1/λ | 1/λ² |
N(μ,σ²) | μ | σ² |
- 泊松的
E = Var = λ；几何与指数分布都有无记忆性； - 正态三西格玛：
1σ→68.27%、2σ→95.45%、3σ→99.73%；1.96σ→95%。
5. 两个极限定理
- 大数定律：
X̄ → μ（"频率趋近期望"——模拟验证的理论依据）； - 中心极限定理：
(ΣXᵢ − nμ)/(σ√n) → N(0,1)（不要求原始分布是正态）； - 推论：
X̄的标准差 =σ/√n——"精度翻倍要样本 ×4"。
6. 统计三件套
- 点估计：矩估计（
θ̂ = 2X̄）与最大似然（θ̂ = max(Xᵢ)）；评价标准：无偏 / 有效 / 一致； - 区间估计（
σ已知）：X̄ ± z_{α/2} · σ/√n，95% 对应z = 1.96； - 假设检验五步：
H₀/H₁→ 统计量 →α→ 拒绝域 → 结论； - 两类错误：第一类（弃真）概率
α；第二类（取伪）概率β——"只能靠增大样本量同时减小"。
7. 主线三个"概率算式"（必须会套）
| 场景 | 公式 |
|---|---|
| Cache 平均访存时间 | EAT = H·T_c + (1 − H)·T_m |
| 散列表（链地址） | 成功 ASL = 1 + α/2；不成功 ASL = α |
| 性能测量的置信区间 | p̂ ± 1.96·√(p̂(1−p̂)/n) |
8. 本节六个高频易错点
- 互斥 ≠ 独立（两个非零概率的互斥事件必然不独立）；
Var(aX+b) = a²Var(X)：b不影响方差，a要平方；E(XY) = E(X)E(Y)需要独立，而E(X+Y) = E(X)+E(Y)不需要——两个方向的"能不能拆"要分清；- 连续型
P(X = x) = 0：概率为 0 不等于不可能发生； - "不拒绝
H₀" ≠ "接受H₀"：只能说证据不足； - 置信区间的正确读法："反复抽样时区间盖住真值的比例"，不是"真值落在本次区间的概率"。
小结
- 概率论 = 不确定性的量化：三个问题——随机变量怎么描述、样本怎么反推参数、很多小随机量加起来会怎样。
- 四个公式：加法、条件、乘法、全概率/贝叶斯；贝叶斯的算式就是"先验 × 似然 → 后验"。
- 互斥 ≠ 独立：前者是"不能同时发生"，后者是"互不影响"——这是最高频的失分点。
- 期望与方差：
E(aX+b) = aE(X)+b、Var(aX+b) = a²Var(X)；和的期望无条件可拆，和的方差要独立才能拆。 - 五个必背分布：二项
np/np(1−p)、几何1/p、泊松λ/λ、指数1/λ/1/λ²、正态μ/σ²。 - 两个极限定理：大数定律管"平均会稳定"，中心极限定理管"和会变正态"；核心经验是
σ/√n——精度翻倍要样本四倍。 - 统计三件套：点估计（矩估计 / 最大似然）、区间估计（
±1.96·SE）、假设检验（两类错误α/β）。 - 三个手算锚点：患病率 1%、灵敏度 99%、特异度 95% →
P(D|+) = 1/6 ≈ 16.67%；Tc=1ns、Tm=100ns、命中率 95% →EAT = 5.95 ns；链地址法α=0.75的成功ASL = 1.375。
回到主线：这一篇是 math 三篇"通用工具"的收尾。
它把主线里到处出现、但一直没点明的那个词补上了出处——"平均"。①
arch的 "平均访存时间EAT"：H·Tc + (1−H)·Tm就是离散随机变量的期望；②arch的"平均CPI"、ds的"平均查找长度ASL"：同样是加权平均（期望）；③os的"平均等待时间"：服务时间取指数分布，P(X > t) = e^{−λt}，积分求期望——把math/10的积分与这里的分布接上了；④ 而"这个优化到底有没有变快"：不能只看一次测量，要用1/√n决定测多少次、用置信区间下结论。至此
math的通用工具三篇（微积分 / 线性代数 / 概率统计）齐了——加上开篇的离散数学，工具层"按需取用"的四个抽屉都有了东西。
下面两篇转向"按需选修"：math/20-numeric.md 讲"计算机到底怎么用有限位算出这些数"（误差从哪来、为什么稳定性比算法快慢更重要），math/21-complex.md 讲复变函数与积分变换（它是 elec 信号与系统的直接前置）。
下一篇：数值分析（可选）
评论（0）
当前浏览器不允许本地存储，评论无法保存。
还没有评论，来说两句。