2026-09-25 · 总风险很大却仍能避开

0. 导读与元结构 (Orientation & Meta-structure)

若有数千个坏事件 (bad events)，并集界要求它们的概率总和小于 $1$；但每个事件也许只牵涉附近几个事件。能否改由局部依赖程度保证一项都不发生？今天开启三日探索微弧的第一日：存在性及其证明；随后看二染色与构造性重抽样。

对象是任意概率空间上的有限事件族 $A_1,\dots ,A_n$ 及其依赖图。量词的关键不是“两两不相关”，而是每个 $A_i$ 对其全部非邻居所生成的布尔事件同时独立。前置为条件概率、独立随机变量与图的度；机制是对被排除事件集合归纳，再将条件存活概率相乘。去向是超图染色与算法局部引理。今天的习题另练独立和的方差控制，不把两套独立性论证混同。

1. 核心概念、定理与谱系 (Concept, Theorem & Lineage)

问题 → 定义。 给定概率空间 $(\mathrm{\Omega },\mathcal{F},\mathbb{P})$、整数 $n\ge 1$ 和 $A_i\in \mathcal{F}$。对无向简单图 $G$（顶点集 $[n]$），记 $N(i)$ 为邻居。称 $G$ 为依赖图 (dependency graph)，若对每个 $i$，$A_i$ 与事件族 $\{A_j:j\notin N(i)\cup \{i\}\}$ 生成的 $\sigma$-代数独立；等价地，对这族事件任意指定发生或不发生，其交事件 $B$ 都满足 $\mathbb{P}(A_i\cap B)=\mathbb{P}(A_i)\mathbb{P}(B)$。有限性保证这里的布尔原子判据足够。若各 $A_i$ 分别只依赖一组相互独立基变量，而 $i,j$ 的基变量支撑不相交就不连边，得到一个有效依赖图；图并不由“两两不独立”连线来定义。

引理（条件坏事件界）。 假设有 $x_i\in [0,1)$，且对每个 $i\in [n]$，

$$\mathbb{P}(A_i)\le x_i\prod _{j\in N(i)}(1-x_j).$$

那么对每个 $i\in [n]$、每个 $S\subseteq [n]\setminus \{i\}$，只要条件事件有正概率，便有 $\mathbb{P}(A_i\mid \bigcap _{j\in S}{A}_j^c)\le x_i$。证明按 $|S|$ 归纳。设 $S_1=S\cap N(i)$、$S_2=S\setminus S_1$，写 $C_T=\bigcap _{j\in T}{A}_j^c$。由外部事件族独立，$\mathbb{P}(A_i\cap C_{S_1}\cap C_{S_2})\le \mathbb{P}(A_i\cap C_{S_2})=\mathbb{P}(A_i)\mathbb{P}(C_{S_2})$。另一方面，在 $C_{S_2}$ 条件下依次排除 $S_1$ 中的事件；每一步涉及的被排除集合真小于 $S$，由归纳假设得到 $\mathbb{P}(C_{S_1}\mid C_{S_2})\ge \prod _{j\in S_1}(1-x_j)>0$。分子除以分母，所得上界至多 $\mathbb{P}(A_i)/\prod _{j\in S_1}(1-x_j)\le x_i$。基础步 $S=\varnothing$ 由假设直接得出；逐步获得的正下界也保证所用条件概率确有定义。

定理（非对称 Lovász 局部引理）。 对每个有限的上述事件族及有效依赖图，若存在满足引理条件的 $(x_i{)}_{i=1}^n\in [0,1{)}^n$，则

$$\mathbb{P}\left(\bigcap _{i=1}^n{A}_i^c\right)\ge \prod _{i=1}^n(1-x_i)>0.$$

证明是按 $i=1,\dots ,n$ 链式相乘存活的条件概率，每一因子由引理至少为 $1-x_i$。若 $\mathbb{P}(A_i)\le p$、图最大度不超过 $d\ge 1$，取 $x_i=1/(d+1)$ 得到常用的充分条件 $ep(d+1)\le 1$：因为 $(1-1/(d+1){)}^d\ge e^{-1}$。$d=0$ 时各事件共同独立；若 $ep\le 1$，直接取 $x_i=p<1$ 即可。此推论不要求 $\sum _i\mathbb{P}(A_i)<1$，总事件数可以很大。

应用及研究生延伸。 对有限 $k$-一致超图独立等概率二染各顶点，超边 $e$ 为单色的概率是 $2^{1-k}$；两条不交超边的事件由不交基变量决定。若每条边至多与另外 $d$ 条相交且 $e(d+1)2^{1-k}\le 1$，便存在没有单色超边的二染色。进一步，变量模型中可在坏事件发生时重抽其支撑变量；这引向 Moser–Tardos 的算法局部引理，但今天的链式条件概率证明本身不提供寻找解的运行时间保证。

2. 固定模板习题 (Template Exercise)

题目。 对每个 $n\ge 1$，令 $X_1,\dots ,X_n$ 独立，$0\le X_i\le 1$ 几乎处处，并令 ${\mu }_n=n^{-1}\sum _{i=1}^n\mathbb{E}{X}_i$。证明对每个 $\epsilon >0$、每个 $n\ge 1$， $\mathbb{P}(|n^{-1}\sum _{i=1}^n{X}_i-{\mu }_n|\ge \epsilon )\le 1/(4n{\epsilon }^2)$，从而样本均值减去其各自的期望趋于 $0$（依概率），不要求 ${\mu }_n$ 自身收敛。

