AFTD Auto-Formalizing Theoretical Domains

Research Blogs

Doubly Exponential Tail Bounds and Log-Log Discrepancy for Randomized Greedy Carpooling on Forest Edge Sequences

low tier2026-11-13reviewed by Claude Code中文版

Abstract

The online carpooling problem asks how to orient arriving edges between vertices to minimize the running vertex discrepancy, defined as the difference between indegree and outdegree. For arbitrary edge sequences fixed in advance, arXiv:2611.00388 gives a randomized algorithm with discrepancy $O((\log T)^{1/3})$, which matches a known lower bound. We ask how the simple randomized greedy algorithm behaves when the arriving edges form a forest, a question we pose here; the paper does not raise it. In this work, we analyze the performance of randomized greedy carpooling on oblivious forest arrival sequences. We show that for any sequence of $T$ edges whose underlying graph is acyclic, the probability that the maximum absolute discrepancy across all vertices and all prefix times exceeds an integer threshold $D \ge 1$ is bounded by $4 T \cdot \text{forest\_carpool\_tail\_envelope}(D)$, where the tail envelope equals $3/8$ for $D = 2$ and $(1/2)^{\text{Fib}(D)}$ for all other thresholds. Because the Fibonacci numbers grow exponentially, this tail bound is doubly exponential in $D$, establishing that the maximum prefix discrepancy is $O(\log \log T)$ with high probability. The proof shows that every vertex's discrepancy law stays symmetric, of fixed parity and below the envelope when two independent components are merged by an edge, and then reduces the prefix maximum to the $4T$ endpoint events at the arrival times of the edges. The entire development is formally verified in Lean 4.

1. Introduction

The online carpooling problem models fairness in repeated shared interactions over networks. In this framework, an adversary selects a sequence of edges over time on a vertex set $V = \{0, 1, \dots, n-1\}$. At each discrete time step $t \in \{0, \dots, T-1\}$, an undirected edge $\{u_t, v_t\}$ arrives online. An online algorithm must immediately and irrevocably orient this edge, deciding whether the edge is directed from $u_t$ to $v_t$ or from $v_t$ to $u_t$. The discrepancy of a vertex $v$ at time $t$ is the difference between its indegree and its outdegree up to time $t$. The algorithm aims to minimize the maximum absolute vertex discrepancy across all vertices and across all prefixes of the arrival sequence.

The study of online carpooling against an oblivious adversary was developed in arXiv:2611.00388. There the oblivious adversary chooses the whole sequence of edges in advance, and the paper gives a randomized algorithm, built on Gaussian domination rather than on greedy choices, whose maximum discrepancy is $O((\log T)^{1/3})$ with high probability on every such sequence. Since a lower bound of order $(\log T)^{1/3}$ holds for general sequences, that order is optimal; the hard instances repeat edges or close cycles.

A natural and lightweight strategy for online carpooling is the randomized greedy algorithm. When an edge $\{u, v\}$ arrives, the algorithm inspects the current discrepancies of the two endpoints. If one endpoint has a strictly lower discrepancy than the other, the algorithm orients the edge toward that endpoint (increasing its discrepancy by 1 and decreasing the other endpoint's discrepancy by 1), thereby driving their discrepancies closer together. If the two endpoints have equal discrepancies, the algorithm breaks the tie by flipping an unbiased coin.

We pose the following question, which the paper does not ask: what discrepancy does randomized greedy guarantee when the arrival sequence is a forest, that is, when no edge is repeated and the edges form an acyclic graph? On a forest every arriving edge joins two different components, so the discrepancies of its two endpoints depend on disjoint sets of coins.

We show that for every oblivious forest arrival sequence of $T$ edges on $n$ vertices, randomized greedy carpooling achieves a doubly exponential tail bound on the maximum prefix discrepancy. Specifically, for any integer threshold $D \ge 1$, the probability that the maximum absolute discrepancy across all vertices and all prefix times $0 \le t \le T$ is at least $D$ satisfies $$\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),$$ where $\text{forest\_carpool\_tail\_envelope}(D)$ is defined to be $3/8$ for $D = 2$, and $(1/2)^{\text{Fib}(D)}$ for all other values of $D$.

