概率方法第三版：从存在性证明到局部引理与随机图相变

简介：《The Probabilistic Method》第三版英文原版PDF，面向数学与计算机科学方向的研究生、教师及科研人员，系统讲解如何借助概率论工具证明组合对象的存在性并分析随机算法，适合组合数学、图论、理论计算机与复杂性理论等方向的学习者。全书以随机化证明为主线，覆盖二项式系数与组合恒等式、大数定律与中心极限定理、Ramsey数与边色数等图论结论、纠错码与信息论、算法平均情况分析、零一法律及Lovász局部引理，并配有较丰富的例子说明定理的使用条件，阅读前需具备概率论、图论和线性代数基础。资源包仅含1个PDF文件，大小约7.77MB，便于在电脑或平板上查阅与检索。目前已有150人学习，适合作为课程补充读物或研究时的工具书，帮助读者建立概率方法的证明思路并迁移到自身课题中。

1. 一本把「存在性」变成可计算问题的书

卡在「要证明存在一个满足某组约束的组合结构，但构造不出来、枚举又是指数级」这种局面上，是很多人第一次认真翻《The Probabilistic Method》第三版的真实动机。这本书讲的不是概率论入门，而是一整套把存在性命题改写成概率陈述的工具箱：不构造具体对象，而是在一个精心设计的概率空间里随机取一个对象，证明它满足全部约束的概率严格大于零。适合两类人：写论文需要给出非构造性下界的研究生，以及做随机算法、图算法、编码设计时需要一个「能不能行」的判据的工程师。第三版在原有方法篇之外补了随机图相变、图性质测试和去随机化，方法篇仍是主干。

2. 期望、改变与二阶矩：三种存在性证明怎么分工

三种工具看起来都在算概率，实际解决的问题完全不一样。期望法回答「有没有」，改变法回答「坏结构太多怎么办」，二阶矩回答「除了存在，是不是还很常见」。选错工具的典型症状是：明明用期望法已经推出 E[X]<1，却还在死磕 P(X=0) 的精确表达式；或者明明坏结构之间存在强相关，却拿并集界硬算，最后界差出好几个数量级。这一章按「能算什么 → 为什么能算 → 参数怎么定 → 什么时候失效」的顺序把三种工具拆开。

2.1 基本方法的三段式：概率空间、坏事件、正概率

基本方法的流程固定得像模板：先定义随机对象，再定义「坏事件」——对象不满足目标性质这件事，最后证明坏事件的概率严格小于 1。以两色完全图的临界数 R(k,k) 为例，随机给 K_n 的每条边独立地染红或蓝，一共 2^{C(n,2)} 种等概率染色。坏事件是「存在一个 k 点全红团或者全蓝团」，用并集界处理：

P(坏) ≤ C(n,k) · 2 · 2^{-C(k,2)} = C(n,k) · 2^{1-C(k,2)}

只要这个上界严格小于 1，就存在一种染色既没有红 K_k 也没有蓝 K_k，于是 R(k,k) > n。这里有个容易被忽略的点：并集界丢掉了坏事件之间的全部重叠信息，算出来的上界是保守的，但这恰好是它好用的原因——不需要知道任意两个单色团是否共存，也不需要处理它们之间的相关性。代价是界偏松，对 k 稍大一点，能推出来的 n 就明显低于真实值。

把这一步落成可跑的东西，关键不是算 C(n,k)，而是防止浮点溢出。C(200,50) 这种量级直接算会炸，转到对数域就没问题：

from math import comb, log2 def max_n_for_k(k, n_max=400): """返回满足 C(n,k)*2^(1-C(k,2)) < 1 的最大 n，即 R(k,k) > n 的保证范围""" best = 0 for n in range(k, n_max + 1): # 全部转到以 2 为底的对数域，避免 C(n,k) 溢出 log2_bound = log2(comb(n, k)) + 1 - comb(k, 2) if log2_bound < 0: # 等价于原不等式严格小于 1 best = n else: break # C(n,k) 关于 n 单调增，后面只会更差 return best for k in range(4, 11): print(k, max_n_for_k(k))

