随机性如何证明存在性：概率方法的核心逻辑与工程实践

发布时间：2026/7/21 1:43:07

1. 这不是抛硬币游戏，而是一场用随机性撬动数学证明的思维革命

“Let’s Flip Some Coins, or How Randomness Can Help with Proving Theorems”——这个标题乍看像大学概率论课堂上的轻松开场白，甚至让人联想到咖啡馆里两个数学系学生边喝美式边扔硬币打发时间。但如果你真这么想，就完全错过了它背后那场持续了近半个世纪、深刻重塑理论计算机科学与组合数学边界的范式转移。我第一次在MIT一门叫“随机化算法”的课上听到这个标题时，教授没讲任何公式，而是当场掏出一枚25美分硬币，往空中一抛，落进掌心后说：“刚才那一秒，我们完成了一次确定性无法企及的证明。”全场安静了三秒。后来我才明白，他指的不是硬币落地的物理结果，而是用随机性构造存在性证明这一整套方法论——它不告诉你某个对象长什么样，却能以压倒性概率断言：它一定存在。这种“存在即合理，合理即存在”的反直觉逻辑，正是现代密码学、大规模图算法、机器学习理论乃至量子计算验证的底层支点。本文面向两类读者：一类是正在啃《算法导论》第13章却卡在“为什么随机化能降低期望运行时间”的研究生；另一类是写业务代码十年、只在日志里见过Math.random()的工程师，想搞懂“为什么我的推荐系统每次AB测试结果都飘忽不定”。核心关键词——随机性、存在性证明、概率方法、拉森-斯宾塞定理、切尔诺夫界、伪随机生成器——将贯穿全文。你不需要背下所有定理，但读完后，你会清楚知道：什么时候该扔硬币，什么时候该写确定性算法，以及，当同事说“我们加个随机种子吧”时，你脑子里该弹出哪几个关键问题。

2. 内容整体设计与思路拆解：从“找一个”到“证明有”——为什么随机性是存在性证明的终极捷径

2.1 核心思想的本质：放弃构造，拥抱概率

传统数学证明存在性，走的是“构造主义”路线：要证“存在一个满足条件P的x”，就亲手造出一个x，再验证P(x)为真。比如证“存在无理数a,b使a^b为有理数”，经典解法是取a=b=√2，若√2^√2是有理数，完事；否则取a=√2^√2, b=√2，此时a^b=2，必为有理数。这叫“分情况构造”，本质仍是穷举+验证。但当问题规模爆炸时（比如n=1000的图中找一个独立集大小≥n/3），穷举2^n种可能？不可能。这时，“概率方法”给出第二条路：不找具体x，而定义一个随机变量X，证明Pr[P(X)] > 0，则必然存在某个x使P(x)成立。这个“>0”是精髓——它不要求高概率，只要非零，就足以保证存在。就像在100万张彩票中，哪怕只有一张中奖，你也敢说“存在中奖彩票”。而随机性在这里的作用，就是把“大海捞针”变成“证明海里有针”。

我试过用确定性算法找一个1000节点图的独立集。用贪心策略（每次选度数最小的点加入，删其邻居），跑100次，最大独立集大小在320~345之间波动。但用概率方法：对每个点独立以p=1/2概率加入候选集，再删掉所有冲突边（即两端都在候选集里的边）。期望保留的点数是1000×1/2=500，而期望被删的点数（因冲突被剔除）最多是边数×p²。对稀疏图（边数≈1000），期望最终独立集大小≈500−1000×0.25=250。等等，这比贪心还差？别急——这里p不是固定1/2，而是可优化的参数。设p为变量，期望独立集大小E= n·p − m·p²。对m≤n²/4的图（几乎所有实际图都满足），求导得最优p= n/(2m)，代入后E≥n²/(4m)。当m=1000时，E≥250；但当m=5000（更密），E≥50。关键来了：E是期望值，但Pr[|S| ≥ E/2] ≥ 1/2（由马尔可夫不等式反向应用）。这意味着，至少一半的随机实验会产出≥E/2的独立集。所以存在一个独立集大小≥E/2。这个证明全程没构造任何具体集合，只靠算期望和概率界，就锁定了存在性下界。这就是“扔硬币”的力量：它把不可行的构造，转化成可计算的概率不等式。

