2026-10-07 · 余量如何买来并行速度

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

Develata，今天是局部依赖微弧的 3/3，承接 10 月 6 日的见证树证明，兑现昨天留下的“大证书是否意味着长运行”之问。本期是深化，不是重讲期望终止定理。

起点有一个容易漏掉的逻辑缺口：总共修了很多次，未必有一条很长的相互影响链。 许多互不干扰的小修复可以同时完成。因而必须区分总工作量 (work)、并行轮数与证书深度，不能把三个计数器写成同一个 $T$。

对象分层：有限独立基变量 → 由变量支撑决定的坏事件 → 每轮所选的事件集合 → 执行日志的见证树。概率量词针对整个随机运行；树大小是证书的属性；并行轮数还依赖调度规则。前置为有限乘积概率、图的独立集、几何级数，以及上期见证树引理。主机制为“每个顶点省一点概率 → 对全部证书求和 → 用极大性把迟延变成深度”。研究生延伸是工作量与关键路径的区别，而非把并行硬件成本藏在定理里。

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

1.1 设置与真正新增的条件

设 $I$ 为有限集，$(X_i{)}_{i\in I}$ 为相互独立的有限取值随机变量，$\mathcal{A}$ 为非空有限坏事件族。对每个 $A\in \mathcal{A}$ 指定支撑 $S(A)\subseteq I$，使 $A$ 仅由这些坐标决定。令

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

这给出支撑相交图。设存在 $\epsilon \in (0,1)$ 及 $x:\mathcal{A}\to (0,1)$，满足

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

记

$$x^{\prime }(A)=x(A)\prod _{B\in \mathrm{\Gamma }(A)}(1-x(B)),K=\sum _{A\in \mathcal{A}}\frac{x(A)}{1-x(A)}>0.$$

$\epsilon$ 是统一余量 (slack)。相比上期，新增的不是独立性，而是每个事件概率都比原来的可用预算少一个因子。

1.2 先不谈并行：大树已经稀少

回忆上期两项引理，并写清它们的用途。对任何不窥看未来随机数、只重抽当前坏事件的顺序执行：

• 把日志从某次重抽开始向前逆扫；旧事件若与树中某标签相交，就挂在最深的相交顶点下面。所得为正规见证树 (proper witness tree)：子标签属于父标签的 ${\mathrm{\Gamma }}^{+}$，同父的子标签互异。
• 对固定树 $\tau$，随机表耦合给出

$$\begin{array}{}\text{(2)}& \mathbb{P}(\tau \text{ 出现})\le \prod _{v\in V(\tau )}{p}_{[v]}.\end{array}$$

这里 $[v]\in \mathcal{A}$ 是顶点标签。固定证书检查的是彼此不同的随机表单元，所以可相乘；实际自适应轮次没有因此变成独立试验。

若 ${\mathcal{T}}_A$ 是根标签为 $A$ 的全部有限正规见证树，上期的辅助分枝过程给出

$$\begin{array}{}\text{(3)}& \sum _{\tau \in {\mathcal{T}}_A}\prod _{v\in V(\tau )}{x}^{\prime }([v])\le \frac{x(A)}{1-x(A)}.\end{array}$$

其核算理由是：对每个父标签 $B$，分别以概率 $x(D)$ 生成标签 $D\in {\mathrm{\Gamma }}^{+}(B)$ 的孩子；生成恰好 $\tau$ 的概率等于 $(1-x(A))/x(A)$ 乘以式 (3) 的单树权重。所有有限树的概率总和至多为一，即使分枝过程可能不灭绝也无妨。[1, §§2–3]

大证书尾界。 对每个整数 $s\ge 1$，令 $H_s$ 表示“日志中存在至少有 $s$ 个顶点的见证树”。由可数并集界、(1)–(3)，

$$\begin{array}{}\text{(4)}& \begin{array}{rl}\mathbb{P}(H_s)& \le \sum _{A\in \mathcal{A}}\sum _{\begin{array}{c}\tau \in {\mathcal{T}}_A\\ |V(\tau )|\ge s\end{array}}(1-\epsilon {)}^{|V(\tau )|}\prod _v{x}^{\prime }([v])\\ & \le (1-\epsilon {)}^{s}K.\end{array}\end{array}$$

这一步已回答昨日第一问：每个顶点都带来一次折扣，无须重新估计树的组合数量。但 (4) 尚未控制总日志长度。

1.3 极大独立集怎样把轮数变成深度

并行算法：独立初始化所有变量；每轮在当前发生的坏事件所诱导的子图里，选择一个极大独立集 (maximal independent set) $M$，对所有 $A\in M$ 的支撑同时独立重抽，直至无坏事件。