这段代码有两个参数值得改：n_max决定搜索上限，k 大时要往上调；break依赖 C(n,k) 对 n 的单调性，改成不做 break 而是继续扫也不会改变结果，只是多跑几轮。逻辑上还有一个隐含假设：comb(n,k)在 n<k 时返回 0，所以起点必须从k开始，否则log2(0)会直接抛异常。跑出来的数字不用和真实临界值比，能稳定复现「k=10 时保证 n 至少到某个值」这个结论就够了，剩下的差距是并集界的固有损耗，不是代码写错了。

2.2 期望法：为什么算 E[X] 比算 P(X=0) 便宜

并集界只回答「坏事件一个都不发生」的概率上界，而期望法把问题改写成计数：设 X 是坏结构的个数，X 是随机变量，E[X] 是它的平均值。如果 E[X] < 1，那么必然存在一个实例使 X = 0——否则每个实例至少有一个坏结构，X ≥ 1 处处成立，平均值就不可能低于 1。这个论证只有一行，但它绕开了「坏事件之间是否独立」这个通常算不动的核心难点，因为期望的线性性不需要任何独立性假设。

实际用的时候，E[X] 通常写成「坏结构总数 × 单个坏结构出现的概率」。以超图的可二染色问题为例，如果每个坏结构是一个最小不可二染色子图，单个出现的概率是 2^{-s}（s 是它的边数），总数是 m，那么 E[X] = m·2^{-s}。条件 m < 2^s 就保证了存在一种二染色让所有坏结构都被破坏。

这套做法的失效信号很明确：当 E[X] 算出来是 0.98 这种贴着 1 的值时，结论仍然成立，但毫无余量，任何一点上界估计的粗糙都可能把结论吃掉。另一个更隐蔽的失效是「E[X] < 1 但 X 的取值不是非负整数」——如果 X 被定义成某种加权和，平均值小于 1 并不能推出存在 X = 0 的实例，这时候要么改成计数型随机变量，要么改用别的工具。

2.3 改变法：删掉坏结构比修好它更划算

有一类问题里 E[X] 大得离谱，期望法直接失效，但结构本身「很接近正确」：随机取一个对象，它只有少数几个局部缺陷，删掉涉及缺陷的那几个元素就能得到合法的子结构。改变法的标准动作是：随机生成 → 计算每个元素平均卷入多少个坏结构 → 删掉所有卷入坏结构的元素 → 估计剩下多少。

模板大致是这样：设共有 m 个坏结构，每个坏结构涉及至多 b 个元素，总元素数是 n。随机选出的对象里坏结构个数的期望是 E[X]，那么平均每个元素卷入的坏结构数是 E[X]·b/n（这里用「涉及」而不是「包含」，是因为一个坏结构可能重复计入多个元素，取上界即可）。删掉所有卷入坏结构的元素之后，坏结构一定全没了，剩下的元素个数至少是 n 减去被删掉的个数。而被删掉的元素个数不超过 E[X]·b，所以剩下的规模至少是 n - E[X]·b。

这套推导的价值在于它给出的不是「存在一个」，而是「存在一个规模至少多大的」。独立性数的下界、某些打包问题的下界都是这么来的。参数上唯一要小心的是 b 的取法：b 取的是单个坏结构涉及的元素数上限，取大了结论变弱但不会错，取小了结论直接崩。经验做法是先用精确的涉及数算一遍，再故意用宽松的 b 算一遍，如果两次结论差距超过一个数量级，说明 b 的估计有问题，应该回去重新数。

2.4 二阶矩：方差告诉你「不只是存在」

期望法证明的是「至少有一个」，但很多场景需要更强的东西：这个性质是不是普遍成立？典型对象是不是都满足？这时候看方差。设 X 是非负整数值随机变量，那么

