2026-10-06 · 只修坏掉的一小块

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

Develata，上一期（9 月 25 日）证明了“存在一个赋值，避开所有坏事件”。今天续接同一三篇微弧的第 2/3 篇，不把中间的日历间隔冒充已刊内容。新的问题是：发现一处坏约束后，只重新随机化它涉及的变量，会不会越修越坏、永远循环？

对象分三层：相互独立的基变量；由有限变量支撑决定的坏事件；算法运行后才产生的随机历史。前两层的独立性并不使第三层的每一轮独立。我们要对每个事件给出期望修复次数界，而不只给“最终能成功”的存在量词。

前置是有限乘积概率、期望与标号树。主证明机制为：预先展开随机表 → 倒着追踪局部冲突 → 用见证树压缩历史 → 通过分枝过程对所有树求和。主线可从高年级本科进入；多类型分枝过程是本期的研究生桥梁。习题另练“尾和 + 条件成功率”，并特别指出它不能直接替代见证树证明。

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

从存在证据到可执行结构

上期的 Lovász 局部引理适用于抽象事件依赖图；今天增加变量模型 (variable model)：取有限指标集 $I$，相互独立的随机变量 $(X_i{)}_{i\in I}$，以及有限坏事件族 $\mathcal{A}$。对每个 $A\in \mathcal{A}$，给定支撑 $S(A)\subseteq I$，使 $A$ 仅由 $(X_i{)}_{i\in S(A)}$ 决定。这里可取有限取值变量以避开与主旨无关的抽样实现问题。定义

$$\mathrm{\Gamma }(A)=\{B\in \mathcal{A}\setminus \{A\}:S(B)\cap S(A)\ne \varnothing \},{\mathrm{\Gamma }}^{+}(A)=\mathrm{\Gamma }(A)\cup \{A\}.$$

算法。 先独立抽取所有变量；只要仍有坏事件发生，就选一个发生的 $A$，将 $S(A)$ 内的全部变量按各自原分布、使用新鲜独立随机性重抽，其他变量不动。固定一种可依据当前及过去信息、但不窥看未来随机数的选择规则，例如选编号最小的坏事件。没有坏事件时输出当前赋值。

这不是把抽象依赖图直接变成程序：还需知道支撑、能抽样并能检测事件。Moser–Tardos 原文将此前构造性局部引理的工作推进到这一自然变量框架；本文采用其 2009 年预印本的 Theorem 1.2 及 §§2–3。[1]

定理：每个事件都有修复预算

假定存在函数 $x:\mathcal{A}\to (0,1)$，满足

$$\mathrm{\forall }A\in \mathcal{A},p_A:=\mathbb{P}(A)\le x(A)\prod _{B\in \mathrm{\Gamma }(A)}(1-x(B)).$$

令 $N_A\in {\mathbb{N}}_0\cup \{\mathrm{\infty }\}$ 是上述算法重抽事件 $A$ 的总次数。则

$$\mathrm{\forall }A\in \mathcal{A},\mathbb{E}{N}_A\le \frac{x(A)}{1-x(A)},\mathbb{E}\sum _{A\in \mathcal{A}}{N}_A\le \sum _{A\in \mathcal{A}}\frac{x(A)}{1-x(A)}<\mathrm{\infty }.$$

所以算法几乎必然在有限次重抽后停机，输出避开所有坏事件的赋值。初始抽样不计入 $N_A$。这是重抽样次数界；总运行时间还要计入抽样、检测及更新数据结构的成本。

证明骨架一：让重复发生留下不同的树

记执行日志为 $C(1),C(2),\dots$，其中 $C(t)$ 是第 $t$ 次重抽的事件标签。固定已发生的一步 $t$，以 $C(t)$ 为根，逆序扫描 $t-1,\dots ,1$：若旧事件与现有某顶点标签共享变量（或标签相同），就将其挂在所有这类顶点中深度最大者之下；否则跳过。平局固定规则处理。所得标号根树叫见证树 (witness tree)。

子标签属于父标签的 ${\mathrm{\Gamma }}^{+}$；同一父顶点的子标签互异：若后来插入的旧标签与已有兄弟相同，它应挂到那个更深的兄弟或更深处，而不能仍作兄弟。称满足这两个条件的树为正规见证树 (proper witness tree)。