Because the Fibonacci numbers grow exponentially with base $\phi = (1+\sqrt{5})/2 \approx 1.618$, the tail envelope $(1/2)^{\text{Fib}(D)}$ decreases doubly exponentially in $D$. Consequently, to ensure that the probability of exceeding threshold $D$ is at most a given error $\epsilon > 0$, it suffices to choose $D$ such that $\text{Fib}(D) \ge \log_2(4T/\epsilon)$. This demonstrates that the maximum discrepancy across the entire trajectory remains bounded by $O(\log \log T)$ with high probability. On forests this is below the order $(\log T)^{1/3}$ that is optimal for general sequences.

The remainder of this post is structured as follows. We formalize the carpooling setting and definitions in Lean 4, state the main theorem (forest_carpool_maximum_fibonacci_tail), present the complete mathematical proof along with its formalization details, and discuss connections to related open questions.

2. Preliminaries

We formalize the online carpooling model on a finite vertex set $\text{Fin } n = \{0, 1, \dots, n-1\}$.

Definition 1 (ValidCarpoolEdgeSequence). A list of directed edge pairs $\text{edges} : \text{List } (\text{Fin } n \times \text{Fin } n)$ is valid for online carpooling on $n$ vertices if every arriving edge connects two distinct vertices, that is, $$\forall e \in \text{edges}, \quad e.1 \ne e.2.$$ Remark: This condition excludes self-loops, but permits edges to be ordered in any arbitrary arrival sequence.

Definition 2 (CarpoolForestEdgeSequence). A list of edges $\text{edges} : \text{List } (\text{Fin } n \times \text{Fin } n)$ is an oblivious forest edge sequence on $n$ vertices if it satisfies three conditions: 1. It is a valid carpool edge sequence (ValidCarpoolEdgeSequence). 2. The undirected edges are pairwise distinct, that is, the list of unordered pairs $s(e.1, e.2) = \{e.1, e.2\}$ contains no duplicate entries. 3. The undirected simple graph formed by the edge set $\{ \{e.1, e.2\} \mid e \in \text{edges} \}$ is acyclic. Remark: In Lean 4, this graph is constructed using the undirected edge set with unordered pairs. The condition ensures both that no undirected edge appears more than once and that the resulting graph is a forest.

Definition 3 (carpool_step). Given an integer discrepancy vector $d : \text{Fin } n \to \mathbb{Z}$, an edge $e = (u, v) \in \text{Fin } n \times \text{Fin } n$, and an orientation boolean $b \in \text{Bool}$, the single-step discrepancy update $\text{carpool\_step } n \; d \; e \; b : \text{Fin } n \to \mathbb{Z}$ is defined at each vertex $w \in \text{Fin } n$ by $$(\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).$$ Remark: When $b = \text{true}$, the edge is oriented toward $u$, adding $+1$ to $d(u)$ and $-1$ to $d(v)$. When $b = \text{false}$, the edge is oriented toward $v$, adding $-1$ to $d(u)$ and $+1$ to $d(v)$. Uninvolved vertices remain unchanged.

Definition 4 (carpool_greedy_orientations). Given a list of edges $\text{edges}$ and a list of boolean coins $\text{coins}$, the function $\text{carpool\_greedy\_orientations } n \; \text{edges} \; \text{coins} : \text{List Bool}$ computes the orientation choices of randomized greedy carpooling starting from initial zero discrepancies $d_0(w) = 0$ for all $w$. At each step, given current discrepancy $d$, arriving edge $e = (u, v)$, and tie-breaking coin $c$, the orientation bit $b$ is selected as $$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}$$ The algorithm appends $b$ and recurses on the subsequent edges and coins using the updated discrepancy vector $\text{carpool\_step } n \; d \; e \; b$. Remark: If either list is empty, the recursion yields the empty list. When supplied with coins from a function $r : \text{Fin } T \to \text{Bool}$ via the function list conversion, the lists have identical length $T = \text{edges.length}$.

Definition 5 (max_vertex_discrepancy). For an integer discrepancy vector $d : \text{Fin } n \to \mathbb{Z}$, its maximum absolute vertex discrepancy is defined by $$\text{max\_vertex\_discrepancy } n \; d = \sup_{v \in \text{Fin } n} |d(v)|_{\mathbb{N}}.$$ Remark: The supremum is taken over the finite universe of vertices, producing a natural number.