P(X = 0) ≤ Var[X] / E[X]²

推导只用了一步切比雪夫型的不等式：X = 0 蕴含 |X - E[X]| = E[X]，于是 P(X=0) ≤ P(|X-E[X]| ≥ E[X]) ≤ Var[X]/E[X]²。只要方差比期望的平方小一个量级，X = 0 的概率就被压得很低，性质就不是「碰巧存在」，而是「绝大多数对象都满足」。

方差的计算是这条路上最容易翻车的地方。Var[X] = Σ Var[X_i] + Σ_{i≠j} Cov(X_i, X_j)，初学者最常见的错误是只算第一项，也就是把所有坏结构当成互相独立。当坏结构共享元素时，协方差项可能是同阶甚至主导的。判断要不要算协方差项有个便宜的办法：先只算 Σ Var[X_i]，如果这个值已经远小于 E[X]²，那协方差项再大也不太可能翻盘；如果两者同阶，就必须老老实实把相关项拆开，通常按「共享一个元素」「共享两个元素」分类求和。

2.5 三者的选择表与参数怎么定

选工具不用凭感觉，看三个信号：坏结构数量是否可控、坏结构之间是否强相关、结论需要「存在」还是「普遍」。

参数定法上有个通用习惯：先把所有不等式写成「左边是待估计量、右边是显式表达式」的形式，把常数全部保留，最后一步再代入具体数值。中途做近似（比如把 (1-1/n)^n 当成 e^{-1}）会让最终结论的适用范围模糊掉——书里大量结论是渐近的，落地时必须反解出「n 至少多大才成立」，这个反解过程里任何一个提前近似都会让门槛失真。

3. 局部引理：依赖图少画一条边，结论就废了

并集界要求坏事件概率之和小于 1，一旦坏事件数量上千，这个条件就基本不可能满足。局部引理换了个角度：不要求和小于 1，只要求每个坏事件「只和少数几个坏事件相关」，且单个概率足够小。它把全局条件拆成局部条件，是这本书里实用价值最高、同时也最容易被误用的一节。

3.1 依赖图不是「相关图」：边怎么画才算安全

依赖图的定义很严格：把每个坏事件画成一个顶点，如果两个坏事件涉及同一组随机变量，就在它们之间连边。注意这里是「涉及同一组变量」，不是「统计上相关」。很多事件在统计上高度相关但变量集合不相交，按定义它们之间没有边；反过来，两个事件变量集合相交，即使实际相关性很弱，也必须连边。

这个定义方向决定了依赖图只能往多了画，不能往少了画。少画一条边的后果不是界变松，而是结论直接错——局部引理的证明依赖「给定一个事件的全部邻居之后，它和其余事件条件独立」，这条性质一旦被破坏，整个归纳就塌了。实际排查时有个保守做法：先按变量集合严格连边，算一遍 d；再人为把 d 放大一倍算一遍。如果两次结论方向一致，说明你对依赖结构的理解没问题；如果放大一倍之后条件就不满足了，说明原来的余量本来就很薄，实际落地时要格外小心。

3.2 对称版与一般版的参数换算

对称版的条件最好记：设每个坏事件的概率不超过 p，依赖图中每个顶点的度不超过 d，如果

e · p · (d + 1) ≤ 1

那么所有坏事件同时不发生的概率严格为正。这个式子里的 e 是自然常数，不是误差项，很多人第一次用时会把 (d+1) 写成 d，边界就偏了。为什么是 d+1 而不是 d：归纳过程中需要把「自己」也算进去，写成 d 会得到一个略强的错误条件。

一般版放弃了对所有事件用同一个上界，改成给每个事件配一个权 x_i ∈ (0,1)，条件是

P(A_i) ≤ x_i · Π_{j ∈ Γ(i)} (1 - x_j)

对称版是它的特例（所有 x_i 取同一个值 1/(d+1)）。一般版的价值在于处理「概率不均匀」的场景：少数几个事件概率特别大、其余都很小，对称版会被那几个大的拖死，一般版可以给大的配大权、小的配小权，条件宽松不少。