同一事件 $A$ 的第 $r$ 次重抽产生的树恰含 $r$ 个 $A$ 标签：逆序扫描时，所有更早的 $A$ 都因根的存在被纳入。因此不同次 $A$ 重抽产生不同的树。于是“重抽很多次”迫使“出现很多不同证书”。

证明骨架二：为什么固定树的概率可以相乘

预先为每个变量 $i$ 准备无限列独立副本 $X_i^{(0)},X_i^{(1)},\dots$；所有表格单元共同独立。算法开始使用第 $0$ 列，每次重抽该变量便前进一列。这只是揭示随机数的方式改变，没有改变算法分布。

若固定树 $\tau$ 确实由日志产生，则任何两个共享变量的顶点深度不同，且较早的重抽处在更深位置。这由“挂到最深处”直接保证。对顶点 $v$ 及 $i\in S([v])$，记

$$k_i(v)=\mathrm{\#}\{w\in V(\tau ):\mathrm{depth}(w)>\mathrm{depth}(v),i\in S([w])\},$$

其中 $[v]$ 是事件标签。算法在对应重抽之前使用的变量值就是 $X_i^{(k_i(v))}$：所有更早重抽过 $i$ 的步骤都会在逆扫中被纳入，不会漏掉。

从深到浅检查树上每个事件，便得到树出现的一个必要条件：每个标签都在这些指定表格单元上发生。不同顶点使用的表格单元互不重复，故检查全部通过的概率是 $\prod _v{p}_{[v]}$。从而

$$\mathbb{P}(\tau \text{ 出现在日志中})\le \prod _{v\in V(\tau )}{p}_{[v]}.$$

对根本不可能由日志产生的正规树，左端为零，界仍成立。相乘的是固定证书所检验的新鲜单元，不是实际运行中条件化后的各轮成功概率。

证明骨架三：用一棵随机树为所有树买单

设 ${\mathcal{T}}_A$ 为根标签 $A$ 的所有有限正规见证树，记

$$x^{\prime }(B)=x(B)\prod _{D\in \mathrm{\Gamma }(B)}(1-x(D)).$$

构造辅助分枝过程 (branching process)：根固定为 $A$；对每个标签为 $B$ 的顶点，独立地对每个 $D\in {\mathrm{\Gamma }}^{+}(B)$ 以概率 $x(D)$ 生一个标签为 $D$ 的孩子，否则不生。各顶点的选择也独立。孩子由标签区分，不额外计排列次序。

产生恰好 $\tau \in {\mathcal{T}}_A$ 的概率是

$$q_{\tau }=\frac{1-x(A)}{x(A)}\prod _{v\in V(\tau )}{x}^{\prime }([v]).$$

为何有根因子？直接相乘“生出的孩子贡献 $x(D)$，没生出的贡献 $1-x(D)$”；每个非根顶点恰作为孩子出现一次，而根是强制生出的。把各孩子的因子与父顶点的缺席因子整理，正好留下上述根修正。

该过程可能生成无限树；因此只用 $\sum _{\tau \in {\mathcal{T}}_A}{q}_{\tau }\le 1$，无需先证明分枝过程灭绝。结合不同重抽有不同树、非负求和以及 $p_B\le x^{\prime }(B)$，

$$\mathbb{E}{N}_A\le \sum _{\tau \in {\mathcal{T}}_A}\prod _{v\in V(\tau )}{p}_{[v]}\le \frac{x(A)}{1-x(A)}\sum _{\tau \in {\mathcal{T}}_A}{q}_{\tau }\le \frac{x(A)}{1-x(A)}.$$

有限期望排除正概率无限重抽，证明完成。

应用与研究生延伸

有限 $k$-一致超图的顶点独立等概率二染色；坏事件是某条边单色，故 $p=2^{1-k}$。若每边至多与 $d\ge 1$ 条其他边相交，且 $ep(d+1)\le 1$，取 $x=1/(d+1)$ 满足上述条件。算法只重染当前单色边上的顶点；若有 $m$ 条边，期望重染边次数至多 $m/d$。此处一次“重染边”抽取 $k$ 个新颜色，不能与一次变量抽样混算。

现代观点。 算法的状态可能不断相互扰动，却有可求和的历史证书。这种“控制证书总质量，而非寻找逐步下降的势函数”的方法，是从概率存在性走向随机算法的一条桥梁。下一篇将研究条件中多一点余量如何控制大树；本篇不把期望界擅自升级为指数尾界。

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

题目。 设 $({\mathcal{F}}_t{)}_{t\ge 0}$ 为过滤 (filtration)，$T$ 是取值于 $\{1,2,\dots \}\cup \{\mathrm{\infty }\}$ 的停止时刻，表示首个成功轮次。给定 $q\in (0,1]$，假设对每个整数 $t\ge 0$，几乎处处有

$$\mathbb{E}[{\mathbf{1}}_{\{T>t+1\}}\mid {\mathcal{F}}_t]\le (1-q){\mathbf{1}}_{\{T>t\}}.$$

证明对所有整数 $t\ge 0$，$\mathbb{P}(T>t)\le (1-q{)}^t$，并证明 $\mathbb{E}T\le 1/q$，从而 $T<\mathrm{\infty }$ 几乎必然。$t=0$ 的右端约定为 $1$。

模板识别。 信号是“给定全部过去，未成功的质量至少按固定比例减少”。不要求各轮独立；目标是先获得尾概率递推，再从尾部还原期望。

分级提示。

1. 对给定条件不等式取期望，使用条件期望的塔式性质。
2. 将整数值变量写成一串尾事件指示函数之和；$T=\mathrm{\infty }$ 时等式仍应成立。
3. 说明为什么可交换无穷求和与期望，再求几何级数。

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

作者与语境。 William P. Thurston，On Proof and Progress in Mathematics，发表于 Bulletin of the American Mathematical Society 30(2)，1994 年 4 月。第 2 节列举导数的无穷小、符号、逻辑、几何、速率、逼近等理解，并在印刷页 164 回忆自己怎样反复消化这些观点。[2]

“I also remember coming back to revisit these different concepts later with added meaning and understanding.”

译：“我也记得，后来再回头重访这些不同概念时，它们增添了意义，我也有了更深的理解。”

上下文转述（非引文）： Thurston 强调这里列举的是思考导数的不同方式，而非一串不同的逻辑定义；把直观翻译为形式定义时，原来不同的心智路径容易消失。他是在回顾个人学习经验，不是在要求以直观取代证明。

本刊解读。 今天可用三幅不同图像理解同一算法：向前看是不断修复赋值；把随机性一次摊开，是每行指针前进的随机表；向后看则是追索原因的树。三者不是三个定理，却分别暴露了可执行性、独立性和概率可求和性。真正值得重访的是它们怎样互相翻译，尤其“共享一个变量”怎样变成“读取同一行不同列”。这层联系是编者的解释，并非 Thurston 对后来重抽样算法的评论。

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

错误推论：“局部引理给出正的成功概率，所以每次全局重新抽一遍，也应当很快。”

令 $m\ge 1$，$X_1,\dots ,X_m$ 独立，且 $\mathbb{P}(X_i=1)=1/4$、$\mathbb{P}(X_i=0)=3/4$；坏事件 $A_i=\{X_i=1\}$。逐项检查：

• 每个坏事件只涉及自己的一个变量；依赖图为空图。
• 取 $x(A_i)=1/4$，局部引理条件取等，完全满足定理。
• 全体成功就是所有坐标为零，概率为 $(3/4{)}^m$。
• 若每次失败都丢弃整份赋值并独立全局重抽，首次成功的抽样轮数 $R$ 为参数 $(3/4{)}^m$ 的几何分布，故 $\mathbb{E}R=(4/3{)}^m$，是指数级；这包括初次抽样。
• 局部重抽不会破坏已修好的其他坐标。对单个坐标，成功前坏样本的个数满足 $\mathbb{P}(N_i\ge r)=(1/4{)}^r$（$r\ge 1$），所以

$$\mathbb{E}{N}_i=\sum _{r\ge 1}(1/4{)}^r=1/3,\mathbb{E}\sum _i{N}_i=m/3.$$

这里 $N_i$ 是重抽次数，不包括初始抽样；每一个坏样本恰触发一次重抽。单事件预算 $x/(1-x)=1/3$ 精确取等。计入初始化，局部算法的期望变量抽样数为 $4m/3$；全局方案则为 $m(4/3{)}^m$。

边界因而十分明确：正概率甚至一个正确的显式下界，不自动意味着全局拒绝抽样高效。 本例的局部性使已成功的部分得以保留；一般重叠支撑中这点不再逐步成立，才需要见证树，而非把各轮当成几何试验。习题中的统一条件成功率假设，并不是局部引理条件的直接改写。

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

今日一问。 若存在 $\epsilon \in (0,1)$，使每个事件满足更强条件

$$p_A\le (1-\epsilon )x(A)\prod _{B\in \mathrm{\Gamma }(A)}(1-x(B)),$$

你能否为“执行日志中出现至少有 $s$ 个顶点的见证树”给出显式概率上界？请再判断：这是否已经直接等价于“总重抽次数至少为 $s$”的尾界？只需找到两种证书大小的区别，不必推导并行定理。

提示：第一问对每棵树额外保留一个 $(1-\epsilon {)}^{|V(\tau )|}$；第二问想一想许多互不相交的局部修复。

地图：独立基变量 → 事件支撑相交 → 局部引理的可构造版本 → 随机表与见证树 → 分枝过程求和 → 大证书尾界、并行深度与约束满足算法。沿此路线，“存在好对象”和“能够有效找到好对象”终于共享了一份可审核的历史记账，但二者仍是不同结论。

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

展开完整解答

可复用模板：条件存活收缩 → 几何尾界 → 尾和恒等式。

记 $a_t=\mathbb{P}(T>t)$。由塔式性质，对每个 $t\ge 0$，

$$a_{t+1}=\mathbb{E}[\mathbb{E}({\mathbf{1}}_{\{T>t+1\}}\mid {\mathcal{F}}_t)]\le (1-q)a_t.$$

因为 $T\ge 1$，$a_0=1$。归纳即得 $a_t\le (1-q{)}^t$；$q=1$ 时所有 $t\ge 1$ 的尾概率为零。

对每个样本点，以扩展非负实数解释等式，

$$T=\sum _{t=0}^{\mathrm{\infty }}{\mathbf{1}}_{\{T>t\}}.$$

当 $T=n<\mathrm{\infty }$，恰有 $t=0,\dots ,n-1$ 这 $n$ 项为 $1$；当 $T=\mathrm{\infty }$，所有项为 $1$，双方均为无穷。由单调收敛定理（亦可用 Tonelli 定理），

$$\mathbb{E}T=\sum _{t=0}^{\mathrm{\infty }}\mathbb{P}(T>t)\le \sum _{t=0}^{\mathrm{\infty }}(1-q{)}^t=\frac{1}{q}.$$

若 $\mathbb{P}(T=\mathrm{\infty })>0$，则对每个 $M\ge 1$ 有 $\mathbb{E}T\ge M\mathbb{P}(T=\mathrm{\infty })$，令 $M\to \mathrm{\infty }$ 与有限上界矛盾。因此几乎必然终止。整个论证没有使用各轮独立性；真正的假设是对全部过去条件化后仍成立的统一收缩。

资料与来源 (Sources)

1. Robin A. Moser and Gábor Tardos, A constructive proof of the general Lovász Local Lemma, arXiv:0903.0544v3，2009-05-20。本文使用 Theorem 1.2、§2 的日志和见证树引理、§3 的分枝过程求和；§1 说明变量模型与抽象局部引理的差别。原文 PDF（本次实际提取并核验）：https://arxiv.org/pdf/0903.0544 。来源层级：L2/author-paper。不把这份 2009 年版本结尾的问题清单当作 2026 年仍未解决的问题清单。
2. William P. Thurston, “On Proof and Progress in Mathematics”, Bulletin (New Series) of the American Mathematical Society, 30(2), April 1994, 161–177。第 2 节，特别是印刷页 163–164 的导数理解与个人回忆；本次提取 AMS 原文并核对短引文：https://www.ams.org/journals/bull/1994-30-02/S0273-0979-1994-00502-6/S0273-0979-1994-00502-6.pdf 。来源层级：L2/first-person-essay。本文只引用理解方式的讨论，不沿用文末的历史未解问题状态。

本期来源核验时间基准为 2026-10-06（Asia/Shanghai）。同日 RSS 发现投影提供候选而非证据；本期最终采用历史原始论文与第一人称随笔，不按出版新旧筛选。第 4 节与习题解答是本文逐式推导，未声称运行数值模拟。前期衔接以本地存档 2026/09/2026-09-25.md 为准。元数据 source_ids 仅列登记册已有来源；技术论文的完整出处独立列于 [1]。