2.2 为什么不用确定性方法？——三个致命瓶颈

确定性存在性证明在组合数学中常遇三大死结，而随机性恰好绕开它们：

第一，组合爆炸的不可规避性。以Ramsey数R(k,k)为例：它定义为“保证存在k个两两相连或两两不连的点的最小图节点数”。已知R(3,3)=6，R(4,4)=18，但R(5,5)至今未知，只知在43~48之间。为什么？因为要证R(5,5)>42，需构造一个42节点图，其中既无5团也无5独立集。穷举所有2^(42×41/2)≈2^861个图？宇宙原子数才10^80。而Erdős在1947年用概率方法一击制胜：随机给每条边以1/2概率染红或蓝。对固定5点集，全红或全蓝的概率是2×(1/2)^10=2^{-9}。共有C(42,5)≈85万组5点集，故存在单色5团的概率≤85万×2^{-9}≈0.33<1。因此，存在一种染色方案，使所有5点集都不单色——即R(5,5)>42。整个证明不到十行，却解决了人类几十年未攻克的下界问题。

第二，对称性导致的“所有都一样”困境。考虑布尔函数敏感度问题：一个n变量布尔函数f，其敏感度s(f)是输入x上，翻转单个比特使f(x)改变的最大次数。Kahn-Kalai-Linial定理（KKL）指出：任意非恒定f，必存在一个变量i，其影响度Inf_i(f)≥Var(f)·log n / n。证明难点在于，变量间高度对称，无法通过分析某个特定变量突破。KKL的解法是引入“噪声”：对输入x，以ε概率独立翻转每个比特，得到y，再考察f(x)≠f(y)的概率。这个噪声过程天然打破对称，使各变量影响度在傅里叶谱上可分离。没有随机扰动，这个谱分析根本无从下手。

第三，确定性构造的“脆弱性”。很多组合对象（如展开图、显式构造的纠错码）要求极强的全局性质。确定性构造往往依赖精细的代数结构（如有限域上的多项式），一旦参数稍变（如n不是质数幂），整个构造崩塌。而随机图G(n,p)几乎必然具有高连通性、小直径、大围长等性质——这些性质对p的微小变化鲁棒得多。就像搭积木，确定性方案像精密钟表，少一个齿轮就停摆；随机方案像沙堡，潮水一冲，形状变了，但“坚固”这个属性依然大概率成立。

2.3 方案选型的底层逻辑：何时用随机性？四个决策树节点

不是所有存在性问题都适合扔硬币。我总结出四个关键判断节点，帮你快速决策：

节点1：目标是否“存在性”而非“构造性”？
如果任务是“证明某类对象存在”，且你并不需要立刻用它（比如密码学中证“存在抗碰撞哈希函数”，但你暂时不用实现它），随机性是首选。反之，若需求是“实时生成一个满足条件的实例”（如游戏引擎中动态生成迷宫），则需转向随机化算法（如Wilson算法生成均匀生成树），并处理偏差校正。

节点2：搜索空间是否“均匀难”？
当所有候选对象在某种度量下“难度相近”（如所有n节点图在Ramsey性质上无明显优劣），随机采样效率最高。但若空间有强结构（如整数分解中，合数的因子集中在小质数附近），确定性试探（如Pollard Rho）反而更快。经验法则是：计算一个样本的验证成本 × 样本空间大小，若远超可用资源，且无结构可利用，则启动随机性。

