AFTD Auto-Formalizing Theoretical Domains

Research Blogs

森林边序列上随机贪心拼车的双指数尾部界与双对数偏差

low tier2026-11-13审阅: Claude CodeEnglish

摘要

在线拼车问题探讨如何为顶点之间到达的边定向,以最小化运行中的顶点偏差(discrepancy),该偏差定义为入度与出度之差。对于预先固定的任意边序列,arXiv:2611.00388 给出了一个偏差为 $O((\log T)^{1/3})$ 的随机化算法,与已知的下界相匹配。我们探究当到达的边构成森林时,简单的随机贪心算法表现如何,这是我们在此提出的问题;该论文并未提出这一问题。在这项工作中,我们分析了随机贪心拼车在遗忘型森林到达序列上的性能。我们证明,对于底层图为无圈图的任意 $T$ 条边的序列,所有顶点和所有前缀时刻的最大绝对偏差超过整数阈值 $D \ge 1$ 的概率以 $4 T \cdot \text{forest\_carpool\_tail\_envelope}(D)$ 为界,其中尾部包络在 $D = 2$ 时等于 $3/8$,对于所有其他阈值等于 $(1/2)^{\text{Fib}(D)}$。由于斐波那契数呈指数增长,这一尾部界关于 $D$ 是双指数的,从而确立了最大前缀偏差以高概率(w.h.p.)为 $O(\log \log T)$。证明表明,当两个独立连通分支被一条边合并时,每个顶点的偏差分布均保持对称、具有固定奇偶性且低于包络,进而将前缀最大值约化为边到达时刻的 $4T$ 个端点事件。整个推导均在 Lean 4 中经过形式化验证。

1. 引言

在线拼车问题对网络中重复共享交互的公平性进行建模。在该框架中,敌手在顶点集 $V = \{0, 1, \dots, n-1\}$ 上随时间选择一个边序列。在每个离散时间步 $t \in \{0, \dots, T-1\}$,一条无向边 $\{u_t, v_t\}$ 在线到达。在线算法必须立即且不可撤销地为这条边定向,决定该边是从 $u_t$ 指向 $v_t$ 还是从 $v_t$ 指向 $u_t$。顶点 $v$ 在时刻 $t$ 的偏差是截至时刻 $t$ 其入度与出度之差。算法的目标是最小化跨所有顶点及到达序列所有前缀的最大绝对顶点偏差。

针对遗忘型敌手(oblivious adversary)的在线拼车研究在 arXiv:2611.00388 中得以展开。在那里,遗忘型敌手预先选定整个边序列,该论文给出了一个基于高斯支配而非贪心选择的随机化算法,对于每个此类序列,其最大偏差以高概率达到 $O((\log T)^{1/3})$。由于对一般序列成立阶为 $(\log T)^{1/3}$ 的下界,因此该阶是最优的;困难实例会重复边或闭合环路。

在线拼车的一种自然且轻量级的策略是随机贪心算法。当一条边 $\{u, v\}$ 到达时,算法检查两个端点的当前偏差。如果一个端点的偏差严格低于另一个端点,则算法将该边朝向该端点定向(使其偏差增加 1,并将另一个端点的偏差减少 1),从而使它们的偏差更加接近。如果两个端点的偏差相等,算法通过抛掷一枚均匀硬币来打破平局。

我们提出以下该论文并未探讨的问题:当到达序列是一片森林,即没有边被重复且各边构成一个无圈图时,随机贪心算法能保证怎样的偏差?在森林上,每条到达的边连接两个不同的连通分支,因此其两个端点的偏差依赖于不相交的硬币集合。

我们证明,对于 $n$ 个顶点上由 $T$ 条边构成的每个遗忘型森林到达序列,随机贪心拼车在最大前缀偏差上都能达到双指数尾部界。具体而言,对于任意整数阈值 $D \ge 1$,所有顶点和所有前缀时刻 $0 \le t \le T$ 的最大绝对偏差至少为 $D$ 的概率满足 $$\Pr\left(\max_{0 \le t \le T} \max_{v \in V} |d_t(v)| \ge D\right) \le 4 T \cdot \text{forest\_carpool\_tail\_envelope}(D),$$ 其中 $\text{forest\_carpool\_tail\_envelope}(D)$ 在 $D = 2$ 时定义为 $3/8$,对 $D$ 的所有其他取值定义为 $(1/2)^{\text{Fib}(D)}$。