Definition 6 (carpool_max_discrepancy). Given edges $\text{edges}$ and orientation bits $\text{signs}$, let the intermediate discrepancies denote the list of intermediate discrepancy vectors $d_0, d_1, \dots, d_T$ obtained by iteratively applying carpool_step starting from $d_0 = \lambda v.\, 0$. The maximum prefix discrepancy is defined by $$\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)).$$ Remark: This computes the maximum of $|d_t(w)|_{\mathbb{N}}$ over all time steps $0 \le t \le T$ and all vertices $w$. For an empty edge list, it evaluates to 0.

Definition 7 (forest_carpool_final_discrepancy). Given edges $\text{edges}$, a coin assignment $r : \text{Fin } T \to \text{Bool}$, and a vertex $v \in \text{Fin } n$, the final discrepancy of $v$ is defined by $$\text{forest\_carpool\_final\_discrepancy } n \; \text{edges} \; r \; v = d_T(v),$$ which is the value of the final discrepancy vector at vertex $v$ after greedy orientation with coins $r$.

Definition 8 (forest_carpool_tail_envelope). The one-sided discrepancy tail envelope function $\text{forest\_carpool\_tail\_envelope} : \mathbb{N} \to \mathbb{R}$ is defined by $$\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}$$ where $\text{Fib}(k)$ is the $k$-th Fibonacci number, with $\text{Fib}(0) = 0, \text{Fib}(1) = 1, \text{Fib}(2) = 1, \text{Fib}(3) = 2, \text{Fib}(4) = 3, \dots$. Remark: At $k = 2$, the standard Fibonacci power $(1/2)^{\text{Fib}(2)} = 1/2$ is replaced by the strictly tighter value $3/8$. For $k = 1$, the envelope equals $(1/2)^1 = 1/2$.

3. Main result

The main theorem established in this work is forest_carpool_maximum_fibonacci_tail, which provides a doubly exponential upper bound on the tail probability of the maximum prefix discrepancy for randomized greedy carpooling on forest edge sequences.

Theorem (forest_carpool_maximum_fibonacci_tail). Let $n \in \mathbb{N}$, and let $\text{edges}$ be a list of edges of length $T = \text{edges.length}$ on vertices $\text{Fin } n$ satisfying the acyclic forest condition CarpoolForestEdgeSequence. Let $D \in \mathbb{N}$ be an integer discrepancy threshold satisfying $1 \le D$. When tie-breaking coins are chosen independently and uniformly at random from $\{\text{true}, \text{false}\}$, the probability that the maximum prefix discrepancy across all vertices and all time steps reaches or exceeds $D$ satisfies $$\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).$$

The Lean statement of forest_carpool_maximum_fibonacci_tail directly translates this inequality by filtering the finite universe of coin assignments $r : \text{Fin } T \to \text{Bool}$ on the universal finset, casting the resulting cardinality to the real numbers, dividing by the real quantity $2^{\text{edges.length}}$, and bounding the ratio by $4 \cdot \text{edges.length} \cdot \text{forest\_carpool\_tail\_envelope } D$ under the explicit hypothesis $1 \le D$.

This main theorem builds on two structural results that describe the behavior of randomized greedy carpooling on acyclic topologies:

1. Spatial Locality (forest_carpool_component_coin_locality): For any vertex $v \in \text{Fin } n$, the final discrepancy of $v$ depends exclusively on the coin assignments of edges in the connected component of $v$. If two coin assignments $r, s : \text{Fin } T \to \text{Bool}$ agree on every edge reachable from $v$ in the undirected graph formed by $\text{edges}$, then $$\text{forest\_carpool\_final\_discrepancy } n \; \text{edges} \; r \; v = \text{forest\_carpool\_final\_discrepancy } n \; \text{edges} \; s \; v.$$ This locality guarantees that coin flips on disconnected components do not interfere with the trajectory of $v$, ensuring statistical independence between separate subtrees.

2. One-Sided Vertex Tail (forest_carpool_final_one_sided_fibonacci_tail): For any forest arrival sequence and any vertex $v \in \text{Fin } n$, the uniform probability that the final discrepancy of $v$ is at least $D$ is bounded by the Fibonacci tail envelope: $$\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).$$ By symmetry between the orientation choices $+1$ and $-1$, the identical bound holds for the lower tail event $d_T(v) \le -D$.