独立集指任意两个不同成员之间无边；极大指不能再加入任何当前坏事件而保持独立。等价地，

$$\mathrm{\forall }B\text{ 当前发生且 }B\notin M,\mathrm{\exists }A\in M:S(A)\cap S(B)\ne \varnothing .$$

它不是基数最大的独立集 (maximum independent set)。本定理只要求前者。选择规则可以依赖已知状态与过去，不能窥看将来的随机表。

同一轮选出的事件支撑两两不交，故可按任意固定顺序串行化：先重抽其中一个不会改变同轮另一个仍然发生的事实。于是前述日志和树引理适用。

深度引理。 若某次重抽属于第 $j$ 轮，则它对应的见证树深度恰为 $j-1$，根深度记作零。[1, Lemma 4.1]

证明。 逆扫同一轮内的其他重抽不会加入根的树，因为支撑不交。随后按轮从 $j-1$ 扫到 $1$。归纳设已经扫过晚于第 $k$ 轮的部分：

1. 第 $k$ 轮内标签两两不交，新加入的顶点不会彼此成为父子，因此树深度至多增加一。
2. 取旧树中最深顶点 $v$。若扫过第 $k$ 轮后深度没增加，则第 $k$ 轮没有重抽 ${\mathrm{\Gamma }}^{+}([v])$ 中任何事件；否则该标签会挂在深度至少为 $v$ 的相交顶点下面。
3. 同样，在第 $k$ 轮之后、$v$ 对应的重抽之前，也不可能有与 $[v]$ 相交的重抽：逆扫时它会在 $v$ 已存在后加入，产生更深顶点，矛盾。因此从第 $k$ 轮开始直到重抽 $[v]$ 前，它的支撑一直未变。
4. $[v]$ 在后来重抽前发生，所以在第 $k$ 轮开始时已经发生。但该轮既没选它，也没选它的任何邻居，违背极大性。

所以每向前扫一轮，深度恰增一，结论得证。这里的第三步是因果持续性的关键，不能用“显然每轮贡献一层”替代。

1.4 并行轮数定理：显式尾界与期望界

令 $R\in {\mathbb{N}}_0\cup \{\mathrm{\infty }\}$ 为并行重抽轮数；初始化后已无坏事件时 $R=0$。对每个整数 $r\ge 1$，$R\ge r$ 蕴含第 $r$ 轮中某个见证树深度为 $r-1$，因而至少有 $r$ 个顶点。由 (4)，

$$\begin{array}{}\text{(5)}& \boxed{{\displaystyle \mathbb{P}(R\ge r)\le min\{1,K(1-\epsilon {)}^r\}\le min\{1,K{e}^{-\epsilon r}\}.}}\end{array}$$

这是 Moser–Tardos 并行分析的核心，而非单纯从有限期望推出的结论。[1, §4]

为避免 $K<1$ 时书写 $\log K$ 所造成的歧义，给出处处有效的版本。置

$$a=-\log (1-\epsilon )>0,L=\lceil \frac{\log max\{1,K\}}{a}\rceil .$$

由 $K(1-\epsilon {)}^L\le 1$ 及尾和恒等式，

$$\begin{array}{}\text{(6)}& \mathbb{E}R=\sum _{r\ge 1}\mathbb{P}(R\ge r)\le L+\sum _{r=L+1}^{\mathrm{\infty }}K(1-\epsilon {)}^r\le L+\frac{1-\epsilon }{\epsilon }\le 1+\frac{\log max\{1,K\}+1}{\epsilon }.\end{array}$$

特别地，$R<\mathrm{\infty }$ 几乎必然。对任意 $\delta \in (0,1)$，取

$$r\ge max\{1,\lceil \frac{\log (K/\delta )}{a}\rceil \}$$

即可保证 $\mathbb{P}(R\ge r)\le \delta$。这些都是对指定算法、指定实例参数的界，不是各轮条件成功率恒定的断言。

1.5 谱系与研究生延伸

这一微弧的逻辑链是：局部引理给正概率存在性 → 变量模型允许局部重抽 → 见证树控制期望工作量 → 严格余量压低大树概率 → 极大调度把并行延迟映射到证书深度。最后两箭头正是本期增量。

现代算法视角。 $R$ 是同步重抽轮数，不是实际运行时间。每轮还要检测坏事件、求极大独立集、抽样及通信。总重抽工作量可以线性增长，而轮数仅对数增长；这是总工作与关键路径 (critical path) 的分离。我们只证明上述具体模型的轮数界，不把它直接升级为任意分布式模型的消息复杂度或最优并行时间，也不把 2009 年论文结尾的问题清单当作今天的未解问题。

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

