OctoInformBeta

OpenAI preprint, September 2026 · §5. Conditioned trees and uniform path sums · §5

Lemma 5.4 [Bounded path sums]: Mark noise and maximal deviations from spine-mean multiples of height at scale 2n+1\sqrt{2n+1} on conditioned Lukasiewicz tree codes of size 2n+12n+1

Uniform convergence in probability for bounded marked spine sums.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Take a critical Galton-Watson tree with an even offspring distribution conditioned, for a size parameter n≥0n \ge 0, to have N=2n+1N = 2n + 1 vertices, together with vertex marks drawn independently given the vertex degrees. Summing a bounded function of each ancestral step and its mark along the path from the root to a vertex yields a spine sum whose slope per unit height is governed by a stationary spine expectation. The question is how the maximal deviation across all vertices between this path sum and the corresponding multiple of vertex height behaves at scale N\sqrt{N} as n→∞n \to \infty.

Tree Codes and Conditioned Offspring Laws

Let N∈ℕN \in \mathbb{N}, and let d=(d0,…,dN−1)∈{0,…,N−1}Nd = (d_0, \dots, d_{N-1}) \in \{0, \dots, N-1\}^N be a finite degree sequence. For any step j∈ℕj \in \mathbb{N}, the degree sequence partial walk Wj(d)W_j(d) is given by (1): Wj(d)=∑0≤i<min⁡(j,N)(di−1).W_j(d) = \sum_{0 \le i < \min(j, N)} (d_i - 1).(1)✦ A discrete bridge sequence dd of length NN is a sequence in {0,…,N−1}N\{0, \dots, N-1\}^N satisfying WN(d)=−1W_N(d) = -1.✦ A sequence d∈{0,…,N−1}Nd \in \{0, \dots, N-1\}^N satisfies the valid tree code condition if WN(d)=−1W_N(d) = -1 and Wj(d)≥0W_j(d) \ge 0 for all j<Nj < N.✦ A Lukasiewicz tree code dd of length NN is a sequence in {0,…,N−1}N\{0, \dots, N-1\}^N satisfying WN(d)=−1W_N(d) = -1 and Wj(d)≥0W_j(d) \ge 0 for all j<Nj < N, and 𝒞N\mathcal{C}_N is the set of Lukasiewicz tree codes of length NN.✦ For any d∈{0,…,N−1}Nd \in \{0, \dots, N-1\}^N and j∈ℕj \in \mathbb{N}, the tree vertex height Hj(d)H_j(d) is the cardinality in (2): Hj(d)=#{k∈{0,…,N−1}:k<j and Wk(d)≤Wr(d) for all r∈{0,…,N} with k≤r≤j}.H_j(d) = \#\bigl\{k \in \{0, \dots, N-1\} : k < j \text{ and } W_k(d) \le W_r(d) \text{ for all } r \in \{0, \dots, N\} \text{ with } k \le r \le j\bigr\}.(2)✦

For N≥1N \ge 1 and an offset m∈{0,…,N−1}m \in \{0, \dots, N-1\}, the cyclic degree rotation σm\sigma_m sends d∈{0,…,N−1}Nd \in \{0, \dots, N-1\}^N to (d(i+m)mod⁡N)i=0N−1(d_{(i+m)\bmod N})_{i=0}^{N-1}✦, and the cyclic bridge rotation restricts σm\sigma_m to discrete bridge sequences of length NN.✦ For each discrete bridge sequence dd of positive length NN, the good rotation index m(d)∈{0,…,N−1}m(d) \in \{0, \dots, N-1\} is the unique cyclic shift index whose rotated bridge satisfies the valid tree code condition✦, and the canonical tree code σm(d)(d)∈𝒞N\sigma_{m(d)}(d) \in \mathcal{C}_N of dd is its cyclic degree rotation by m(d)m(d).✦