3.3 算法化版本：从「存在」到「能跑出来」的代价

局部引理的原版是非构造性的：它告诉你「存在一个所有坏事件都不发生的赋值」，但没告诉你怎么找。算法化版本补上了这一步，做法是重采样：随便给一个初始赋值，找到当前被违反的坏事件，只对它的变量集合重新随机赋值，重复直到没有坏事件为止。只要每个坏事件涉及的变量数有上界、且概率条件比存在性版本更强一些，这个过程期望意义下收敛。

代价体现在两个方面。一是条件收紧：存在性版本要求 e·p·(d+1) ≤ 1，算法版本在变量数较大时往往需要 p 再小一个量级，实操中经常出现「书上的定理说存在，但算法跑不出来」的情况，不是算法实现错了，是条件没到。二是每轮重采样的范围：只重置被违反事件涉及的变量，还是重置它的整个邻域，收敛速度差别很大。工程上我一般先按最小范围重采样，跑固定轮数不收敛再扩大到邻域，扩大到邻域仍不收敛就回头检查 p 和 d 的估计。

3.4 用一段脚本校验你的 p 和 d 是否达标

局部引理的参数校验适合写成脚本，因为手算 e·p·(d+1) 很容易在量级上出错。下面这段同时做对称版判定和一般版的数值求解：

import math def symmetric_ok(p, d): """对称版：e * p * (d + 1) <= 1 时，全部坏事件同时不发生的概率为正""" return math.e * p * (d + 1) <= 1.0, math.e * p * (d + 1) def general_ok(probs, neighbors, iters=500): """一般版：迭代求最小可行权 x_i，返回 (是否可行, 权向量) neighbors[i] 是事件 i 在依赖图中的邻居下标列表""" n = len(probs) x = [0.1] * n # 初始权，取小一点保证单调上升 for _ in range(iters): new_x = [] for i in range(n): prod = 1.0 for j in neighbors[i]: prod *= (1.0 - x[j]) # 解 x_i * prod >= p_i 的最小可行 x_i，并夹到 (0,1) xi = probs[i] / prod if prod > 1e-12 else 1.0 new_x.append(min(0.999, max(xi, 1e-9))) if max(abs(a - b) for a, b in zip(new_x, x)) < 1e-9: x = new_x break x = new_x # 回代校验，留 1e-12 容差抵掉浮点误差 ok = all(probs[i] <= x[i] * math.prod(1 - x[j] for j in neighbors[i]) + 1e-12 for i in range(n)) return ok, x # 例：8 个坏事件，每个概率 1e-3，依赖图是一个 3-正则图 probs = [1e-3] * 8 neighbors = [[(i - 1) % 8, (i + 1) % 8, (i + 3) % 8] for i in range(8)] print(symmetric_ok(1e-3, 3)) print(general_ok(probs, neighbors))

symmetric_ok返回布尔值和实际算出来的乘积，第二项特别有用：0.98 和 0.02 都判定为可行，但余量完全不同，后者说明结论很稳，前者说明参数一动就崩。general_ok的迭代逻辑是求最小不动点，初始权取 0.1 是为了让迭代从下往上收敛，如果初值取 0.9，迭代可能在可行域里来回震荡。iters是兜底轮数，正常规模几十轮就收敛，跑到 500 轮还没收敛基本可以判定不可行。这个脚本只做数值校验，不构成证明——它给出的是「按这组参数，一般版的条件看起来满足」，最终结论仍要回到定理的严格形式。

4. 集中不等式与泊松范式：把「存在」推到「几乎必然」

前面三章解决的都是「存在」，但工程上更常问的是「这个量会不会偏离期望太远」和「一堆事件里一个都不发生的概率有多大」。这两个问题分别对应鞅集中和泊松范式，前者管单个随机变量的尾部，后者管大量弱相关事件的联合稀疏性。