题目。 设 $n\ge 1$，$0<p<q<1$，$X_1,\dots ,X_n$ 为相互独立、参数为 $p$ 的 Bernoulli 随机变量，$S_n=\sum _{i=1}^n{X}_i$。证明

$$\mathbb{P}(S_n\ge nq)\le e^{-nD(q\Vert p)},D(q\Vert p)=q\log \frac{q}{p}+(1-q)\log \frac{1-q}{1-p}.$$

对数均为自然对数；$nq$ 不必是整数。

模板识别。 信号是“独立和的上尾”以及“想要指数级而非多项式级界”。把和放进指数，独立性便把一个难处理的尾事件转换为可以相乘的矩；最后还有一个自由参数需要优化。

分级提示。

1. 对任意 $t>0$，将 $\{S_n\ge nq\}$ 写成指数随机变量的上尾，再用 Markov 不等式。
2. 先算 $\mathbb{E}{e}^{t{X}_1}$，不要把 $e^{t\mathbb{E}{X}_1}$ 误当成它。
3. 对上界取对数并除以 $n$；求导时关注 $-tq+\log (1-p+p{e}^t)$ 的驻点，以及它为何落在 $t>0$。

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

人物与记录。 Terence Tao，个人网站 What's New 的 Career Advice 随笔 “Work hard”。这是作者本人的研究方法反思，包含其个人经验判断；本次原页未提供可确认的统一发布日期，故不补写年份。[2]

“The devil is often in the details; if you think you understand a piece of mathematics, you should be able to back that up by having read all the relevant literature and having written down at least a sketch of how that piece of mathematics goes, and then ultimately writing up a complete and detailed treatment of the topic.”

译：“问题往往藏在细节里；若你认为自己理解了一段数学，就应当能以读过全部相关文献、至少写出它如何成立的梗概来支撑这一判断，并最终写出完整而详细的论述。”

上下文转述（非引文）。 Tao 接着反对只抛出宏大想法、期待别人承担全部细节的分工幻想；文末又明确区分努力工作与最大化工作时长。他强调的是有准备、有支撑证据的高质量投入，而非把疲劳当成研究成果。

本刊解读。 今天最该写下的“细节”不是再算一次几何级数，而是验证这个箭头：为什么第 $j$ 轮仍需修复，就必有深度 $j-1$ 的证书？独立性只能解释同轮更新不冲突；极大性才排除一个坏事件一直无人理会。把证明写到这一步，直觉才暴露出自己暗中借用的调度假设。这个应用是本刊的解释，不是 Tao 在该文中讨论 Moser–Tardos 算法。

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

邻近错误命题：“每轮只要选一个非空独立集，就仍有 (5) 的并行轮数界。”

我们沿用前期不交支撑的测试场景，但改变问题：昨天比较全局重启与局部修复；今天检验局部修复内部的调度极大性，给出直接的概率矛盾。

取 $m=256$ 个独立 Bernoulli$(1/4)$ 变量，$A_i=\{X_i=1\}$，每个事件只依赖坐标 $i$。逐项核查：

1. 依赖图为空图。取 $x(A_i)=1/2$、$\epsilon =1/2$，则 $p_{A_i}=(1-\epsilon )x(A_i)=1/4$，严格余量条件完全满足，且 $K=256$。
2. 非极大策略：每轮只选编号最小的当前坏事件，重抽该坐标。单点集总是独立集，但只要还有其他坏事件，它就不是极大的。
3. 令 $B$ 为初始坏坐标个数，则 $B\sim \mathrm{Bin}(256,1/4)$，$\mathbb{E}B=64$、$\mathrm{Var}(B)=48$。每个初始坏坐标都至少要被重抽一次才能修好；一次仅修一个，故该策略的轮数 $R_{\mathrm{one}}\ge B$。
4. 由 Chebyshev 不等式，

$$\mathbb{P}(R_{\mathrm{one}}\ge 32)\ge \mathbb{P}(B\ge 32)\ge 1-\frac{48}{{32}^2}=\frac{61}{64}.$$

5. 若误用 (5)，却会得到

$$\mathbb{P}(R_{\mathrm{one}}\ge 32)\le 256\cdot 2^{-32}=2^{-24},$$

与上一项矛盾。

失效点不在概率模型、余量或独立集性质，而只在未要求极大。空图上真正的极大独立集必须包含全部当前坏事件；单点策略则人为把本可并行的任务串行化。

同时，这个场景解释了为何大树界不直接控制总工作量：不同坐标的重抽不会进入同一棵树；许多小分量可以累积大量操作，任何一个分量都不必有大证书。这里所有数值来自上面的精确均值、方差与分数运算，不声称做了随机模拟。

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

