简介《The Probabilistic Method》第三版 PDF 是一部面向数学、理论计算机科学与组合优化方向研究生及研究人员的经典教材聚焦以概率论工具证明离散对象的存在性与性质。内容围绕随机化证明、组合恒等式、大数定律与中心极限定理、图论中的 Ramsey 数与边色数、编码理论、算法分析、零一律及 Lovász 局部引理等主题展开强调概率模型在难以直接构造或逐一枚举的问题中的方法价值。资源包内仅含 1 个 PDF 文件大小约 7.77MB便于在电脑或平板上检索、批注与系统阅读。当前已有 150 人学习说明其在相关课程与研究入门中具有一定参考需求。书中以清晰阐述和丰富例子连接概率论基础、图论与线性代数预备知识适合读者理解随机化证明的思路、掌握局部引理等核心工具并用于组合数学、复杂性理论与算法课程延伸阅读。1. 概率方法为什么“算出一个正概率”就等于“证明了存在”要证明一个组合对象存在最反直觉的做法是根本不构造它。概率方法把“存在性”翻译成“随机采样命中的概率大于零”——你只要定义一个合适的概率空间证明随机取到的对象以正概率满足条件存在性就成立了。这套思路解决的是极值组合里最难的一类问题想证明“某个结构一定有某种性质”直接构造往往无从下手但随机对象的平均行为是可以算的。这个机制值得搞懂因为它是后面所有大偏差、局部引理、相变分析的共同地基也是把“大概能行”变成“一定存在”的唯一合法通道。2. 期望的线性性为什么“变量不独立”也照样能加2.1 从拉姆齐下界看“把计数翻译成概率”拉姆齐数 R(k,k) 是这样一个最小的 n把完全图 K_n 的每条边任意染成红色或蓝色都必然出现一个单色的 K_k。上界很难证下界反而有一个极其干净的概率证明。对 K_n 的边独立地、等概率地染红或蓝。固定任意一个 k 元顶点集它内部共有 C(k,2) 条边全部同色的概率是 2·2^{-C(k,2)} 2^{1-C(k,2)}。设随机变量 X 为单色 K_k 的个数写成指示变量之和X Σ_T I_T其中 T 跑遍所有 k 元子集。于是 E[X] C(n,k)·2^{1-C(k,2)}。关键一步来了如果这个期望严格小于 1那么必然存在某一种染色方案使 X 0——因为 X 只能取非负整数若所有方案都满足 X ≥ 1期望就至少是 1。X 0 的染色方案就是“没有单色 K_k”的方案于是 R(k,k) n。代入 n ⌊2^{k/2}⌋用 C(n,k) ≤ n^k/k! 放缩得到 E[X] ≤ 2^{1k/2}/k!当 k ≥ 3 时这个值小于 1。所以 R(k,k) 2^{k/2}这是一个指数级的下界。2.2 线性性真正吃的是什么上面那步求和看起来平平无奇但它成立的前提只有一个期望对加法线性。E[XY] E[X] E[Y] 对任意两个随机变量都成立不需要它们独立也不需要它们同分布。而 E[XY] E[X]E[Y] 才需要独立——这是两件完全不同的事很多人栽在这里。那些指示变量 I_T 之间高度相关两个 k 元集只要共享顶点它们“是单色团”的事件就纠缠在一起。但这种相关性对求和毫无影响。指示变量方法的通用配方也就三步第一步把“坏事件存在”写成 X Σ I_AX 是坏事件的计数。第二步用线性性算出 E[X]完全绕过相关性。第三步若 E[X] 1则存在 X 0 的样本点。这个配方的威力在于它把“证明存在一个没有坏事件的对象”降级成“算一个平均数”。判断一条边能否被割随机把顶点分成两半每条边跨割的概率是 1/2于是期望割大小是 m/2立刻得到任何图都存在大小至少 m/2 的割。整个论证没有一条边是独立的但这不重要。2.3 修正式先弄脏再擦干净一阶矩只能给“坏事件数为零”的结论。当期望值大于 1 时这个方法当场失效——而现实中大部分问题的自然构造都带一堆坏事件。修正式alteration换了个思路先随机生成一个粗糙的解然后局部删掉坏的部分控制损失量。经典例子是独立集下界。给定 n 个顶点、m 条边的图 G每个顶点以概率 p 独立地被选进集合 S。S 期望有 pn 个顶点S 内部期望有 p²m 条边。对 S 内部的每条边删掉其中一个端点剩下的点构成独立集大小至少是 pn 减去删除数而删除数不超过坏边数。于是存在一个独立集大小至少 pn − p²m。对 p 求极值取 p n/(2m)下界约为 n²/(4m)。整个过程没有任何“构造算法”的野心但结论是硬的。import random def sample_then_delete(n, edges, p): 修正式演示随机采点再删掉坏边的端点得到一个独立集。 n : 顶点数 edges : (u, v) 边列表 p : 每个顶点被采样的独立概率 返回 : (采样得到的点数, 删除后独立集大小) keep {v for v in range(n) if random.random() p} # 第一层随机采样 removed set() for u, v in edges: if u in keep and v in keep: # 第二层只处理保留下来的坏边 if u not in removed and v not in removed: removed.add(v) # 固定删后一个端点行为可复现 return len(keep), len(keep) - len(removed)代码里两层结构对应修正式的两个阶段第一层是随机采样第二层是确定性修复。删除逻辑加了u not in removed and v not in removed的守卫避免同一条链上的坏边重复删除同一个点这保证了删除数不超过坏边数也就保证了keep - removed的期望下界推导成立。参数 p 的选择直接决定下界质量。p 太大会让坏边暴涨p² 项p 太小则采到的点本身就不够pn 项。上面推导出的 p n/(2m) 是最优平衡点但在 m 很小的稀疏图上这个值会超过 1此时直接取 p 1 并退化成“删掉每条边一个端点”下界变成 n − m。这提示了一件事修正式给出的是参数化的下界族取哪个参数要按图的稠密程度分情况讨论不能照抄公式。3. 二阶矩与集中为什么“平均有一个”和“几乎到处都是”差着一条鸿沟3.1 一阶矩只回答“有没有”一阶矩给出的是存在性它对“有多少”这个问题极其吝啬。E[X] 100 的时候X 1 和 X 100 都完全可能概率分布的形状完全没有被约束。二阶矩方法补上这一块。设 X 非负由切比雪夫不等式P(X 0) ≤ P(|X − E[X]| ≥ E[X]) ≤ Var(X) / E[X]²。结论很直白只要 Var(X) o(E[X]²)那么 X 0 的概率趋于零也就是“不仅存在而且几乎到处都是”。这个方法在随机图子图计数、数论里的不同子集和问题、随机置换的环结构上反复出现因为它把“存在性”升级成了“密度”。但注意这个判据的强度Var/E² 趋于零是一个相当苛刻的条件等价于说随机变量的相对涨落必须消失。很多自然的问题达不到这个强度那时二阶矩只能给出“存在无穷多个 n”这种弱形式的结论而不是“所有足够大的 n”。3.2 随机图的方差分解相关项到底从哪来以 G(n,p) 里的三角形个数 X 为例X Σ_T I_TT 跑遍所有三元组。方差不能直接从 E[X] 算因为指示变量之间两两相关必须把协方差项一项一项拆开Var(X) Σ_T Var(I_T) Σ_{T≠T} Cov(I_T, I_{T})。两个三角形什么时候协方差不为零只有两种情况。第一种是共享一条边此时两个三角形一共涉及 4 个顶点、5 条边两者同时出现的概率是 p⁵减去 p³·p³ p⁶ 得到 Cov p⁵ − p⁶。第二种是恰好共享一个顶点涉及 5 个顶点、6 条边Cov p⁶ − p⁹。这两类情况互斥覆盖了所有相关的三角形对。数量上共享边的无序对有 C(n,3)·3(n−3)/2 个共享顶点的有 C(n,3)·3·C(n−3,2)/2 个。import math, random def theory(n, p): 二阶矩展开返回 E[X] 与 Var[X] 的解析值近似忽略高阶小项 E math.comb(n, 3) * p**3 # 独立项每个三角形自身的伯努利方差 v1 math.comb(n, 3) * p**3 * (1 - p**3) # 共边项4 个顶点、5 条边的联合概率 p^5 pairs_edge math.comb(n, 3) * 3 * (n - 3) / 2 v2 pairs_edge * (p**5 - p**6) # 共顶点项5 个顶点、6 条边的联合概率 p^6 pairs_vert math.comb(n, 3) * 3 * math.comb(n - 3, 2) / 2 v3 pairs_vert * (p**6 - p**9) return E, v1 v2 v3 def monte_carlo(n, p, trials400): 蒙特卡洛估计逐对判定边是否存在再暴力数三角形 samples [] for _ in range(trials): adj [[False] * n for _ in range(n)] for i in range(n): for j in range(i 1, n): if random.random() p: # 每条边独立以 p 出现 adj[i][j] adj[j][i] True cnt 0 for i in range(n): for j in range(i 1, n): if not adj[i][j]: continue for k in range(j 1, n): if adj[i][k] and adj[j][k]: cnt 1 samples.append(cnt) m sum(samples) / len(samples) v sum((x - m) ** 2 for x in samples) / (len(samples) - 1) return m, vtheory函数里三项的物理含义要分清v1是每个三角形自己贡献的方差量级 n³p³v2是共边对量级 n⁴p⁵v3是共顶点对量级 n⁵p⁶。除以 E² ≈ n⁶p⁶/36 之后三项分别变成约 6/(n³p³)、9/(n²p)、9/(2n)。这个比例关系本身就是结论。第三项永远趋于零意味着共顶点的那种相关性随 n 增大自动消失不用管。第一项要求 n³p³ → ∞也就是 E[X] 本身趋于无穷——三角形太少的时候方差方法必然失效这不是技巧问题。第二项要求 n²p → ∞。当 p 落到 c/n 这个量级时三项里第一项变成常数 6/c³Var/E² 不趋于零X 事实上服从泊松分布此时该用第 8 章的泊松范式而不是硬套二阶矩。monte_carlo的 trials 参数只影响估计精度不影响理论值。用 n40、p0.3 跑一遍理论 E[X] 约 267样本方差会有几个百分点的波动这属于正常现象别急着怀疑公式。3.3 当变量强相关鞅和集中不等式接手二阶矩只用到二阶信息遇到强相关的场景就不够用了。典型例子是随机图的着色数改变一条边的状态会连锁影响整个图的可着色性指示变量根本拆不开。这时换一套工具。核心想法是把目标量 f 看成关于一组独立随机变量 X_1,…,X_n 的函数然后控制“改一个变量f 最多变多少”。如果有界差分常数是 c_1,…,c_n那么P(|f − E[f]| ≥ t) ≤ 2·exp(−t² / (2Σc_i²))。这个机制值得琢磨它用的不是方差而是每个变量的“影响幅度”。只要任何一个变量单独翻不了天f 就会紧紧贴住它的期望。随机图的着色数、最长递增子序列长度、旅行商路径长度都满足这个条件因为改动一条边或一个位置只影响局部。再往下还有更强的版本处理 f 对变量集合的依赖呈“凸距离”形态的情况比如最大独立集在随机图里以及能用顶点数和最大度数的多项式来界定的情形。这两个工具的共同前提是随机变量独立依赖结构可以用“影响范围”量化。一旦你要处理的是带约束的组合问题每个变量只能在颜色列表里选就得换第 4 章的局部引理。4. 局部引理为什么“每个坏事件概率小”远远不够4.1 依赖图把相关性压缩成一张稀疏图假设有 n 个坏事件 A_1,…,A_n想证明“所有坏事件同时不发生”的概率大于零。最朴素的做法是联合界只要 Σ P(A_i) 1 就行。这个条件非常苛刻n 一大就直接失效。局部引理说的是不需要所有事件两两独立只需要每个事件只与“少数几个”其他事件相关。形式化地建一张依赖图顶点是事件如果 A_i 与 A_j 不独立就连一条边。设依赖图最大度为 d且每个 P(A_i) ≤ p那么只要e·p·(d1) ≤ 1就有 P(∩ A_i^c) 0。这里的 e 是自然对数的底不是随手写的常数它来自下面那个证明里的收缩因子。和联合界对比一下就明白差距联合界要求 np 1局部引理允许 p ≈ 1/(ed)相当于把允许的单事件概率放大了 n/d 倍。在依赖图稀疏d 远小于 n的场景里这是数量级的改善。图着色的例子最能说明问题。给 n 个顶点的图做 q 着色每个顶点随机取一种颜色。坏事件是“某条边两端同色”概率 p 1/q。一条边 e 的坏事件依赖于所有与 e 共享顶点的边——如果图的最大度是 Δ这样的边最多 2(Δ−1) 条。代入条件q ≥ e(2Δ−1) 就足以保证存在合法着色。这个下界比贪心算法给出的 Δ1 差一个 log 因子左右但它对任何图都成立而且证明只有五行。4.2 链式条件概率的收缩e 这个常数是怎么冒出来的局部引理的证明是整章最精妙的地方值得完整走一遍。目标是证明 P(∩_i A_i^c) 0。把它拆成条件概率的乘积P(∩_i A_i^c) ∏_i P(A_i^c | A_1^c ∩ … ∩ A_{i−1}^c)。只要能证明每个条件概率都严格大于零乘积就大于零。所以真正的任务是对任意事件 A_i本文还有配套的精品资源点击获取