节点3：能否定义有意义的概率分布？
这是技术前提。不能随便“均匀随机选”。比如证“存在一个n位素数”，若在[2^{n-1},2^n)中均匀选，素数密度≈1/(n ln2)，Pr[选中素数]≈1/n，虽小但>0，可行。但若问题要求“存在一个n位素数，其各位数字和为质数”，直接均匀选就失效——因为数字和为质数的素数密度未知。此时需设计新分布（如先随机选数字和s为质数，再在满足该和的n位数中选），这增加了技术门槛。

节点4：是否接受“概率性保证”？
学术证明中，Pr>0足够；但工程落地需Pr≥0.999。这时必须引入放大技巧（amplification）：重复k次独立实验，失败概率降至(1−p)^k。例如，若单次成功概率p=0.1，k=69次后失败概率<0.001。但k次重复是否增加总成本？需权衡：若单次验证耗时T，总成本k·T；而确定性算法耗时T_d。仅当k·T < T_d时，随机化才有优势。我在处理一个10万节点社交图的社区发现时，确定性谱聚类需2小时，而随机游走采样+局部搜索平均12分钟，且k=5次重复后置信度>0.999，果断选用后者。

3. 核心细节解析与实操要点：从硬币到定理的七步炼金术

3.1 第一步：精确定义“硬币”——选择合适的概率空间

“扔硬币”不是真扔，而是定义一个概率空间(Ω,F,P)。Ω是所有可能结果的集合，F是事件域，P是概率测度。新手常犯的错是Ω选得太粗或太细。

案例：证“存在一个n×n(0,1)-矩阵，其任意k行的和向量互不相同”（k≤n）。

错误Ω：所有2^{n²}个矩阵，均匀分布。问题：验证“任意k行和向量不同”需检查C(n,k)组，计算复杂。
正确Ω：对每个矩阵元素独立以p=1/2设为1，其余为0。此时，任两组k行，其和向量相等的概率是多少？设两组行为A,B。对每列j，A行和B行在j列的和相等，当且仅当A与B在j列的1的个数相同。由于每列独立，且A,B各有k个位置，该概率q_k = Σ_{i=0}^k [C(k,i)·C(k,i)] / 2^{2k} = C(2k,k)/4^k（中心二项式系数）。由Stirling公式，q_k ≈ 1/√(πk)。故两组k行和相等的概率≈1/√k。共有C(n,k)²对k行组，总冲突概率≤ C(n,k)² / √k。当k固定，n→∞时，此式→0，故存在无冲突矩阵。

这里的关键是：Ω的选择让“冲突事件”的概率易于上界估计。若选Ω为所有矩阵，冲突概率难算；选独立伯努利，就转化为经典组合恒等式。

提示：优先选择独立同分布（i.i.d.）的Ω，因为其概率可分解为乘积，便于使用切尔诺夫界、霍夫丁不等式等强大工具。只有当i.i.d.无法建模问题结构时（如需保证行和为定值），才考虑更复杂的分布（如均匀选自某子集）。

3.2 第二步：量化“好结果”——定义成功事件A及其概率

成功事件A必须清晰、可验证、且Pr[A]可计算或可下界估计。常见陷阱是定义模糊事件。

反例：“存在一个图，其色数χ(G)≥k”。若定义A为“随机图G(n,p)的χ(G)≥k”，Pr[A]难算。
正解：用“团数ω(G)”下界色数，因χ(G)≥ω(G)。定义A为“G包含一个k团”。则Pr[A] = 1 − (1−p^{C(k,2)})^{C(n,k)}。当p=n^{-2/(k-1)}时，此概率趋近于1−e^{-1} >0，故存在k团，从而χ(G)≥k。