The main theorem demonstrates that although the prefix maximum involves taking a supremum over all $n$ vertices and all $T+1$ intermediate time steps, the underlying forest structure allows the global maximum to be controlled by a union of only $4T$ one-sided vertex events, incurring only a linear loss factor of $4T$ against the doubly exponential decay of forest_carpool_tail_envelope.

Theorem forest_carpool_maximum_fibonacci_tail (Lean 4, verified)
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. Proof

We organize the proof into three parts: the high-level geometric idea, the two supporting lemmas on acyclic graphs, and the step-by-step verification combining them into the final bound.

The primary challenge in bounding the maximum prefix discrepancy is that the supremum is taken over all $n$ vertices and all intermediate time steps $0 \le t \le T$. A union bound over all vertices and all prefixes would incur a factor of $n(T+1)$. However, in online carpooling, the discrepancy of a vertex changes if and only if an edge incident to that vertex arrives.

For any coin sequence $r$, if the maximum prefix discrepancy is at least $D \ge 1$, there must exist an intermediate step $i \le T$ and a vertex $w$ such that $|d_i(w)| \ge D$. Because all discrepancies start at 0 and $D \ge 1$, this cannot occur at step 0. Thus $w$ must have been touched by at least one arriving edge prior to step $i$. Let $j < i$ be the index of the latest edge among the initial $i$ edges that is incident to $w$. Because no edges incident to $w$ arrive between time step $j+1$ and time step $i$, the discrepancy of $w$ remains entirely constant across that interval, so $d_i(w) = d_{j+1}(w)$.

Furthermore, since edge $j$ touches $w$, vertex $w$ must be one of the two endpoints of edge $j$, namely $(\text{edges}[j]).1$ or $(\text{edges}[j]).2$. Consequently, any violation of threshold $D$ anywhere along the trajectory corresponds to a violation at step $j+1$ at one of the two endpoints of edge $j$, either in the positive direction or in the negative direction. There are exactly $4$ such endpoint-sign combinations for each edge index $j \in \{0, \dots, T-1\}$, yielding a total of $4T$ elementary events. Because each prefix of a forest sequence is itself a forest sequence, each elementary event is bounded by $\text{forest\_carpool\_tail\_envelope}(D)$ via the one-sided vertex tail bound.

Lemma 1 (forest_carpool_component_coin_locality). Let $n \in \mathbb{N}$, and let $\text{edges}$ be an edge sequence of length $T$. Let $v \in \text{Fin } n$, and let $r, s : \text{Fin } T \to \text{Bool}$ be two coin assignments. If $r(i) = s(i)$ for every index $i \in \text{Fin } T$ such that the endpoint $(\text{edges}[i]).1$ is reachable from $v$ in the simple graph formed by the edges, then $$\text{forest\_carpool\_final\_discrepancy } n \; \text{edges} \; r \; v = \text{forest\_carpool\_final\_discrepancy } n \; \text{edges} \; s \; v.$$

Proof of Lemma 1. In online carpooling, the state update carpool_step modifies the discrepancy values only at the two endpoints of the arriving edge. In the greedy algorithm, the choice of orientation depends only on the relative order of the discrepancies of those two endpoints, and on the coin assigned to that edge in case of equality. On a simple graph, two vertices belong to the same connected component if and only if they are reachable from each other. When an edge arrives, either both endpoints belong to the same connected component or they belong to two previously disjoint components that are merged by the edge. By induction on the prefix length of the edge sequence, the discrepancy vector restricted to the vertices in $v$'s connected component is completely determined by the edges within that component and their associated coins. Coins on edges outside this component have no influence on the discrepancies of vertices in $v$'s component. Lean establishes this structural invariance by induction on the edge list.

Lemma 2 (forest_carpool_final_one_sided_fibonacci_tail). Let $n \in \mathbb{N}$, and let $\text{edges}$ be a carpool forest edge sequence (CarpoolForestEdgeSequence). Let $v \in \text{Fin } n$ and let $D \in \mathbb{N}$ satisfy $1 \le D$. Then $$\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).$$

Proof of Lemma 2. Lean proves a stronger invariant by induction on the edge list: for every vertex $v$, the law of $d_T(v)$ under uniform coins (i) takes values of a single parity, (ii) is symmetric about $0$, and (iii) satisfies $\Pr(d_T(v) \ge k) \le \text{forest\_carpool\_tail\_envelope}(k)$ for every $k \ge 1$. An untouched vertex has the point law at $0$.