A critical even offspring distribution pp specifies a nonnegative mass function (p(k))k≥0(p(k))_{k \ge 0} on ℕ\mathbb{N} satisfying ∑k=0∞p(k)=1\sum_{k=0}^\infty p(k) = 1, p(k)=0p(k) = 0 for every odd kk, p(0)>0p(0) > 0, p(2)>0p(2) > 0, ∑k=0∞kp(k)=1\sum_{k=0}^\infty k\,p(k) = 1, and ∑k=0∞k2p(k)<∞\sum_{k=0}^\infty k^2 p(k) < \infty.✦ For a critical even offspring distribution pp and N∈ℕN \in \mathbb{N}, the independent and identically distributed (i.i.d.) offspring product measure ℙp⊗N\mathbb{P}_p^{\otimes N} of pp on ℕN\mathbb{N}^N is the NN-fold product measure of pp.✦ For N∈ℕN \in \mathbb{N} and a sequence d∈ℕNd \in \mathbb{N}^N, the total step Stot(d)S_{\mathrm{tot}}(d) of dd is ∑i=0N−1(di−1)\sum_{i=0}^{N-1} (d_i - 1).✦ For a size parameter n∈ℕn \in \mathbb{N}, the conditioned offspring bridge law ℙp,nbr\mathbb{P}_{p,n}^{\mathrm{br}} on ℕ2n+1\mathbb{N}^{2n+1} is the conditional distribution of ℙp⊗(2n+1)\mathbb{P}_p^{\otimes (2n+1)} given the event {d∈ℕ2n+1:Stot(d)=−1}\{d \in \mathbb{N}^{2n+1} : S_{\mathrm{tot}}(d) = -1\}.✦ Let ψn:ℕ2n+1→𝒞2n+1\psi_n : \mathbb{N}^{2n+1} \to \mathcal{C}_{2n+1} be the tree-code map from bridges on sequences of length 2n+12n+1; the conditioned tree code law ℙp,n\mathbb{P}_{p,n} on 𝒞2n+1\mathcal{C}_{2n+1} is the pushforward of ℙp,nbr\mathbb{P}_{p,n}^{\mathrm{br}} under ψn\psi_n.✦

The Offspring Spine Ladder Distribution

The infinite offspring product measure ℙp⊗ℕ\mathbb{P}_p^{\otimes \mathbb{N}} of pp on ℕℕ\mathbb{N}^{\mathbb{N}} is the countable product of copies of the offspring law of pp indexed by ℕ\mathbb{N}.✦ For a sequence x=(x0,x1,…)∈ℕℕx = (x_0, x_1, \dots) \in \mathbb{N}^{\mathbb{N}} and a step n∈ℕn \in \mathbb{N}, the offspring walk partial sum Sn(x)S_n(x) of xx at step nn is given by (3): Sn(x)=∑k=0n−1(xk−1).S_n(x) = \sum_{k=0}^{n-1} (x_k - 1).(3)✦ An index n∈ℕn \in \mathbb{N} satisfies the ladder epoch condition for xx if either Sn+1(x)≥0S_{n+1}(x) \ge 0, or Sm+1(x)<0S_{m+1}(x) < 0 for all m∈ℕm \in \mathbb{N} and n=0n = 0.✦ The first weak ladder epoch τ(x)∈ℕ\tau(x) \in \mathbb{N} of xx is the least index satisfying the ladder epoch condition for xx✦, and the weak ladder overshoot Δ(x)∈ℕ\Delta(x) \in \mathbb{N} of xx is max⁡(Sτ(x)+1(x),0)\max(S_{\tau(x)+1}(x), 0).✦ Together these form the spine ladder variable pair L(x)=(xτ(x),Δ(x))∈ℕ×ℕL(x) = (x_{\tau(x)}, \Delta(x)) \in \mathbb{N} \times \mathbb{N}✦, and the offspring spine ladder distribution νp\nu_p on ℕ×ℕ\mathbb{N} \times \mathbb{N} is the pushforward of ℙp⊗ℕ\mathbb{P}_p^{\otimes \mathbb{N}} under x↦L(x)x \mapsto L(x).✦

Spine Records and Marked Sums