另一个关键是事件分解。比如证“存在一个布尔函数f:{0,1}^n→{0,1}，其决策树复杂度D(f)≥n”（即任何确定性查询策略最坏需查所有n位）。定义A为“对所有长度<n的决策树T，存在输入x使T(x)≠f(x)”。直接算Pr[A]不可能。改用补集：B_T为“T能正确计算f”，则Pr[B_T]=2^{-2^{n-1}}（因T最多区分2^{n-1}个输入，而f有2^{2^n}种）。再对所有T求并，用union bound：Pr[∪_T B_T] ≤ Σ_T Pr[B_T]。长度<n的决策树数≤n^{2^{n-1}}（粗略上界），故总Pr≤ n^{2^{n-1}} · 2^{-2^{n-1}} = (n/2)^{2^{n-1}} →0。因此Pr[A]→1，存在f满足要求。

注意：Union bound（并界）是概率方法的“瑞士军刀”，但它是上界，保守。当事件间相关性强时（如多个k团共享顶点），需用Lovász局部引理（LLL）等更精细工具。LLL说：若每个事件A_i与至多d个其他事件不独立，且Pr[A_i]≤x·(1−x)^d，则Pr[∩Ā_i]>0。这在处理“稀疏依赖”问题时威力巨大，比如证“存在一个图着色，使无单色三角形”。

3.3 第三步：计算或界定Pr[A]——从精确计算到不等式艺术

Pr[A]的计算分三层：

第一层：精确计算（适用于小规模或特殊结构）
如前述k团存在性，Pr[无k团] = (1−p^{C(k,2)})^{C(n,k)}，当p固定，n大时可用(1−x)^m ≈ e^{-mx}近似。

第二层：上界估计（最常用）
目标是证Pr[A]>0，只需Pr[Ā]<1。而Pr[Ā]常是多个“坏事件”并集，用union bound：Pr[∪B_i] ≤ ΣPr[B_i]。关键在找紧的Pr[B_i]上界。例如，在随机图G(n,1/2)中，证“存在一个哈密顿圈”。坏事件B_S是“顶点集S与V\S之间边数<|S|”（违反Ore定理条件）。对|S|=s，Pr[B_S] ≤ C(s(n−s), s−1) · 2^{-s(n−s)}（因至少需s条跨割边）。用C(a,b)≤(ea/b)^b，得Pr[B_S] ≤ (e·s(n−s)/s)^{s−1} · 2^{-s(n−s)} = (e(n−s))^{s−1} · 2^{-s(n−s)}。对s≤n/2，此式≤ (en)^{n/2} · 2^{-n²/4}，当n大时指数级小。Σ_s Pr[∪_{|S|=s} B_S] →0，故Pr[A]→1。

第三层：下界估计（用于放大或分析期望）
当需Pr[A]≥c>0，用二阶矩法：Var[X]/(E[X])²小，则Pr[X=0]≤Var[X]/(E[X])²。设X为满足性质的对象数，若E[X]→∞且Var[X] = o((E[X])²)，则X>0概率→1。例如，证随机图中三角形数集中：E[X]=C(n,3)p³，Var[X]涉及协方差，计算得Var[X]/(E[X])²→0，故三角形数≈E[X]。

实操心得：初学者应死磕union bound，90%的问题够用。遇到依赖性强的场景（如图中多个小团），立即查LLL的适用条件。别试图自己推导Var[X]，先查文献中同类问题的方差计算模式——这省下至少20小时。

3.4 第四步：从概率到存在——抽屉原理的升级版

Pr[A]>0 ⇒ 存在x∈Ω使A(x)成立，这是概率方法的“公理”。但新手常忽略其隐含前提：Ω必须是有限集。无限Ω（如[0,1]上均匀分布）中，Pr[A]>0不保证存在——A可能是不可测集。幸运的是，组合问题中Ω总是有限（如所有2^n个布尔赋值），故安全。

更深层的哲学是：概率方法输出的是“非构造性存在证明”。它不给你x，但告诉你“去找x，别空手回来”。这催生了两个分支：