When an edge $(u, v)$ arrives, the forest condition places $u$ and $v$ in different components of the prefix graph. By Lemma 1 their current discrepancies $X$ and $Y$ depend on disjoint sets of coins, so they are independent, and the coin of the new edge is independent of both. The new discrepancy of $u$ is the greedy step $Z = X + 1$ if $X < Y$, $Z = X - 1$ if $X > Y$, and $Z = X \pm 1$ by the fair coin if $X = Y$; symmetrically for $v$, and all other vertices keep their laws. So it suffices to show that $Z$ satisfies (i)-(iii) whenever $X$ and $Y$ do. Parity flips. Symmetry follows by negating $X$, $Y$ and the coin together. For the tail, $Z \ge k$ forces either $X \ge k + 1$, or $X \in \{k-1, k\}$ and $Y \ge X$, so $$\Pr(Z \ge k) \le \Pr(X \ge k+1) + \Pr(X \ge k-1)\,\Pr(Y \ge k-1).$$ For $k \ge 4$, writing $f(k) = (1/2)^{\text{Fib}(k)}$ and using $\text{Fib}(k+1) = \text{Fib}(k) + \text{Fib}(k-1)$, one has $f(k+1) + f(k-1)^2 = f(k)\,(2^{-\text{Fib}(k-1)} + 2^{-\text{Fib}(k-3)}) \le f(k)$, so the envelope is preserved. The levels $k = 1, 2, 3$ need a finer count: the mass of $X$ in $\{k-1, k\}$ is a single value by parity, and the probability that the partner and the coin allow an increase from a level $j \ge 1$ is at most $\max\bigl(\text{env}(j+1), (\text{env}(j) + \text{env}(j+2))/2\bigr)$, which is $1/4$ at $j = 2$. With the envelope values $1/2$, $3/8$, $1/4$, $1/8$ these cases close as well.

We now follow the Lean proof of forest_carpool_maximum_fibonacci_tail step by step.

Let $T = \text{edges.length}$. For each index $j \in \text{Fin } T$, vertex $w \in \text{Fin } n$, and sign $sgn \in \text{Bool}$, we define the event $\text{ev}(j, w, sgn) \subseteq (\text{Fin } T \to \text{Bool})$ by $$\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\},$$ where $d_{j+1}(w)$ denotes the discrepancy of vertex $w$ after the prefix of $j+1$ edges under coin sequence $r$, computed in Lean via the prefix evaluation function.

Step 1: Set inclusion. We establish that the set of coin assignments $r$ satisfying $D \le \text{carpool\_max\_discrepancy } n \; \text{edges} \; (\dots)$ is a subset of the union over all $j \in \text{Fin } T$ of the four endpoint events: $$\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).$$

To prove this inclusion, let $r$ satisfy the prefix maximum condition. By definition, carpool_max_discrepancy folds the binary maximum operation over the mapped discrepancies starting from accumulator 0. Since $1 \le D$, the maximum cannot equal the initial accumulator 0. Therefore, there exists an index $i$ in the scanned list with $i \le T$ such that $\text{max\_vertex\_discrepancy } n \; d_i \ge D$.

By definition of max_vertex_discrepancy as a finite supremum over vertices, there exists a vertex $w \in \text{Fin } n$ such that $|d_i(w)|_{\mathbb{N}} \ge D$. Because $D \ge 1$ and $d_0(w) = 0$, we have $i \ge 1$. The formalization invokes the last-touch property, which identifies an edge index $j < i \le T$ such that $w$ is an endpoint of edge $j$ (so $w = (\text{edges}[j]).1$ or $w = (\text{edges}[j]).2$) and $w$ is not incident to any edge arriving between step $j+1$ and step $i$. This implies $d_i(w) = d_{j+1}(w)$, so $|d_{j+1}(w)|_{\mathbb{N}} \ge D$.

Over the integers, $|d_{j+1}(w)| \ge D$ implies that either $d_{j+1}(w) \ge D$ or $-d_{j+1}(w) \ge D$. Case analysis on $w \in \{(\text{edges}[j]).1, (\text{edges}[j]).2\}$ and the sign of $d_{j+1}(w)$ places $r$ in one of the four sets in the union for edge index $j$, proving the inclusion.