今日一问。 若没有统一余量，而是对每个事件分别给出 ${\epsilon }_A\in (0,1)$，满足

$$p_A\le (1-{\epsilon }_A)x^{\prime }(A),$$

请给每个证书顶点定义代价 $c_A=-\log (1-{\epsilon }_A)$，考察树的总费用

$$C(\tau )=\sum _{v\in V(\tau )}{c}_{[v]}.$$

你能否先证明一个关于“出现 $C(\tau )\ge u$ 的证书”的尾界，再判断它何时能优于简单使用 $\underset{A}{min}{\epsilon }_A$ 的轮数估计？特别是：只有一类事件余量很小时，仅凭依赖图的结构，真能阻止同一个事件反复出现、独自支撑很深的因果链吗？若不能，还缺什么信息？

提示只到此为止：概率折扣按顶点相乘，取负对数后成为可加费用；但从费用回到轮数，仍需单独的结构性下界，不能把加权深度当成普通深度。

数学地图： 独立基变量 → 局部依赖与概率存在性 → 重抽样日志 → 见证树与分枝求和 → 余量、证书费用 → 并行调度与关键路径。另一支从今日习题的指数矩 → 参数优化 → 倾斜测度与大偏差。两条路线都用指数权重，但“给历史证书付费”与“对随机和倾斜”并非同一个证明。

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

展开完整解答

可复用模板：指数 Markov → 独立分解矩母函数 → 优化倾斜参数。

对每个 $t>0$，指数函数单调，且 $e^{t{S}_n}$ 非负，故

$$\mathbb{P}(S_n\ge nq)\le e^{-tnq}\mathbb{E}{e}^{t{S}_n}=e^{-tnq}\prod _{i=1}^n\mathbb{E}{e}^{t{X}_i}=\exp \{n[-tq+\log (1-p+p{e}^t)]\}.$$

中间乘积用到联合独立性；单个期望为 $(1-p)+p{e}^t$，有限且显式。

置 $f(t)=-tq+\log (1-p+p{e}^t)$，则

$$f^{\prime }(t)=-q+\frac{p{e}^t}{1-p+p{e}^t},f^{″}(t)=\frac{p(1-p)e^t}{(1-p+p{e}^t{)}^2}>0.$$

因此 $f$ 严格凸。唯一驻点满足

$$e^{t_{\ast }}=\frac{q(1-p)}{p(1-q)}>1,t_{\ast }=\log \frac{q(1-p)}{p(1-q)}>0,$$

所以它属于允许的优化范围，并给全局最小值。又

$$1-p+p{e}^{t_{\ast }}=\frac{1-p}{1-q}.$$

代入并整理得

$$\begin{array}{rl}f(t_{\ast })& =-q\log \frac{q(1-p)}{p(1-q)}+\log \frac{1-p}{1-q}\\ & =-q\log \frac{q}{p}-(1-q)\log \frac{1-q}{1-p}=-D(q\Vert p).\end{array}$$

于是得到所求不等式。由于 $f(0)=0$、$f^{\prime }(0)=p-q<0$，最小值严格负，故 $D(q\Vert p)>0$；所得确是指数衰减上界。$nq$ 非整数不影响 Markov 步骤，无需悄悄假设它为整数。

资料与来源 (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.3、§§2–3 的两项见证树引理、§4 的 Lemma 4.1 与轮数分析，以及 §7 对实现成本的区分。PDF：https://arxiv.org/pdf/0903.0544 。L2/author-paper。本文式 (6) 将原文渐近期望表述改写成对小 $K$ 也明确定义的显式上界；第 4 节是本刊据模型构造的边界检验。
2. Terence Tao, “Work hard”, What's New, Career Advice。本人撰写的研究方法随笔；核验原文正文与末段，未确认发布日期，故不作推定。https://terrytao.wordpress.com/career-advice/work-hard/ 。L2/first-person-essay。短引文来自 Tao 正文，不采用页面开头转引的 André Weil 语句，以免把二手转引当作本次已经核验的回忆录原文。

核验日期：2026-10-07，星期三，Asia/Shanghai。本期使用同日成功的 RSS 投影作为发现背景，但未引用其中未经打开的条目；最终按内容质量选择原始论文与第一人称随笔，不按出版年龄筛选。AnySearch 的一次 Trevisan 定向检索未找到适用的一人称材料，未将此解释为该作者没有相关写作；随后采用并核验登记册中的 Tao 原页。与上期的衔接依据本地存档 2026/10/2026-10-06.md。元数据 source_ids 记录已登记的来源，技术论文完整出处见 [1]。习题及反例给出自足推导，不依赖未核验的外部题解。