4.1 有界差分的鞅不等式：什么时候集中是免费的

设 Y = f(X_1, ..., X_n)，X_i 相互独立，且改变任意一个 X_i 时 Y 的变化量不超过 c_i，那么

P(|Y - E[Y]| ≥ t) ≤ 2·exp(-2t² / Σ c_i²)

这个不等式的好处是几乎不需要知道 Y 的分布，只要变化量有界就能用。判断能不能用的标准很简单：把 f 写成对每个坐标的依赖，逐个估计「换掉一个坐标最多影响多少」，如果这个影响不随 n 增长，集中就是免费的；如果某个坐标的影响随 n 线性增长（比如 f 是最大值函数，换一个坐标可能让最大值从 1 跳到 n），这个不等式就什么都给不出。

实际估计 c_i 时的常见错误是按平均影响算，正确做法是按最坏影响算。举一个排序相关的例子：Y 是某个统计量，改变一个输入可能让整个排序结构重排，这时最坏影响远大于平均影响，用平均影响估 c_i 会得到一个过于乐观的界。经验做法是先找「最敏感的那个坐标」，单独估它的 c，其余取一个宽松上界，这样得到的 Σc_i² 虽然偏大，但结论是可靠的。

4.2 联合事件不等式：μ 和 Δ 两个量的用法

设有一族坏事件 A_1, ..., A_m，μ = Σ P(A_i)，Δ = Σ_{i~j} P(A_i ∧ A_j)（i~j 指两个事件在依赖图里相邻），则

P(一个坏事件都不发生) ≤ exp(-μ + Δ)

μ 是「期望发生多少个」，Δ 是对两两同时发生的修正。当 Δ 远小于 μ 时，不等式退化成泊松形式，坏事件的数量近似服从泊松分布；当 Δ 和 μ 同阶时，修正项吃掉大部分余量，界变得很松，这时候说明事件之间的相关太强，泊松范式不适用。

用这个不等式之前要先想清楚两件事：事件族是不是足够稀疏（μ 不能大到每个位置都出事），以及相关性是不是局部化的（强相关只发生在近邻之间）。两条都满足，结论通常很好用；有一条不满足，要么换工具，要么把事件族重新切分，让它变稀疏。

4.3 随机图相变：临界窗口为什么难讲清楚

随机图 G(n, p) 里 p = c/n 是分水岭。c < 1 时最大连通块只有 O(log n)，c > 1 时突然冒出一个 Θ(n) 规模的巨片。这条结论的证明思路是分支过程：从一个顶点出发做广度优先搜索，它在每一层「生出」的新顶点数近似服从参数为 c 的泊松分布，泊松分布均值小于 1 时分支过程必然灭绝，大于 1 时有正概率存活。

难讲清楚的是临界窗口。p = 1/n + λn^{-2/3} 这个尺度上，最大连通块的大小是 n^{2/3} 量级，三种形态（次临界、临界、超临界）在这里交界，直接用分支过程近似会失效，因为不同分支之间的碰撞不能忽略。工程上如果只是做参数选型，避开这个窗口就行：要么让 c 明显小于 1，要么让 c 明显大于 1.5，落在窗口里讨论「到底有没有巨片」意义不大。

4.4 数值验证：用并查集把巨片位置跑出来

相变的结论可以用几十行代码验证，不依赖任何图论库。用并查集维护连通块，逐条边做合并，最后取最大块的大小：

import random def giant_ratio(n, c, trials=5): """经验估计 G(n, c/n) 中最大连通块占顶点数的比例""" total = 0.0 for _ in range(trials): parent = list(range(n)) size = [1] * n def find(a): while parent[a] != a: parent[a] = parent[parent[a]] # 路径压缩 a = parent[a] return a p = c / n for i in range(n): for j in range(i + 1, n): if random.random() < p: ri, rj = find(i), find(j) if ri != rj: # 按大小合并，控制树高 if size[ri] < size[rj]: ri, rj = rj, ri parent[rj] = ri size[ri] += size[rj] total += max(size) return total / trials / n for c in (0.5, 0.8, 0.99, 1.5, 3.0): print(c, round(giant_ratio(1200, c), 4))