由于斐波那契数以底数 $\phi = (1+\sqrt{5})/2 \approx 1.618$ 指数增长,尾部包络 $(1/2)^{\text{Fib}(D)}$ 关于 $D$ 双指数衰减。因此,为确保超过阈值 $D$ 的概率至多为给定的误差 $\epsilon > 0$,只需选择 $D$ 使得 $\text{Fib}(D) \ge \log_2(4T/\epsilon)$。这表明整个轨迹上的最大偏差以高概率保持在 $O(\log \log T)$ 的界内。在森林上,这低于对一般序列而言最优的 $(\log T)^{1/3}$ 阶。

本文其余部分的结构如下。我们在 Lean 4 中形式化拼车设定与相关定义,叙述主定理(forest_carpool_maximum_fibonacci_tail),给出完整的数学证明及其形式化细节,并讨论与相关开放问题的联系。

2. 预备知识

我们在有限顶点集 $\text{Fin } n = \{0, 1, \dots, n-1\}$ 上形式化在线拼车模型。

定义 1(ValidCarpoolEdgeSequence)。若每条到达的边都连接两个不同的顶点,即 $$\forall e \in \text{edges}, \quad e.1 \ne e.2.$$ 则有向边对列表 $\text{edges} : \text{List } (\text{Fin } n \times \text{Fin } n)$ 对于 $n$ 个顶点上的在线拼车是合法的。 注:该条件排除了自环,但允许边以任意到达顺序排列。

定义 2(CarpoolForestEdgeSequence)。如果边列表 $\text{edges} : \text{List } (\text{Fin } n \times \text{Fin } n)$ 满足以下三个条件,则它是 $n$ 个顶点上的遗忘型森林边序列: 1. 它是合法的拼车边序列(ValidCarpoolEdgeSequence)。 2. 无向边两两各异,即无序对列表 $s(e.1, e.2) = \{e.1, e.2\}$ 不包含重复项。 3. 由边集 $\{ \{e.1, e.2\} \mid e \in \text{edges} \}$ 构成的无向简单图是无圈的。 注:在 Lean 4 中,该图是使用带有无序对的无向边集构造的。该条件既保证了没有无向边出现超过一次,又保证了所得图是一片森林。

定义 3(carpool_step)。给定整数偏差向量 $d : \text{Fin } n \to \mathbb{Z}$、边 $e = (u, v) \in \text{Fin } n \times \text{Fin } n$ 以及定向布尔值 $b \in \text{Bool}$,单步偏差更新 $\text{carpool\_step } n \; d \; e \; b : \text{Fin } n \to \mathbb{Z}$ 在每个顶点 $w \in \text{Fin } n$ 处定义为 $$(\text{carpool\_step } n \; d \; e \; b)(w) = d(w) + (\text{if } w = u \text{ then } (\text{if } b \text{ then } 1 \text{ else } -1) \text{ else } 0) + (\text{if } w = v \text{ then } (\text{if } b \text{ then } -1 \text{ else } 1) \text{ else } 0).$$ 注:当 $b = \text{true}$ 时,边朝向 $u$ 定向,为 $d(u)$ 增加 $+1$ 并为 $d(v)$ 增加 $-1$。当 $b = \text{false}$ 时,边朝向 $v$ 定向,为 $d(u)$ 增加 $-1$ 并为 $d(v)$ 增加 $+1$。未涉及的顶点保持不变。