For N∈ℕN \in \mathbb{N} and a sequence d∈ℕNd \in \mathbb{N}^N, the zero-extended sequence d̃∈ℕℕ\tilde{d} \in \mathbb{N}^{\mathbb{N}} is defined by d̃k=dk\tilde{d}_k = d_k for k<Nk < N and d̃k=0\tilde{d}_k = 0 for k≥Nk \ge N.✦ For v,k∈ℕv, k \in \mathbb{N}, the reversed prefix index ρv(k)\rho_v(k) is v−1−kv - 1 - k if k<vk < v and kk if k≥vk \ge v✦; for x∈ℕℕx \in \mathbb{N}^{\mathbb{N}} and v∈ℕv \in \mathbb{N}, the reversed prefix x(v)∈ℕℕx^{(v)} \in \mathbb{N}^{\mathbb{N}} of xx of length vv has entries xk(v)=xρv(k)x^{(v)}_k = x_{\rho_v(k)}.✦

For an integer sequence S:ℕ→ℤS : \mathbb{N} \to \mathbb{Z} and m∈ℕm \in \mathbb{N}, the running maximum Mm(S)M_m(S) of SS up to mm is max⁡0≤j≤mSj\max_{0 \le j \le m} S_j.✦ For a sequence S:ℕ→ΛS : \mathbb{N} \to \Lambda taking values in a linearly ordered set Λ\Lambda and n∈ℕn \in \mathbb{N}, the set ℛn(S)\mathcal{R}_n(S) of weak record times of SS up to nn is given by (4): ℛn(S)={k∈{1,…,n}:Sj≤Sk for all 0≤j≤k}.\mathcal{R}_n(S) = \{k \in \{1, \dots, n\} : S_j \le S_k \text{ for all } 0 \le j \le k\}.(4)✦ Writing u+=max⁡(u,0)u_+ = \max(u, 0), for a sequence x∈ℕℕx \in \mathbb{N}^{\mathbb{N}} and a step t∈ℕt \in \mathbb{N}, the record type θt(x)∈ℕ×ℕ\theta_t(x) \in \mathbb{N} \times \mathbb{N} of xx at step tt is defined in (5) by θt(x)=(x(t−1)+,(St(x)−M(t−1)+(S(x)))+)∈ℕ×ℕ.\theta_t(x) = \bigl(x_{(t-1)_+},\, \bigl(S_t(x) - M_{(t-1)_+}(S(x))\bigr)_+\bigr) \in \mathbb{N} \times \mathbb{N}.(5)✦ For a weight function f:ℕ×ℕ→ℝf : \mathbb{N} \times \mathbb{N} \to \mathbb{R}, a sequence x∈ℕℕx \in \mathbb{N}^{\mathbb{N}}, and a step bound v∈ℕv \in \mathbb{N}, the record spine sum Sfrec(x,v)S_f^{\mathrm{rec}}(x, v) is defined in (6) by Sfrec(x,v)=∑t∈ℛv(S(x))f(θt(x)).S_f^{\mathrm{rec}}(x, v) = \sum_{t \in \mathcal{R}_v(S(x))} f(\theta_t(x)).(6)✦ For N∈ℕN \in \mathbb{N}, a Lukasiewicz tree code d∈𝒞Nd \in \mathcal{C}_N, a weight function f:ℕ×ℕ→ℝf : \mathbb{N} \times \mathbb{N} \to \mathbb{R}, and a step bound v∈ℕv \in \mathbb{N}, the tree code spine sum Sfcode(d,v)S_f^{\mathrm{code}}(d, v) of ff is Sfrec(d̃(v),v)S_f^{\mathrm{rec}}(\tilde{d}^{(v)}, v).✦