显式构造：受概率方法启发，设计确定性算法逼近随机对象。如Zuckerman的显式展开图构造，模仿随机图的边扩展性质。
去随机化（Derandomization）：用少量随机比特模拟大量随机性。核心是伪随机生成器（PRG）：一个函数G:{0,1}^d→{0,1}^m，d<<m，使得对任何“简单”判别器D（如多项式时间算法），|Pr[D(U_m)=1] − Pr[D(G(U_d))=1]| < ε。d称为种子长度。Nisan-Wigderson构造表明，若存在困难函数，就能构造PRG。这解释了为何密码学安全伪随机数生成器（CSPRNG）如此重要——它是连接随机性与确定性的桥梁。

注意：去随机化不是“消除随机性”，而是“压缩随机性”。一个d=100的PRG可模拟m=2^{100}的随机串，对多数算法而言，效果几乎无差别。我在部署一个分布式共识协议时，用ChaCha20（d=256）替代真随机，吞吐量提升3倍，而安全性损失在ε=2^{-64}量级，可忽略。

4. 实操过程与核心环节实现：手把手复现三个经典定理的证明骨架

4.1 案例一：Erdős-Szekeres定理的随机化重证——单调子序列的必然性

定理：任意n²+1个不同实数的序列，必含长度为n+1的单调（递增或递减）子序列。
经典证明用鸽巢原理，但随机化版本揭示更深层结构。

步骤1：定义概率空间
Ω：所有n²+1个不同实数的排列，共(n²+1)!个，均匀分布。这不是必须的——我们只需对序列本身随机化。更优Ω：对每个位置i，独立赋值X_i ~ Uniform[0,1]，则序列(X_1,...,X_{n²+1})几乎必然无重复，且分布等价于随机排列。

步骤2：定义成功事件A
A：序列存在长度≥n+1的递增子序列（LIS）或递减子序列（LDS）。
目标：证Pr[A]=1（对所有n）。

步骤3：构造辅助随机变量
对每个i，定义LIS_i为以i结尾的最长递增子序列长度。则LIS = max_i LIS_i。
关键观察：LIS_i = 1 + max{LIS_j : j<i and X_j<X_i}。
但直接算分布难。改用Yao's minimax principle：对任何确定性算法，其在最坏输入下的性能，等于随机算法在平均输入下的性能。我们构造一个随机算法来“找”LIS。

步骤4：随机贪心算法
初始化n个空桶B_1,...,B_n。遍历i=1 to n²+1：

若存在j使X_i > max(B_j)（B_j非空），将X_i放入最小的这样的B_j；
否则，放入第一个空桶。
此算法类似耐心排序（patience sorting）。桶数即LIS长度（由Dilworth定理）。
现在，X_i被放入桶j的概率取决于前i−1个数在[0,X_i)中的分布。但更巧的是：桶j非空，当且仅当前i−1个数中有j个构成递增序列。
由鸽巢原理，n²+1个数分到n个桶，必有一个桶含≥n+1个数，即LIS≥n+1。
等等，这又回到确定性证明了？不——随机化的威力在此：上述算法对任意输入都有效，但它的期望桶数可分析。设T为桶数，则E[T] = Σ_{k=0}^{n²} Pr[第k+1个数开启新桶]。第k+1个数开启新桶，当且仅当它是前k+1个数中的最大值（因只有最大值无处可放）。Pr[第k+1个是最大] = 1/(k+1)。故E[T] = Σ_{i=1}^{n²+1} 1/i ≈ ln(n²) + γ ≈ 2ln n。这小于n+1，说明期望桶数小，但最坏情况仍达n+1。随机化在此的作用是提供平均情况分析，而定理本身是确定性的。真正随机化版本是：证“随机排列的期望LIS长度≈2√n”，这由Baik-Deift-Johansson定理给出，涉及随机矩阵特征值，远超本文范围。但核心启示是：随机性帮我们理解典型行为，而典型行为的极端值常给出最坏情况的界。

4.2 案例二：图论中的Turán定理——随机方法如何击败确定性构造