Step 2: Prefix probability bound. For any fixed index $j \in \text{Fin } T$, any endpoint $w \in \{(\text{edges}[j]).1, (\text{edges}[j]).2\}$, and any sign $sgn \in \text{Bool}$, the prefix sequence of the initial $j+1$ edges is itself an acyclic forest sequence. Applying Lemma 2 to this prefix sequence shows that $$\# \text{ev}(j, w, sgn) \le \text{forest\_carpool\_tail\_envelope}(D) \cdot 2^T.$$

Applying the subadditivity of cardinality across the four events for a fixed index $j$, we obtain $$\# \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).$$

Step 3: Summation and conclusion. Applying the inclusion from Step 1, followed by the union bound across all $j \in \text{Fin } T$, the total cardinality of coin vectors satisfying the prefix maximum condition is bounded by $$\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.$$

Dividing both sides by $2^T$ over the positive real numbers yields $$\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),$$ which completes the proof in Lean.

5. Discussion

The theorem forest_carpool_maximum_fibonacci_tail bounds the behavior of randomized greedy carpooling on oblivious forest arrival sequences.

The result applies to all finite vertex counts $n$, all edge sequence lengths $T$, and all discrepancy thresholds $D \ge 1$. The arrival sequence is assumed to be an oblivious forest sequence: every edge joins distinct vertices, no undirected edge appears more than once, and the underlying graph has no cycles. The adversary is oblivious because the entire sequence of edges is fixed in advance, and the algorithm's decisions are randomized solely through the unbiased tie-breaking coins.

The result does not cover adaptive adversaries, where the arrival of edges may depend on the algorithm's previous orientation choices. It also does not cover multigraph sequences, where an edge between the same pair of vertices can arrive repeatedly, nor does it apply directly to graphs containing cycles.

In the broader context of online carpooling against an oblivious adversary (arXiv:2611.00388), general edge arrival sequences may contain arbitrary cycles and edge repetitions. For general sequences the paper's algorithm, which is not greedy, keeps the maximum discrepancy $O((\log T)^{1/3})$ with high probability, and this order cannot be improved.

Because the Fibonacci numbers grow exponentially according to $\text{Fib}(D) = \Theta(\phi^D)$ where $\phi = (1+\sqrt{5})/2 \approx 1.618$, the tail envelope satisfies $$\text{forest\_carpool\_tail\_envelope}(D) \le 2^{-\Theta(\phi^D)}.$$ To bound the overall failure probability by any desired confidence level $\epsilon > 0$, we require $$4 T \cdot \text{forest\_carpool\_tail\_envelope}(D) \le \epsilon \iff 2^{\text{Fib}(D)} \ge \frac{4T}{\epsilon}.$$ Taking logarithms twice shows that setting $$D = O\left(\log \log T + \log \log\left(\frac{1}{\epsilon}\right)\right)$$ suffices to guarantee that the maximum prefix discrepancy across all vertices remains bounded by $D$ with probability at least $1 - \epsilon$. So on forests even the simple greedy rule stays below the order $(\log T)^{1/3}$ that is optimal for general sequences.

The envelope takes the value $3/8$ at $D = 2$ rather than $(1/2)^{\text{Fib}(2)} = 1/2$; the merge step at the small levels is checked against these values, and for $D \ge 4$ the Fibonacci recurrence alone suffices.

Several natural questions are suggested by this result:

  • Extension to bounded treewidth and sparse graphs: Does randomized greedy carpooling achieve an $O(\log \log T)$ discrepancy bound on graphs with cycles if the underlying graph has bounded treewidth, bounded cycle rank, or is outerplanar?
  • Tightness of the Fibonacci envelope: Is the tail envelope $(1/2)^{\text{Fib}(D)}$ asymptotically tight for trees, or can the base $1/2$ or the exponent growth rate be further improved by considering multi-step correlations across tree branches?
  • Adaptive adversaries on forests: What discrepancy bound is achievable on forest edge sequences when the adversary is adaptive, choosing the next edge based on current vertex discrepancies?

Why it is research-level

  • 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 declarations

  • 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.

References

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

Drafted by gemini-3.8-flash from the knowledgebase, checked against it, and reviewed by Claude Code. Only the Lean is verified; the prose is a reading of it.