参数说明：n控制在几千以内，因为边枚举是 O(n²)，n=1200 单次约 72 万次抽样，五次跑下来几秒钟，n 上到 5000 就明显慢了，需要改成按几何分布跳采样。trials取 5 是权衡方差和耗时，c 接近 1 时方差大，要取到 20 以上才稳。c是平均度，也是这条曲线的唯一控制参数。跑出来的比值在 c=0.5 和 c=0.8 时应该很小（低于 0.02），c=1.5 和 c=3.0 时应该跳到 0.5 以上——这个跳变的位置就是相变点，和理论值 1 对得上，误差来自有限 n 和临界窗口的宽度。

5. 避坑：读这本证明书最容易翻车的五个地方

这本书的证明平均长度不到两页，但每一步省略的推导都可能让人卡半天。下面五个坑是我自己反复踩、也见过别人反复踩的，按「现象 → 原因 → 解决」写清楚。

5.1 坑一：证明看懂了，实例还是拿不出来

现象是定理读完觉得没问题，回头想写代码验证，发现根本不知道从哪下手，因为证明从头到尾没给过任何构造步骤。

原因在于这类证明的性质：它只说明「满足条件的对象构成的空间非空」，路径是「假设全都不满足，推出矛盾」。矛盾推出来就结束了，构造过程从来没有出现在证明里。改变法稍微好一点，因为它至少给出了「删掉哪些元素」这个动作，但删完之后剩下的结构长什么样，证明并不关心。

解决办法是分清「存在性结论」和「可构造结论」，要在读的时候标记出来。如果只需要一个下界或者一个反例存在性，非构造性证明够用；如果要真的跑出实例，就得去找算法化版本，或者退一步用随机化搜索：按证明里的概率分布随机采样，检查是否满足性质，重复到命中为止。后者在参数有余量时通常几百次内就能命中，余量很薄时会直接卡死，卡死本身就是个信号——说明这个参数点落在理论界的边缘，实际不可用。

5.2 坑二：依赖图少画了边，局部引理给出错误结论

现象是按自己画的依赖图算出 d=5、p=0.01，e·p·(d+1) ≈ 0.16 远小于 1，结论应该很稳，但拿具体例子一测就发现反例。

原因是依赖图漏了隐式依赖。最常见的情况是事件之间通过一个全局约束耦合：比如所有事件都依赖「总和不超过某个值」这个条件，变量集合两两不交，但给定其他事件之后，剩余事件的概率分布会变。按变量集合连边，这种情况一条边都不画，可实际上它们强相关。

解决办法是改用更保守的连边规则：只要两个事件的概率在给定对方之后发生变化，就认为它们相邻。判断方法是手算一两个 P(A_i | A_j) 和 P(A_i) 对比，差得明显就连边。这个规则会把依赖图变密、条件变严，但结论不会错。另一个办法是先按严格规则算一遍，再把 d 乘 2 重算，两次都通过才放心用。

5.3 坑三：并集界用过头，界和真实值差好几个数量级

现象是坏事件只有十几个，套并集界算出来概率上界是 3.7，完全没信息量，但直觉上这些事件同时发生的可能性很小。

原因是并集界完全不管事件之间的重叠。当坏事件高度重叠（比如都涉及同一批高频元素）时，ΣP(A_i) 会把同一块概率重复计入很多次，上界虚高得离谱。事件越相关，并集界越没用。

解决办法是先看事件之间是否近似互斥或强相关，如果是，改用联合事件不等式，用 Δ 修正重叠部分；如果事件之间近似独立，直接用乘积形式 P(∩¬A_i) ≈ Π(1-P(A_i)) 会比并集界强得多，虽然这不再是严格上界，但配合局部引理可以恢复严格性。判断该用哪个：算一下 μ 和 Δ 的比值，Δ/μ 小于 0.1 就用泊松形式，大于 0.5 就说明重叠严重，得换思路。

