企业官网建设流程全解析

简介：《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^{1+k/2}/k!，当 k ≥ 3 时这个值小于 1。所以 R(k,k) > 2^{k/2}，这是一个指数级的下界。

2.2 线性性真正吃的是什么

上面那步求和看起来平平无奇，但它成立的前提只有一个：期望对加法线性。E[X+Y] = E[X] + E[Y] 对任意两个随机变量都成立，不需要它们独立，也不需要它们同分布。而 E[XY] = E[X]E[Y] 才需要独立——这是两件完全不同的事，很多人栽在这里。

那些指示变量 I_T 之间高度相关：两个 k 元集只要共享顶点，它们“是单色团”的事件就纠缠在一起。但这种相关性对求和毫无影响。指示变量方法的通用配方也就三步：

第一步，把“坏事件存在”写成 X = Σ I_A，X 是坏事件的计数。第二步，用线性性算出 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_T，T 跑遍所有三元组。方差不能直接从 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, trials=400): """蒙特卡洛估计：逐对判定边是否存在，再暴力数三角形""" 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, v

theory函数里三项的物理含义要分清：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 参数只影响估计精度，不影响理论值。用 n=40、p=0.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·(d+1) ≤ 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

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