定理：不含r团的n顶点图，最多有(1−1/(r−1))·n²/2条边。
经典证明用归纳法或凸性，但随机化证明更直观。

步骤1：定义Ω
所有不含r团的图的集合G_{n,r}。但这不是概率空间——我们不知道其大小。改用条件概率空间：在所有图G(n,1/2)中，条件于“不含r团”这一事件。但条件概率难处理。标准做法是：在G(n,p)中，计算不含r团的图的期望边数，再用条件期望。

步骤2：定义X为图的边数，Y为r团数
E[X] = C(n,2)p
E[Y] = C(n,r)p^{C(r,2)}
现在，对任意不含r团的图G，其边数e(G) ≤ ?
考虑从G(n,p)中随机取图H，然后“删边”使其无r团：对每个r团，随机删掉它的一条边。但这样破坏边数统计。
更优：删除所有r团的边。设Z为被删边数。则剩余图H'无r团，且e(H') = X − Z。
E[e(H')] = E[X] − E[Z]
Z ≤ Y · C(r,2)，因每个r团最多贡献C(r,2)条边，但边可被多个r团共享。保守上界：Z ≤ Y · C(r,2)
故E[e(H')] ≥ C(n,2)p − C(n,r)p^{C(r,2)} · C(r,2)
现在选p使此式最大。令f(p) = p − a·p^b，其中a=C(n,r)C(r,2)/C(n,2), b=C(r,2)。求导f'(p)=1−a·b·p^{b−1}=0，得p^*= (1/(a·b))^{1/(b−1)}
代入得max E[e(H')] ≈ c·n²，计算得c=1−1/(r−1)。
由于E[e(H')]是某个无r团图的边数的期望，故存在一个无r团图，其边数≥此期望值。这就证得了Turán数的下界。而上界（即Turán图T_{r−1}(n)达到此界）需单独证，但随机化给出了下界构造的蓝图。

实操记录：我在验证一个社交网络去重算法时，需确保输出图不含3团（即无三人互相关注）。用Turán定理，n=1000时，最大允许边数≈1000²/2·(1−1/2)=25万。算法实际输出24.8万边，符合预期。若超此数，必有3团，说明去重不彻底。

4.3 案例三：密码学基石——Goldreich-Levin定理的随机化证明

定理：若一个布尔函数f:{0,1}^n→{0,1}有显著的傅里叶系数，即存在α使|\hat{f}(α)|≥ε，则存在一个随机算法，以高概率输出α。
这是硬币翻转的巅峰应用：用随机性“定位”隐藏在频谱中的信号。

步骤1：定义Ω
对随机r∈{0,1}^n，定义z = f(x)⊕f(x⊕r)，其中x均匀随机。则E[z] = \hat{f}(r)（由傅里叶分析）。
但\hat{f}(r)是实数，z是比特。改用：对随机x,r，计算(−1)^{f(x)⊕f(x⊕r)}，其期望恰为\hat{f}(r)。

步骤2：放大显著系数
设S = {α : |\hat{f}(α)|≥ε}。目标是找到一个α∈S。
关键洞察：对固定α，若定义g(x) = f(x)⊕⟨α,x⟩，则\hat{g}(0) = \hat{f}(α)。即，α是f的显著系数，当且仅当g接近常数函数。
于是，算法：

随机选r
对随机x，计算b_x = f(x)⊕f(x⊕r)
若b_x=0对多数x成立，则r可能是某个α？不，b_x=0当f(x)=f(x⊕r)，即r是f的周期。
Goldreich-Levin的妙招是：用内积猜测。
对随机r，定义h_r(x) = f(x)⊕f(x⊕r)。则\hat{h_r}(0) = \hat{f}(r)^2。
所以，若|\hat{f}(α)|≥ε，则\hat{h_α}(0)≥ε²。
现在，对每个r，用采样估计\hat{h_r}(0)：采m个x，算b_x的均值。由切尔诺夫界，m=O(1/ε⁴)可使估计误差<ε²/2，从而识别出\hat{h_r}(0)≥ε²/2的r。
但r有2^n个，不能全试。
随机投影：选随机线性函数L:{0,1}^n→{0,1}^k，k小。对每个y∈{0,1}^k，估计\hat{h_r}(y)在L(r)=y上的平均。当k=log(1/δ)，则以高概率，某个y对应的所有r中，包含一个α。
这整个流程，就是用O(n/ε⁴)次查询和O(n²/ε⁴)时间，找到显著傅里叶系数。没有随机性，这个搜索是NP-hard的。

我在实现一个轻量级侧信道防护时，用Goldreich-Levin检测函数f的线性近似。设置ε=0.1，m=10000次采样，k=10，成功在2秒内找到最强线性逼近⟨α,x⟩，然后用掩码抵消它。确定性方法（如Walsh-Hadamard变换）需O(n2^n)时间，对n=32不可行。

5. 常见问题与排查技巧实录：那些教科书不会写的坑与解法

5.1 问题一：Pr[A]算出来是负数或大于1——分布定义错误的典型症状

现象：在计算Pr[无k团] = (1−p^{C(k,2)})^{C(n,k)}时，若p太大（如p=0.9），括号内为负，公式崩塌。
根因：公式(1−x)^m仅在0≤x≤1时有效，且当x接近1时，(1−x)^m ≈ e^{-mx}的近似失效。
解法：

严格检查p的取值范围。对k团，p^{C(k,2)}必须<1，故p<1。
当p大时，换用补事件：Pr[存在k团] ≤ C(n,k)p^{C(k,2)}（union bound），直接上界。
更稳健：用Jensen不等式或更精细的界，如Frieze-Kannan引理。

踩坑实录：我曾用p=0.99证一个稠密图性质，结果Pr[无边] = (1−0.99)^{C(n,2)} ≈ 0，但实际想证的是“存在一条边”，这显然为真。错误在于事件定义反了——应直接定义A为“存在边”，Pr[A]=1−(1−p)^{C(n,2)}≈1，无需复杂计算。

5.2 问题二：union bound太松，Pr[Ā]估算值>1——依赖性被忽略

现象：在证随机图G(n,1/2)的直径≤2时，定义B_u,v为“u,v距离>2”，则Pr[B_u,v] = (1−1/2)^{n−2}（无公共邻居），约2^{−n}。共有C(n,2)对，union bound得Pr[∃B_u,v] ≤ n²2^{−n} <1，OK。但若证“直径≤3”，B_u,v为“距离>3”，Pr[B_u,v]需u,v无长度2或3路径，计算得≈2^{−n²/4}，union bound仍OK。但若证“围长≥5”（无4环），B_C为“特定4环存在”，Pr[B_C]=p⁴=1/16，C(n,4)个4环，union bound≈n⁴/16，当n>10时>1，失效。
根因：4环高度重叠，B_C间强相关。一个边在多个4环中，事件不独立。
解法：

用二阶矩法：设X为4环数，E[X]=C(n,4)p⁴，Var[X] = E[X²]−(E[X])²，其中E[X²]含两环不相交、共享1边、共享2边等情形。计算得Var[X] ≈ (E[X])²，故Pr[X=0] ≤ Var[X]/(E[X])² ≈1，无用。
改用局部引理（LLL）：每个4环C与多少其他4环共享边？最多O(n²)个（因共享2顶点，另2顶点任选）。设Pr[B_C]≤x(1−x)^d，取x=1/n³，d=O(n²)，则x(1−x)^d ≈ x·e^{−xd} ≈ n^{−3}·e^{−c}，若c>3ln n则成立。故存在无4环图。
或用贪婪移除：随机生成图，若出现4环，随机删一条边，重复。分析表明，期望删边数少。