定义 4(carpool_greedy_orientations)。给定边列表 $\text{edges}$ 和布尔硬币列表 $\text{coins}$,函数 $\text{carpool\_greedy\_orientations } n \; \text{edges} \; \text{coins} : \text{List Bool}$ 从对所有 $w$ 均为零的初始偏差 $d_0(w) = 0$ 出发,计算随机贪心拼车的定向选择。在每一步,给定当前偏差 $d$、到达边 $e = (u, v)$ 和决胜硬币 $c$,定向比特 $b$ 选择为 $$b = \begin{cases} \text{true} & \text{if } d(u) < d(v) \\ \text{false} & \text{if } d(v) < d(u) \\ c & \text{if } d(u) = d(v). \end{cases}$$ 算法追加 $b$,并使用更新后的偏差向量 $\text{carpool\_step } n \; d \; e \; b$ 在后续的边和硬币上进行递归。 注:若任一列表为空,则递归生成空列表。当通过函数至列表转换由函数 $r : \text{Fin } T \to \text{Bool}$ 提供硬币时,两列表具有相同的长度 $T = \text{edges.length}$。

定义 5(max_vertex_discrepancy)。对于整数偏差向量 $d : \text{Fin } n \to \mathbb{Z}$,其最大绝对顶点偏差定义为 $$\text{max\_vertex\_discrepancy } n \; d = \sup_{v \in \text{Fin } n} |d(v)|_{\mathbb{N}}.$$ 注:上确界是在顶点的有限全集上取的,产生一个自然数。

定义 6(carpool_max_discrepancy)。给定边 $\text{edges}$ 和定向比特 $\text{signs}$,令中间偏差表示从 $d_0 = \lambda v.\, 0$ 出发通过迭代应用 carpool_step 得到的中间偏差向量列表 $d_0, d_1, \dots, d_T$。最大前缀偏差定义为 $$\text{carpool\_max\_discrepancy } n \; \text{edges} \; \text{signs} = \text{foldl } \max \; 0 \; ((\text{carpool\_discrepancies } n \; \text{edges} \; \text{signs}).\text{map } (\text{max\_vertex\_discrepancy } n)).$$ 注:这计算了在所有时间步 $0 \le t \le T$ 和所有顶点 $w$ 上的 $|d_t(w)|_{\mathbb{N}}$ 的最大值。对于空边列表,其求值结果为 0。

定义 7(forest_carpool_final_discrepancy)。给定边 $\text{edges}$、硬币赋值 $r : \text{Fin } T \to \text{Bool}$ 以及顶点 $v \in \text{Fin } n$,顶点 $v$ 的最终偏差定义为 $$\text{forest\_carpool\_final\_discrepancy } n \; \text{edges} \; r \; v = d_T(v),$$ 即在根据硬币 $r$ 进行贪心定向后,顶点 $v$ 处的最终偏差向量的值。

定义 8(forest_carpool_tail_envelope)。单侧偏差尾部包络函数 $\text{forest\_carpool\_tail\_envelope} : \mathbb{N} \to \mathbb{R}$ 定义为 $$\text{forest\_carpool\_tail\_envelope}(k) = \begin{cases} \frac{3}{8} & \text{if } k = 2 \\ \left(\frac{1}{2}\right)^{\text{Fib}(k)} & \text{if } k \ne 2 \end{cases}$$ 其中 $\text{Fib}(k)$ 是第 $k$ 个斐波那契数,满足 $\text{Fib}(0) = 0, \text{Fib}(1) = 1, \text{Fib}(2) = 1, \text{Fib}(3) = 2, \text{Fib}(4) = 3, \dots$。 注:在 $k = 2$ 处,标准斐波那契幂 $(1/2)^{\text{Fib}(2)} = 1/2$ 被严格更紧的值 $3/8$ 所替代。对于 $k = 1$,该包络等于 $(1/2)^1 = 1/2$。

3. 主要结果

本工作确立的主定理是 forest_carpool_maximum_fibonacci_tail,它为森林边序列上随机贪心拼车的最大前缀偏差尾部概率给出了一个双指数上界。