For d∈𝒞Nd \in \mathcal{C}_N and v∈ℕv \in \mathbb{N}, the spine records of dd at vv are the elements t∈ℛv(S(d̃(v)))t \in \mathcal{R}_v(S(\tilde{d}^{(v)}))✦, and the spine record type of tt is θt(d̃(v))\theta_t(\tilde{d}^{(v)}).✦ When v≤Nv \le N, each spine record t∈ℛv(S(d̃(v)))t \in \mathcal{R}_v(S(\tilde{d}^{(v)})) determines the spine record vertex v−t∈{0,…,N−1}v - t \in \{0, \dots, N-1\}.✦ Given a mark set AA, a function b:(ℕ×ℕ)×A→ℝb : (\mathbb{N} \times \mathbb{N}) \times A \to \mathbb{R}, d∈𝒞Nd \in \mathcal{C}_N, v≤Nv \le N, and a mark assignment a∈ANa \in A^N, the marked spine sum Sbmark(d,v,a)S_b^{\mathrm{mark}}(d, v, a) is given by (7): Sbmark(d,v,a)=∑t∈ℛv(S(d̃(v)))b(θt(d̃(v)),av−t).S_b^{\mathrm{mark}}(d, v, a) = \sum_{t \in \mathcal{R}_v(S(\tilde{d}^{(v)}))} b\bigl(\theta_t(\tilde{d}^{(v)}),\, a_{v - t}\bigr).(7)✦

Let AA be a measurable space and let κ=(κk)k≥0\kappa = (\kappa_k)_{k \ge 0} be a family of probability measures on AA indexed by k∈ℕk \in \mathbb{N}. For N∈ℕN \in \mathbb{N} and a Lukasiewicz tree code d∈𝒞Nd \in \mathcal{C}_N, the conditional mark measure μd,κ\mu_{d,\kappa} on ANA^N is the product measure ⨂i=0N−1κdi\bigotimes_{i=0}^{N-1} \kappa_{d_i}✦, and the map d↦μd,κd \mapsto \mu_{d,\kappa} defines the tree code marking kernel Kκ,NK_{\kappa, N} from 𝒞N\mathcal{C}_N to ANA^N.✦ At size parameter n∈ℕn \in \mathbb{N}, the marked tree code law ℙp,κ,n\mathbb{P}_{p,\kappa,n} on 𝒞2n+1×A2n+1\mathcal{C}_{2n+1} \times A^{2n+1} is the joint distribution of the conditioned tree code law ℙp,n\mathbb{P}_{p,n} with the tree code marking kernel Kκ,2n+1K_{\kappa, 2n+1}.✦

The Claim