5.4 坑四：渐近结论直接套小规模数据

现象是书上的定理写「对充分大的 n 成立」，直接拿 n=50 去用，结果和定理说的完全相反。

原因是渐近结论里的「充分大」是个未定常数，证明过程中通常做了好几处「n 大于某个常数时成立」的放缩，这些常数从没被显式算出来过。有些定理的证明里 o(1) 项在 n=10⁶ 时才降到 0.01 以下，n=50 时它比主项还大。

解决办法是把证明里的每一次放缩反解成显式不等式。具体做法是跟着证明走一遍，把每一处「对充分大的 n，A(n) ≤ B(n)」都写成 A(n) ≤ B(n) 的具体条件，最后取所有条件的交集。这个过程很烦，但反解出来的 n 门槛往往和直觉差好几个数量级。如果反解成本太高，退而求其次：做数值实验，从小到大扫 n，看结论从哪个 n 开始稳定成立，把这个 n 乘 10 当作安全门槛用。

5.5 坑五：二阶矩里把相关事件当独立算方差

现象是方差算出来比期望的平方小两个数量级，结论漂亮得不像话，但构造反例一搜就有。

原因是只算了 Σ Var[X_i]，漏了所有协方差项。当坏结构之间频繁共享元素时，协方差项是正的且数量级和方差项相当，漏掉它会把方差低估一个量级，进而把 P(X=0) 的界压得虚低。

解决办法是把相关结构分类展开。按「共享 0 个、1 个、2 个元素」把所有事件对分组，前一组近似独立可以不算，后两组逐项算 Cov 并求和。如果分组太细算不动，用联合事件不等式兜底：它给出的界比精确方差松，但不会因为你漏项而给出错误结论。判断要不要展开的标准是：先只算对角项，如果结论已经足够强（比如 P(X=0) < 0.01），对角项就够了；如果算出来是 0.3 这种尴尬值，说明对角项不够，必须展开。

6. 把书上的存在性证明落成脚本：三步验证与阅读顺序表

书读完之后真正留在手上的，不是定理陈述，而是一套「拿到一个新问题怎么下手」的流程。我自己固定走三步：第一步把目标性质写成坏事件集合，明确每个坏事件涉及的随机变量；第二步用最粗的工具（并集界或期望法）先算一遍，看条件离满足差多远；第三步按差距大小选精化方向——差一个数量级以内上二阶矩或局部引理，差好几个数量级说明概率空间选错了，要换随机模型重来。这三步里第二步最容易跳过，很多人一上来就用局部引理，结果参数算到一半发现并集界其实就够了，白折腾。

阅读顺序上，如果目标是把工具用起来，方法篇的第 1、2、3、4、5、7 章按顺序读，第 6 章（相关性不等式）和第 8 章（泊松范式）可以按需插入；如果目标是做随机图或者算法分析，第 9 章之后按主题挑，第 11 章的相变、第 16 章的去随机化、第 17 章的图性质测试是第三版新增的三块，和工程距离最近。每章末尾的习题里带星号的难度明显更高，时间紧就先跳过，不影响主线。附录里的大偏差界那张表建议单独复印一份放手边，参数估计时经常要回头查。

最后说个血泪教训：我早期读这类书习惯只看定理陈述和结论，证明跳过，觉得「知道有这么个工具就行」。结果真到用的时候，参数怎么定、边界在哪、什么时候失效，一条都答不上来，只能从头再读一遍。现在我每次读到一个准备用的定理，都会强制自己把证明里的每一处放缩反解成一个显式不等式，写进一个单独的笔记文件，用的时候直接查门槛。这个习惯救过我好几次——有一次算出来的 n 门槛比我原计划的数据规模大两个数量级，提前发现，省了一周的返工。希望帮到你。

本文还有配套的精品资源，点击获取