模板识别。 独立有界加数的均值偏差：先定位二阶矩和方差的规模，再把均方界转成概率界。

分级提示。 ① 单个 $[0,1]$ 随机变量的方差最多多少？② 独立性怎样消去中心化交叉项？③ 对非负随机变量 $({\bar{X}}_n-{\mu }_n{)}^2$ 使用哪条基本尾界？

3. 大家之言 (Mathematician in Their Own Words)

Timothy Gowers 在其 2026-09-17 第一人称文章 Why I didn’t sign the Fields medallists’ letter 中谈到读论文时如何主动建立理解；此文亦在 Tao 博客作为 Gowers 客座文章刊登，作者不是 Tao。原文短句：“read ‘actively’ rather than ‘passively’”（“主动地读，而不是被动地读”）。Gowers 原文；本次核验的同文客座转载包含该原句。

解读（非原话）： 先试图自己证明、卡住时才取最小提示，是检验定义中量词是否真正被理解的一种方式。今日可先暂停在“为何非邻居须与整个事件族独立”，自己构造一组反例，再看下一节。Gowers 的讨论涉及数学实践与 AI，不是在陈述局部引理的历史。

4. 反例与边界 (Counterexample & Boundary)

令 $(U,V)$ 在 ${\mathbb{F}}_3^2$ 的九个点上均匀分布，设四个坏事件为 $A_1=\{U=0\}$、$A_2=\{V=0\}$、$A_3=\{U-V=0\}$、$A_4=\{U+V=0\}$（等式在 ${\mathbb{F}}_3$ 中）。每个事件各含三个点，概率 $1/3$；任意两条不同的直线恰交于 $(0,0)$，故交概率 $1/9=(1/3{)}^2$：四个事件两两独立。但对任意 $(u,v)$，若 $u=0$ 或 $v=0$ 已落入前两件；若两者均非零，则在 ${\mathbb{F}}_3^{\times }=\{1,-1\}$ 中 $u=v$ 或 $u=-v$，落入后两件。因此 $\mathbb{P}(\bigcap _{i=1}^4{A}_i^c)=0$。有限枚举复核：九点、四个事件各三点、六对交各一点、无一剩余点。

这不反驳定理：空图虽使每对事件都无边，却不是依赖图，因为例如 $A_1$ 与其他三个事件联合生成的代数并不独立（后三个的不发生交事件与 $A_1$ 的条件行为不同）。局部引理里的“独立于非邻居族”不可降格为逐对独立。与此同时，并集界只给出 $\sum _i\mathbb{P}(A_i)=4/3$，同样无法得出存在性。

5. 今日一问与数学地图 (Question & Map)

今日一问。 给定有限 $k$-一致超图，各边至多与 $d$ 条其他边相交。已知随机二染满足 $e(d+1)2^{1-k}\le 1$。若把同一套存在性证明改成“只重抽当前单色边的颜色”，要记录何种历史对象，才能避免将循环重抽误判为独立试验？只画出所需依赖信息，不必证明算法终止。

地图：独立基变量与条件概率 $⟶$ 依赖图、邻域乘积 $⟶$ 超图二染色 $⟶$ 重抽样见证树 (witness trees) 与构造性局部引理。今日给的是有限存在性；无限超图还需另加有限约束与紧致性等桥梁，不能从本定理直接套用。

附录 A：习题完整解答 (Full Solution)

展开完整解答

模板：独立和的方差可加 + Chebyshev 尾界。 记 $m_i=\mathbb{E}{X}_i$。因 $0\le X_i\le 1$，有 $X_i^2\le X_i$，所以 $\mathrm{Var}(X_i)=\mathbb{E}{X}_i^2-m_i^2\le m_i(1-m_i)\le 1/4$。令 $Y_n=n^{-1}\sum _i(X_i-m_i)$；每项可积且二阶矩有限，独立性使 $i\ne j$ 时 $\mathbb{E}[(X_i-m_i)(X_j-m_j)]=0$。故 $\mathbb{E}{Y}_n=0$ 且 $\mathbb{E}{Y}_n^2=n^{-2}\sum _{i=1}^n\mathrm{Var}(X_i)\le 1/(4n)$。对 $Y_n^2$ 用 Markov 不等式得到 $\mathbb{P}(|Y_n|\ge \epsilon )\le \mathbb{E}{Y}_n^2/{\epsilon }^2\le 1/(4n{\epsilon }^2)$。对任意固定 $\epsilon >0$，右端随 $n\to \mathrm{\infty }$ 趋零，即依概率收敛。结论只涉及中心化的 $Y_n$，无须假定 ${\mu }_n$ 有极限。

资料与来源 (Sources)

• Yufei Zhao, Probabilistic Methods in Combinatorics, §6.1–6.2, “Lovász Local Lemma” （MIT 教学讲义；定义、两种形式、证明、超图二染色例子）: https://yufeizhao.com/pm/6.pdf
• Timothy Gowers, “Why I didn’t sign the Fields medallists’ letter”, 2026-09-17，作者第一人称文章；本次以同文客座转载核对引文: https://terrytao.wordpress.com/2026/09/17/why-i-didnt-sign-the-fields-medallists-letter/