Theorem 1. Let (Ω,P)(\Omega, P) be a measurable space with a probability measure under which BB is a standard Brownian motion, let pp be a critical even offspring distribution, and let R>0R > 0 and ε>0\varepsilon > 0. For every function f:ℕ×ℕ→ℝf : \mathbb{N} \times \mathbb{N} \to \mathbb{R} satisfying |f(z)|≤R|f(z)| \le R for all z∈ℕ×ℕz \in \mathbb{N} \times \mathbb{N}, writing μp(f)=∫ℕ×ℕf(z)νp(dz)\mu_p(f) = \int_{\mathbb{N} \times \mathbb{N}} f(z)\,\nu_p(\mathrm{d}z), the tree code spine sum satisfies (8): limn→∞ℙp,n({d∈𝒞2n+1:max0≤v≤2n+1|Sfcode(d,v)−μp(f)Hv(d)|>ε2n+1})=0.\lim_{n \to \infty} \mathbb{P}_{p,n}\!\left(\left\{d \in \mathcal{C}_{2n+1} : \max_{0 \le v \le 2n+1} \bigl|S_f^{\mathrm{code}}(d, v) - \mu_p(f) H_v(d)\bigr| > \varepsilon\sqrt{2n+1}\right\}\right) = 0.(8)✦ Moreover, for every measurable space AA, every family κ=(κk)k≥0\kappa = (\kappa_k)_{k \ge 0} of probability measures on AA indexed by k∈ℕk \in \mathbb{N}, and every function b:(ℕ×ℕ)×A→ℝb : (\mathbb{N} \times \mathbb{N}) \times A \to \mathbb{R} such that a↦b(z,a)a \mapsto b(z, a) is measurable for each z∈ℕ×ℕz \in \mathbb{N} \times \mathbb{N} and |b(z,a)|≤R|b(z, a)| \le R for all z∈ℕ×ℕz \in \mathbb{N} \times \mathbb{N} and a∈Aa \in A, writing, for each z=(z1,z2)∈ℕ×ℕz = (z_1, z_2) \in \mathbb{N} \times \mathbb{N}, b‾(z)=∫Ab(z,a)κz1(da)\bar{b}(z) = \int_A b(z, a)\,\kappa_{z_1}(\mathrm{d}a), and writing μp,κ(b)=∫ℕ×ℕb‾(z)νp(dz)\mu_{p,\kappa}(b) = \int_{\mathbb{N} \times \mathbb{N}} \bar{b}(z)\,\nu_p(\mathrm{d}z), the marked spine sum satisfies (9) and the mark noise satisfies (10): limn→∞ℙp,κ,n({(d,a)∈𝒞2n+1×A2n+1:max0≤v≤2n+1|Sbmark(d,v,a)−μp,κ(b)Hv(d)|>ε2n+1})=0,\lim_{n \to \infty} \mathbb{P}_{p,\kappa,n}\!\left(\left\{(d, a) \in \mathcal{C}_{2n+1} \times A^{2n+1} : \max_{0 \le v \le 2n+1} \bigl|S_b^{\mathrm{mark}}(d, v, a) - \mu_{p,\kappa}(b) H_v(d)\bigr| > \varepsilon\sqrt{2n+1}\right\}\right) = 0,(9)✦ limn→∞ℙp,κ,n({(d,a)∈𝒞2n+1×A2n+1:max0≤v≤2n+1|Sbmark(d,v,a)−Sb‾code(d,v)|>ε2n+1})=0.\lim_{n \to \infty} \mathbb{P}_{p,\kappa,n}\!\left(\left\{(d, a) \in \mathcal{C}_{2n+1} \times A^{2n+1} : \max_{0 \le v \le 2n+1} \bigl|S_b^{\mathrm{mark}}(d, v, a) - S_{\bar{b}}^{\mathrm{code}}(d, v)\bigr| > \varepsilon\sqrt{2n+1}\right\}\right) = 0.(10)✦

In the paper, the result reads: for every fixed bounded measurable real label bb, max⁡v∈TN|Bb(v)−μbH(v)|=oP(N)\max_{v \in T_N} |B_b(v) - \mu_b H(v)| = o_P(\sqrt{N}), where N=2n+1N = 2n+1, and Sbmark(d,v,a)S_b^{\mathrm{mark}}(d, v, a), μp,κ(b)\mu_{p,\kappa}(b), and Hv(d)H_v(d) stand for Bb(v)B_b(v), μb\mu_b, and H(v)H(v). The theorem expresses this convergence in probability on conditioned Lukasiewicz tree codes of length N=2n+1N = 2n+1 through vanishing tail probabilities at threshold ε2n+1\varepsilon\sqrt{2n+1} for the unweighted spine sum in (8), the marked spine sum in (9), and the mark noise in (10).

What Is Checked

The claims are stated over a probability space (Ω,P)(\Omega, P) supporting a standard Brownian motion BB, a critical even offspring distribution pp, its conditioned tree code law ℙp,n\mathbb{P}_{p,n} on 𝒞2n+1\mathcal{C}_{2n+1}, its marked tree code law ℙp,κ,n\mathbb{P}_{p,\kappa,n} on 𝒞2n+1×A2n+1\mathcal{C}_{2n+1} \times A^{2n+1} built from a family κ\kappa of probability measures on a measurable space AA, the offspring spine ladder distribution νp\nu_p, the tree vertex height, the tree code spine sum, the marked spine sum, bounded weights ff and measurable mark weights bb bounded in absolute value by R>0R > 0, and a threshold ε>0\varepsilon > 0. For these constructions, the library proves that cyclic degree and bridge rotations act as permutations on {0,…,N−1}N\{0, \dots, N-1\}^N and on discrete bridge sequences of length N≥1N \ge 1, that a discrete bridge sequence of length N≥1N \ge 1 rotated by its good rotation index satisfies the valid tree code condition✦, and that every sequence in ℕℕ\mathbb{N}^{\mathbb{N}} admits an index satisfying the ladder epoch condition.✦