定理(forest_carpool_maximum_fibonacci_tail)。 设 $n \in \mathbb{N}$,且令 $\text{edges}$ 为顶点 $\text{Fin } n$ 上长度为 $T = \text{edges.length}$ 且满足无圈森林条件 CarpoolForestEdgeSequence 的边列表。设 $D \in \mathbb{N}$ 为满足 $1 \le D$ 的整数偏差阈值。当决胜硬币独立且均匀随机地从 $\{\text{true}, \text{false}\}$ 中选取时,跨所有顶点和所有时间步的最大前缀偏差达到或超过 $D$ 的概率满足 $$\frac{\#\left\{ r : \text{Fin } T \to \text{Bool} \;\middle|\; D \le \text{carpool\_max\_discrepancy } n \; \text{edges} \; (\text{carpool\_greedy\_orientations } n \; \text{edges} \; (\text{List.ofFn } r)) \right\}}{2^T} \le 4 T \cdot \text{forest\_carpool\_tail\_envelope}(D).$$

forest_carpool_maximum_fibonacci_tail 的 Lean 命题直接翻译了这一不等式:在全集有限集上过滤硬币赋值 $r : \text{Fin } T \to \text{Bool}$ 的有限全集,将所得基数强转为实数,除以实数量 $2^{\text{edges.length}}$,并在显式假设 $1 \le D$ 下将该比值以 $4 \cdot \text{edges.length} \cdot \text{forest\_carpool\_tail\_envelope } D$ 为界。

该主定理建立在描述随机贪心拼车在无圈拓扑上行为的两个结构性结果之上:

1. 空间局部性(forest_carpool_component_coin_locality): 对于任意顶点 $v \in \text{Fin } n$,$v$ 的最终偏差仅依赖于 $v$ 所在连通分支中各边的硬币赋值。若两个硬币赋值 $r, s : \text{Fin } T \to \text{Bool}$ 在由 $\text{edges}$ 构成的无向图中从 $v$ 可达的每条边上都一致,则 $$\text{forest\_carpool\_final\_discrepancy } n \; \text{edges} \; r \; v = \text{forest\_carpool\_final\_discrepancy } n \; \text{edges} \; s \; v.$$ 这种局部性保证了在不连通分支上的抛硬币不会干扰 $v$ 的轨迹,从而确保了各个分离子树之间的统计独立性。

2. 单侧顶点尾部(forest_carpool_final_one_sided_fibonacci_tail): 对于任意森林到达序列和任意顶点 $v \in \text{Fin } n$,$v$ 的最终偏差至少为 $D$ 的均匀概率以斐波那契尾部包络为界: $$\frac{\#\left\{ r : \text{Fin } T \to \text{Bool} \;\middle|\; D \le \text{forest\_carpool\_final\_discrepancy } n \; \text{edges} \; r \; v \right\}}{2^T} \le \text{forest\_carpool\_tail\_envelope}(D).$$ 由定向选择 $+1$ 与 $-1$ 之间的对称性,相同的界对下尾事件 $d_T(v) \le -D$ 同样成立。

该主定理表明,尽管前缀最大值涉及对所有 $n$ 个顶点和所有 $T+1$ 个中间时间步取上确界,但底层森林结构使得全局最大值能够仅由 $4T$ 个单侧顶点事件的并来控制,相对于 forest_carpool_tail_envelope 的双指数衰减仅产生了 $4T$ 的线性损失因子。

定理 forest_carpool_maximum_fibonacci_tail (Lean 4 已验证)
theorem forest_carpool_maximum_fibonacci_tail (n : ℕ)
    (edges : List (Fin n × Fin n)) (hf : CarpoolForestEdgeSequence n edges)
    (D : ℕ) (hD : 1 ≤ D) :
  (((Finset.univ.filter (fun r : Fin edges.length → Bool =>
    D ≤ carpool_max_discrepancy n edges
      (carpool_greedy_orientations n edges (List.ofFn r)))).card : ℝ) /
    (2 ^ edges.length : ℝ)) ≤ 4 * edges.length * forest_carpool_tail_envelope D

4. 证明

我们将证明分为三个部分:高层几何思想、关于无圈图的两个支撑引理,以及将它们结合得出最终界的分步验证。

界定最大前缀偏差的主要挑战在于,上确界是在所有 $n$ 个顶点和所有中间时间步 $0 \le t \le T$ 上取的。在所有顶点和所有前缀上应用联合界(union bound)将招致 $n(T+1)$ 的因子。然而,在在线拼车中,顶点的偏差发生改变当且仅当与该顶点关联的边到达。

对于任意硬币序列 $r$,若最大前缀偏差至少为 $D \ge 1$,则必存在中间步 $i \le T$ 和顶点 $w$ 使得 $|d_i(w)| \ge D$。因为所有偏差均从 0 开始且 $D \ge 1$,这不可能发生在第 0 步。因此在第 $i$ 步之前,$w$ 必定至少被一条到达的边所触及。令 $j < i$ 为前 $i$ 条边中与 $w$ 关联的最后一条边的索引。因为在时间步 $j+1$ 和时间步 $i$ 之间没有与 $w$ 关联的边到达,所以 $w$ 的偏差在该区间内完全保持不变,故而 $d_i(w) = d_{j+1}(w)$。

此外,由于边 $j$ 触及 $w$,顶点 $w$ 必须是边 $j$ 的两个端点之一,即 $(\text{edges}[j]).1$ 或 $(\text{edges}[j]).2$。因此,沿轨迹任何位置对阈值 $D$ 的违反,都对应于在第 $j+1$ 步边 $j$ 的两个端点之一在正方向或负方向上的违反。对于每个边索引 $j \in \{0, \dots, T-1\}$,恰好存在 $4$ 种这样的“端点-符号”组合,总共产生 $4T$ 个基本事件。由于森林序列的每个前缀本身都是森林序列,因此每个基本事件通过单侧顶点尾部界均以 $\text{forest\_carpool\_tail\_envelope}(D)$ 为界。

引理 1(forest_carpool_component_coin_locality)。设 $n \in \mathbb{N}$,且令 $\text{edges}$ 为长度为 $T$ 的边序列。设 $v \in \text{Fin } n$,且令 $r, s : \text{Fin } T \to \text{Bool}$ 为两个硬币赋值。若对于使得端点 $(\text{edges}[i]).1$ 在各边构成的简单图中从 $v$ 可达的每个索引 $i \in \text{Fin } T$,均有 $r(i) = s(i)$,则 $$\text{forest\_carpool\_final\_discrepancy } n \; \text{edges} \; r \; v = \text{forest\_carpool\_final\_discrepancy } n \; \text{edges} \; s \; v.$$

引理 1 的证明。在在线拼车中,状态更新 carpool_step 仅修改到达边两个端点处的偏差值。在贪心算法中,定向的选择仅依赖于这两个端点偏差的相对顺序,以及在相等时分配给该边的硬币。在简单图上,两个顶点属于同一个连通分支当且仅当它们互相可达。当一条边到达时,要么两个端点属于同一个连通分支,要么它们属于此前不相交、被该边合并的两个分支。通过对边序列的前缀长度进行归纳,限制在 $v$ 所在连通分支中各顶点上的偏差向量完全由该分支内的边及其关联的硬币决定。该分支之外各边上的硬币对 $v$ 所在分支中顶点的偏差没有任何影响。Lean 通过对边列表的归纳确立了这一结构不变性。

引理 2(forest_carpool_final_one_sided_fibonacci_tail)。设 $n \in \mathbb{N}$,且令 $\text{edges}$ 为拼车森林边序列(CarpoolForestEdgeSequence)。设 $v \in \text{Fin } n$ 且令 $D \in \mathbb{N}$ 满足 $1 \le D$。则 $$\frac{\#\left\{ r : \text{Fin } T \to \text{Bool} \;\middle|\; D \le \text{forest\_carpool\_final\_discrepancy } n \; \text{edges} \; r \; v \right\}}{2^T} \le \text{forest\_carpool\_tail\_envelope}(D).$$

引理 2 的证明。Lean 通过对边列表的归纳证明了一个更强的不变量:对于每个顶点 $v$,$d_T(v)$ 在均匀硬币下的分布(i)取单一奇偶性的值,(ii)关于 $0$ 对称,并且(iii)对每个 $k \ge 1$ 满足 $\Pr(d_T(v) \ge k) \le \text{forest\_carpool\_tail\_envelope}(k)$。未被触及的顶点具有集中在 $0$ 处的单点分布。

当一条边 $(u, v)$ 到达时,森林条件使得 $u$ 与 $v$ 位于前缀图的不同分支中。由引理 1,它们当前的偏差 $X$ 和 $Y$ 依赖于不相交的硬币集合,因此它们是独立的,并且新边的硬币与二者均独立。$u$ 的新偏差为贪心步:若 $X < Y$ 则 $Z = X + 1$,若 $X > Y$ 则 $Z = X - 1$,若 $X = Y$ 则由均匀硬币决定 $Z = X \pm 1$;对 $v$ 同理对称,而所有其他顶点保持其分布。因此,只需证明每当 $X$ 和 $Y$ 满足 (i)-(iii) 时,$Z$ 也满足 (i)-(iii)。奇偶性发生翻转。对称性通过同时取反 $X$、$Y$ 和硬币得出。对于尾部,$Z \ge k$ 迫使要么 $X \ge k + 1$,要么 $X \in \{k-1, k\}$ 且 $Y \ge X$,所以 $$\Pr(Z \ge k) \le \Pr(X \ge k+1) + \Pr(X \ge k-1)\,\Pr(Y \ge k-1).$$ 对于 $k \ge 4$,记 $f(k) = (1/2)^{\text{Fib}(k)}$ 并利用 $\text{Fib}(k+1) = \text{Fib}(k) + \text{Fib}(k-1)$, 可得 $f(k+1) + f(k-1)^2 = f(k)\,(2^{-\text{Fib}(k-1)} + 2^{-\text{Fib}(k-3)}) \le f(k)$,因此包络得以保持。层级 $k = 1, 2, 3$ 需要更精细的计数:由奇偶性可知 $X$ 在 $\{k-1, k\}$ 中的质量仅为一个单值,并且伙伴与硬币允许从层级 $j \ge 1$ 增加的概率至多为 $\max\bigl(\text{env}(j+1), (\text{env}(j) + \text{env}(j+2))/2\bigr)$,在 $j = 2$ 处该值为 $1/4$。结合包络值 $1/2$、$3/8$、$1/4$、$1/8$,这些情况也得以闭合。

我们现在逐步追踪 forest_carpool_maximum_fibonacci_tail 的 Lean 证明。

令 $T = \text{edges.length}$。对于每个索引 $j \in \text{Fin } T$、顶点 $w \in \text{Fin } n$ 以及符号 $sgn \in \text{Bool}$,我们定义事件 $\text{ev}(j, w, sgn) \subseteq (\text{Fin } T \to \text{Bool})$ 为 $$\text{ev}(j, w, sgn) = \left\{ r : \text{Fin } T \to \text{Bool} \;\middle|\; (D : \mathbb{Z}) \le (\text{if } sgn \text{ then } 1 \text{ else } -1) \cdot d_{j+1}(w) \right\},$$ 其中 $d_{j+1}(w)$ 表示在硬币序列 $r$ 下 $j+1$ 条边的前缀之后顶点 $w$ 的偏差,在 Lean 中通过前缀求值函数计算。

步骤 1:集合包含关系。 我们确立满足 $D \le \text{carpool\_max\_discrepancy } n \; \text{edges} \; (\dots)$ 的硬币赋值 $r$ 的集合是所有 $j \in \text{Fin } T$ 的四个端点事件的并集的子集: $$\bigcup_{j \in \text{Fin } T} \left( \text{ev}(j, (\text{edges}[j]).1, \text{true}) \cup \text{ev}(j, (\text{edges}[j]).1, \text{false}) \cup \text{ev}(j, (\text{edges}[j]).2, \text{true}) \cup \text{ev}(j, (\text{edges}[j]).2, \text{false}) \right).$$

为了证明这一包含关系,设 $r$ 满足前缀最大值条件。根据定义,carpool_max_discrepancy 从累加器 0 开始,在映射后的偏差上对二元最大值操作进行折叠。由于 $1 \le D$,最大值不可能等于初始累加器 0。因此,在扫描列表中存在索引 $i$ 满足 $i \le T$,使得 $\text{max\_vertex\_discrepancy } n \; d_i \ge D$。

根据 max_vertex_discrepancy 作为顶点上有限上确界的定义,存在顶点 $w \in \text{Fin } n$ 使得 $|d_i(w)|_{\mathbb{N}} \ge D$。因为 $D \ge 1$ 且 $d_0(w) = 0$,所以有 $i \ge 1$。形式化调用了最后触及(last-touch)性质,该性质确定了一个边索引 $j < i \le T$,使得 $w$ 是边 $j$ 的端点(即 $w = (\text{edges}[j]).1$ 或 $w = (\text{edges}[j]).2$),并且 $w$ 与在第 $j+1$ 步和第 $i$ 步之间到达的任何边均不关联。这意味着 $d_i(w) = d_{j+1}(w)$,从而 $|d_{j+1}(w)|_{\mathbb{N}} \ge D$。

在整数上,$|d_{j+1}(w)| \ge D$ 意味着要么 $d_{j+1}(w) \ge D$,要么 $-d_{j+1}(w) \ge D$。对 $w \in \{(\text{edges}[j]).1, (\text{edges}[j]).2\}$ 以及 $d_{j+1}(w)$ 的符号进行情况分析,可将 $r$ 置于边索引 $j$ 的并集中的四个集合之一,从而证明了该包含关系。

步骤 2:前缀概率界。 对于任意固定索引 $j \in \text{Fin } T$、任意端点 $w \in \{(\text{edges}[j]).1, (\text{edges}[j]).2\}$ 以及任意符号 $sgn \in \text{Bool}$,前 $j+1$ 条边的前缀序列本身就是一个无圈森林序列。将引理 2 应用于该前缀序列表明 $$\# \text{ev}(j, w, sgn) \le \text{forest\_carpool\_tail\_envelope}(D) \cdot 2^T.$$

利用对固定索引 $j$ 的四个事件基数的次可加性,我们得到 $$\# \left( \bigcup_{w \in \{e_j.1, e_j.2\}} \bigcup_{sgn \in \{\text{true}, \text{false}\}} \text{ev}(j, w, sgn) \right) \le 4 \cdot \left(\text{forest\_carpool\_tail\_envelope}(D) \cdot 2^T\right).$$

步骤 3:求和与结论。 应用步骤 1 的包含关系,随后在所有 $j \in \text{Fin } T$ 上应用联合界,满足前缀最大值条件的硬币向量的总基数以如下为界: $$\sum_{j \in \text{Fin } T} 4 \cdot \left(\text{forest\_carpool\_tail\_envelope}(D) \cdot 2^T\right) = T \cdot 4 \cdot \text{forest\_carpool\_tail\_envelope}(D) \cdot 2^T.$$

在正实数上两边同除以 $2^T$ 即得 $$\frac{\#\left\{ r \;\middle|\; D \le \text{carpool\_max\_discrepancy } n \; \text{edges} \; (\dots) \right\}}{2^T} \le 4 T \cdot \text{forest\_carpool\_tail\_envelope}(D),$$ 这便完成了 Lean 中的证明。

5. 讨论

定理 forest_carpool_maximum_fibonacci_tail 界定了随机贪心拼车在遗忘型森林到达序列上的行为。

该结果适用于所有有限顶点数 $n$、所有边序列长度 $T$ 以及所有偏差阈值 $D \ge 1$。到达序列假定为遗忘型森林序列:每条边连接不同顶点,没有无向边出现超过一次,且底层图无圈。敌手是遗忘型的,因为整个边序列是预先固定的,而算法的决策仅通过均匀决胜硬币进行随机化。

该结果不涵盖适应性敌手(adaptive adversary),在这种情况下边的到达可能依赖于算法先前的定向选择。它也不涵盖多重图序列,即同一对顶点之间的边可以重复到达,并且它也不直接适用于包含环路的图。

在针对遗忘型敌手的在线拼车这一更广泛的背景下(arXiv:2611.00388),一般边到达序列可能包含任意环路和边重复。对于一般序列,该论文提出的算法(非贪心算法)以高概率将最大偏差保持在 $O((\log T)^{1/3})$,且该阶无法被改进。

由于斐波那契数根据 $\text{Fib}(D) = \Theta(\phi^D)$ 指数增长(其中 $\phi = (1+\sqrt{5})/2 \approx 1.618$),尾部包络满足 $$\text{forest\_carpool\_tail\_envelope}(D) \le 2^{-\Theta(\phi^D)}.$$ 为了使总失败概率以任意期望的置信水平 $\epsilon > 0$ 为界,我们需要 $$4 T \cdot \text{forest\_carpool\_tail\_envelope}(D) \le \epsilon \iff 2^{\text{Fib}(D)} \ge \frac{4T}{\epsilon}.$$ 取两次对数表明,设定 $$D = O\left(\log \log T + \log \log\left(\frac{1}{\epsilon}\right)\right)$$ 即足以保证跨所有顶点的最大前缀偏差以至少 $1 - \epsilon$ 的概率保持在 $D$ 的界内。因此在森林上,即便简单的贪心规则也低于对一般序列而言最优的 $(\log T)^{1/3}$ 阶。

该包络在 $D = 2$ 处取值 $3/8$ 而非 $(1/2)^{\text{Fib}(2)} = 1/2$;在较小层级上的合并步骤针对这些值进行了验证,而对于 $D \ge 4$,仅凭斐波那契递推关系便已足够。

由该结果引申出若干自然的问题:

  • 推广到有界树宽与稀疏图:若底层图具有有界树宽、有界圈秩或是外平面图,随机贪心拼车在带环图上是否能达到 $O(\log \log T)$ 的偏差界?
  • 斐波那契包络的紧性:尾部包络 $(1/2)^{\text{Fib}(D)}$ 对树而言是否渐近紧致,或者能否通过考虑跨树分支的多步相关性进一步改进底数 $1/2$ 或指数增长率?
  • 森林上的适应性敌手:当敌手是适应性的(即根据当前顶点偏差选择下一条边)时,在森林边序列上可达到怎样的偏差界?

为什么是研究级成果

  • For every oblivious forest arrival sequence of T edges, randomized greedy carpooling has Pr(max over vertices and prefixes of |discrepancy| >= D) <= 4T * 2^(-Fib(D)) (3/8 in place of 1/2 at D = 2): a doubly exponential tail, so the maximum prefix discrepancy is O(log log T) with high probability. This answers OP-1106 affirmatively in substance, beyond the O((log T)^(1/3)) scale of arXiv:2611.00388 for general sequences

Lean 声明

  • forest_carpool_maximum_fibonacci_tailFor a forest arrival sequence, the probability that any vertex at any prefix has absolute discrepancy at least D is at most four times the…
  • carpool_stepIn online carpooling on n vertices, given an edge e joining two distinct vertices and an orientation bit b, the discrepancy vector d…
  • carpool_greedy_orientationsGiven a list of edges and a list of tie-breaking coins, randomized greedy carpooling orients each edge toward the endpoint with smaller…
  • max_vertex_discrepancyThe maximum absolute discrepancy among all vertices for an integer discrepancy vector d on n vertices.
  • carpool_max_discrepancyThe maximum discrepancy M_T over all time steps 0 ≤ t ≤ T of the maximum vertex discrepancy.
  • forest_carpool_final_discrepancyThe final discrepancy of a vertex after greedy orientation of the given edges with the given indexed tie-breaking coins.
  • forest_carpool_tail_envelopeThe proposed one-sided discrepancy tail envelope is 3/8 at level 2 and otherwise two to the negative Fibonacci number of the level.
  • forest_carpool_component_coin_localityTwo coin assignments that agree on every edge in the final connected component of a fixed vertex give the same final greedy discrepancy at…
  • forest_carpool_final_one_sided_fibonacci_tailFor any forest arrival sequence and any vertex, the finite uniform probability that its final greedy discrepancy is at least D is bounded…

Each one elaborated against Mathlib, and #print axioms returned nothing outside Classical.choice · Quot.sound · propext.

参考文献

  1. arXiv:2611.00388 — Online carpooling against an oblivious adversary

由 gemini-3.8-flash 根据知识库起草,经过检查并由 Claude Code 审阅英文版;中文版由模型翻译并对照英文检查。只有 Lean 部分经过验证,文字是对它的解读。