OctoInformBeta

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

Theorem 5.5 [Uniform marked path sums]: For N=2n+1N=2n+1 with Brownian motion, spine tail integrals approach 00 and uniform height errors above εN\varepsilon\sqrt{N} vanish in probability, including core marks

Degree-bounded spine sums concentrate in critical even conditioned trees.

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

In the planar map model decorated by Fortuin-Kasteleyn (FK) percolation with parameter p∈(1/2,1)p \in (1/2, 1), large finite maps decompose along a critical Galton-Watson tree conditioned to have N=2n+1N = 2n+1 vertices, where each vertex carries a core block contributing to graph distances. Moving from the root to a vertex vv traverses an ancestral spine whose steps correspond to weak ascending ladder records of the reversed Lukasiewicz exploration walk, recording both the ancestor’s offspring degree and its overshoot.

When each spine step receives a real-valued mark bounded in magnitude by the ancestor’s offspring degree, summing those marks along the spine yields an ancestral path sum. Under only a finite second moment for the offspring distribution, do these marked spine sums stay within εN\varepsilon\sqrt{N} of a constant multiple of the vertex height simultaneously across all NN vertices with probability tending to 11 for every ε>0\varepsilon > 0, both for general degree-bounded marks and for the core metric increments of the FK inventory model?

Conditioned Trees and Marked Spine Sums

A critical even offspring distribution π=(πk)k≥0\pi = (\pi_k)_{k \ge 0} is a probability distribution on ℕ\mathbb{N} such that πk=0\pi_k = 0 for every odd kk, π0>0\pi_0 > 0, π2>0\pi_2 > 0, ∑k=0∞kπk=1\sum_{k=0}^{\infty} k \pi_k = 1, and ∑k=0∞k2πk<∞\sum_{k=0}^{\infty} k^2 \pi_k < \infty.✦ A block offspring probability weight sequence η=(ηm)m≥0\eta = (\eta_m)_{m \ge 0} is a sequence of nonnegative real numbers satisfying ∑m=0∞ηm=1\sum_{m=0}^{\infty} \eta_m = 1✦, and the doubled block mass sequence η̃\tilde{\eta} of η\eta is the sequence on ℕ\mathbb{N} that assigns ηk/2\eta_{k/2} when kk is even and 00 when kk is odd. Whenever η\eta satisfies η0>0\eta_0 > 0, η1>0\eta_1 > 0, ∑m=0∞mηm=1/2\sum_{m=0}^{\infty} m \eta_m = 1/2, and ∑m=0∞m2ηm<∞\sum_{m=0}^{\infty} m^2 \eta_m < \infty, its doubled sequence η̃\tilde{\eta} defines a critical even offspring distribution.✦

For a natural number NN, a degree sequence d:{0,…,N−1}→{0,…,N−1}d : \{0, \dots, N-1\} \to \{0, \dots, N-1\}, and a step j∈ℕj \in \mathbb{N}, the degree sequence partial walk is Wj(d)=∑0≤i<Ni<j(di−1).W_j(d) = \sum_{\substack{0 \le i < N \\ i < j}} (d_i - 1).(1)✦ A discrete bridge sequence dd of length NN is a degree sequence in {0,…,N−1}N\{0, \dots, N-1\}^N whose partial walk (1) satisfies WN(d)=−1W_N(d) = -1, and a Lukasiewicz tree code dd of length NN is a discrete bridge sequence of length NN such that Wj(d)≥0W_j(d) \ge 0 for all j<Nj < N. The tree vertex height Hj(d)H_j(d) of a degree sequence dd of length NN at step j∈ℕj \in \mathbb{N} is the number of indices k∈{0,…,N−1}k \in \{0, \dots, N-1\} with k<jk < j such that Wk(d)≤Wr(d)W_k(d) \le W_r(d) for every r∈{0,…,N}r \in \{0, \dots, N\} satisfying k≤r≤jk \le r \le j.✦

When N>0N > 0, cyclically rotating a degree sequence or discrete bridge sequence dd of length NN by an offset m∈{0,…,N−1}m \in \{0, \dots, N-1\} produces the sequence i↦di+mmod⁡Ni \mapsto d_{i+m \bmod N}; the good rotation index m*(d)∈{0,…,N−1}m^*(d) \in \{0, \dots, N-1\} of a bridge dd is the unique cyclic shift index turning dd into a valid tree code, and the canonical tree code of dd is the bridge obtained by rotating dd by m*(d)m^*(d). The total step of an integer sequence d∈ℕNd \in \mathbb{N}^N is the integer ∑i=0N−1(di−1)\sum_{i=0}^{N-1} (d_i - 1).✦ Under a critical even offspring distribution π\pi, the offspring product measure π⊗N\pi^{\otimes N} on ℕN\mathbb{N}^N governs NN independent draws from π\pi✦, and conditioning π⊗(2n+1)\pi^{\otimes(2n+1)} on having total step −1-1 yields the conditioned offspring bridge law ℙnπ,br\mathbb{P}_n^{\pi,\mathrm{br}}✦; pushing ℙnπ,br\mathbb{P}_n^{\pi,\mathrm{br}} forward under the tree code map from integer sequences of length 2n+12n+1 to Lukasiewicz tree codes of length 2n+12n+1 gives the conditioned tree code law ℙnπ\mathbb{P}_n^{\pi}.✦

Given a measurable mark space AA and a family of probability measures κ=(κk)k≥0\kappa = (\kappa_k)_{k \ge 0} on AA, the conditional mark measure on a Lukasiewicz tree code dd of length NN is the product measure ⨂i=0N−1κdi\bigotimes_{i=0}^{N-1} \kappa_{d_i} on ANA^N, forming the tree code marking kernel from tree codes of length NN to ANA^N. Combining the conditioned tree code law ℙnπ\mathbb{P}_n^{\pi} with this marking kernel of length 2n+12n+1 defines the marked tree code law ℙnπ,κ\mathbb{P}_n^{\pi,\kappa} on pairs (d,𝒂)(d, \mathbf{a}) of a tree code dd of length 2n+12n+1 and a vertex marking 𝒂=(a0,…,a2n)∈A2n+1\mathbf{a} = (a_0, \dots, a_{2n}) \in A^{2n+1}.✦

The offspring walk partial sum Sn(x)S_n(x) of a stream x:ℕ→ℕx : \mathbb{N} \to \mathbb{N} at time n∈ℕn \in \mathbb{N} is the integer ∑k=0n−1(xk−1)\sum_{k=0}^{n-1} (x_k - 1), and the running maximum MN(S)M_N(S) of an integer sequence S:ℕ→ℤS : \mathbb{N} \to \mathbb{Z} up to N∈ℕN \in \mathbb{N} is the integer max⁡0≤k≤NSk\max_{0 \le k \le N} S_k. The weak record times up to nn of SS form the set Recn(S)={k∈{1,…,n}:Sj≤Sk for all 0≤j≤k}\mathrm{Rec}_n(S) = \{k \in \{1, \dots, n\} : S_j \le S_k \text{ for all } 0 \le j \le k\}✦, and the record type at step s∈ℕs \in \mathbb{N} for xx is (xmax⁡(s−1,0),(Ss(x)−Mmax⁡(s−1,0)(S(x)))+)(x_{\max(s-1,0)}, (S_s(x) - M_{\max(s-1,0)}(S(x)))_+).✦ Extending a tree code dd of length NN by zeros for indices k≥Nk \ge N gives a stream d̃:ℕ→ℕ\tilde{d} : \mathbb{N} \to \mathbb{N}, whose reversed prefix of length v∈ℕv \in \mathbb{N} is the stream d̃(v)\tilde{d}^{(v)} taking d̃v−1−k\tilde{d}_{v-1-k} for k<vk < v and d̃k\tilde{d}_k for k≥vk \ge v. The spine records ℛv(d)\mathcal{R}_v(d) of dd at step v≤Nv \le N are the weak record times Recv(S(d̃(v)))\mathrm{Rec}_v(S(\tilde{d}^{(v)}))✦; each record s∈ℛv(d)s \in \mathcal{R}_v(d) determines the spine record type ζ(d,v,s)\zeta(d, v, s) as the record type of d̃(v)\tilde{d}^{(v)} at step ss, together with the spine record vertex v−s∈{0,…,N−1}v - s \in \{0, \dots, N-1\}. Given a mark label b:(ℕ×ℕ)×A→ℝb : (\mathbb{N} \times \mathbb{N}) \times A \to \mathbb{R} and a marking 𝒂∈AN\mathbf{a} \in A^N, the marked spine sum at step v≤Nv \le N is Bb(d,v,𝒂)=∑s∈ℛv(d)b(ζ(d,v,s),av−s).B_b(d, v, \mathbf{a}) = \sum_{s \in \mathcal{R}_v(d)} b\bigl(\zeta(d, v, s),\, a_{v-s}\bigr).(2)✦

Under a critical even offspring distribution π\pi, the infinite offspring product measure π⊗ℕ\pi^{\otimes \mathbb{N}} governs streams x:ℕ→ℕx : \mathbb{N} \to \mathbb{N}.✦ A step n∈ℕn \in \mathbb{N} satisfies the ladder epoch condition for xx if Sn+1(x)≥0S_{n+1}(x) \ge 0, or if Sm+1(x)<0S_{m+1}(x) < 0 for every m∈ℕm \in \mathbb{N} and n=0n = 0.✦ The first weak ladder epoch L(x)L(x) is the first time step at which the exploration walk attains a weak ascending ladder record, with weak ladder overshoot O(x)=(SL(x)+1(x))+O(x) = (S_{L(x)+1}(x))_+ and spine ladder pair Λ(x)=(xL(x),O(x))∈ℕ×ℕ\Lambda(x) = (x_{L(x)}, O(x)) \in \mathbb{N} \times \mathbb{N}. Pushing π⊗ℕ\pi^{\otimes \mathbb{N}} forward under Λ\Lambda yields the offspring spine ladder distribution πsp\pi_{\mathrm{sp}} on ℕ×ℕ\mathbb{N} \times \mathbb{N}.✦ For a cutoff m∈ℕm \in \mathbb{N} and a pair z=(k,i)∈ℕ×ℕz = (k, i) \in \mathbb{N} \times \mathbb{N}, the spine tail truncation is tail⁡m(k,i)={kif k>m,0otherwise.\operatorname{tail}_m(k, i) = \begin{cases} k & \text{if } k > m, \\ 0 & \text{otherwise.} \end{cases}(3)✦

The Inventory Model and Core Metric Marks

An FK model parameter choice specifies p∈(1/2,1)p \in (1/2, 1), determining the inventory radius parameter u=(1−p)/16u = (1-p)/16 and the flexible order parameter ϑp=1+2p/(1−p)\vartheta_p = 1 + 2p/(1-p). An inventory order is either a flexible order or a fixed order carrying a type in {true,false}\{\mathrm{true}, \mathrm{false}\}✦, and a burger-order alphabet letter is either a burger token carrying a type in {true,false}\{\mathrm{true}, \mathrm{false}\} or an inventory order.✦ An inventory stack evaluation state pairs a list of pending orders with a freshest-first list of boolean burger types✦; evaluating a word of letters updates this state step by step, and word reduction evaluates the word starting from empty pending orders and an empty burger stack.✦ A word is empty-reducing if its reduction yields the empty state with neither pending orders nor burgers.✦ Under parameter pp, the letter distribution λp\lambda_p on the burger-order alphabet 𝒜\mathcal{A} assigns probability 1/41/4 to each burger token, p/2p/2 to the flexible order, and (1−p)/4(1-p)/4 to each fixed order, generating for each index set ι\iota the independent and identically distributed inventory stream measure ℙstr,p(ι)=λp⊗ι\mathbb{P}_{\mathrm{str},p}^{(\iota)} = \lambda_p^{\otimes \iota} on 𝒜ι\mathcal{A}^\iota. For N∈ℕN \in \mathbb{N}, the empty-reducing word probability ep(N)e_p(N) is the probability ℙstr,p(ℕ)({x:(x0,…,xN−1) is empty-reducing})\mathbb{P}_{\mathrm{str},p}^{(\mathbb{N})}(\{x : (x_0, \dots, x_{N-1})\text{ is empty-reducing}\}), and the total empty word probability τp\tau_p is the sum ∑n=0∞ep(2n)\sum_{n=0}^{\infty} e_p(2n).

A typed burger-order letter is either a burger token or an order token, each carrying a type in {true,false}\{\mathrm{true}, \mathrm{false}\}.✦ Typed word stack execution evaluates a typed word against a boolean burger stack and returns either the resulting stack or failure on an illegal closure, while the empty-reducing typed word set 𝒲N\mathcal{W}_N consists of all typed words of length NN whose execution from an empty stack finishes with an empty stack.✦ For a typed word ww and initial stack ss, the flexible closing count f(w,s)f(w, s) counts the flexible order closures encountered during evaluation; writing f(w)f(w) for the empty initial stack, the inventory word monomial weight of ww at parameters ϑ,r\vartheta, r is ϑf(w)r|w|\vartheta^{f(w)} r^{|w|}. Along a list ll of positions, a non-crossing arch matching is formed inductively by skipping unmatched items or nesting a paired arch (i,j)(i, j) around non-crossing matchings on the interior and exterior✦, and the arch transposition product turns⁡(E)\operatorname{turns}(E) maps an arch list EE to the identity when empty and to turns⁡(E′)∘(ij)\operatorname{turns}(E') \circ (i\;j) when (i,j)(i, j) precedes E′E'.✦ A two-stack matching certificate M=(E,F)M = (E, F) for a typed-letter assignment ww along ll consists of two non-crossing arch matchings EE and FF along ll whose endpoints together form a permutation of ll, with every (i,j)∈E(i, j) \in E pairing a true\mathrm{true} burger with a true\mathrm{true} order and every (i,j)∈F(i, j) \in F pairing a false\mathrm{false} burger with a false\mathrm{false} order✦, and the mate permutation πM\pi_M of MM is the permutation turns⁡(E++F)\operatorname{turns}(E \mathbin{++} F) of ll, where E++FE \mathbin{++} F denotes concatenation.

For a permutation α\alpha of {0,…,K−1}\{0, \dots, K-1\}, the chord opening endpoints are the indices ii with i<α(i)i < \alpha(i)✦; two openers xx and yy satisfy the chord crossing relation if x<y<α(x)<α(y)x < y < \alpha(x) < \alpha(y) or y<x<α(y)<α(x)y < x < \alpha(y) < \alpha(x), forming the edges of the chord intersection graph of α\alpha on its openers. A connected typed core cc of length KK is a typed word of length KK arising from a letter sequence on {0,…,K−1}\{0, \dots, K-1\} admitting a two-stack matching certificate MM whose mate permutation πM\pi_M has a root opener at 00 from which every opener is reachable in the chord intersection graph of πM\pi_M. For a connected typed core cc of length k=|c|k = |c|, empty-stack execution determines its canonical two-stack matching Mc=(Ec,Fc)M_c = (E_c, F_c), its core entry corner is 0∈{0,…,k−1}0 \in \{0, \dots, k-1\}, and its core vertex rotation permutation is ρc=σk∘turns⁡(Ec)\rho_c = \sigma_k \circ \operatorname{turns}(E_c) on {0,…,k−1}\{0, \dots, k-1\}, where σk\sigma_k is the cyclic shift permutation of (0,…,k−1)(0, \dots, k-1). Given any permutation ρ\rho on a finite set, the permutation-wedge vertices are the cycle equivalence classes of ρ\rho✦, and the permutation-wedge dart graph of edge permutation ee and vertex rotation ρ\rho is the simple graph on those cycle vertices whose edges connect distinct cycle classes xx and yy whenever some dart dd belongs to one and e(d)e(d) belongs to the other.✦ The isolated core map graph GcG_c of cc is the permutation-wedge dart graph of πMc\pi_{M_c} and ρc\rho_c✦, and the core corner metric increment of cc at corner j∈{0,…,k−1}j \in \{0, \dots, k-1\} is the graph distance Δc(j)=distGc([0]ρc,[σk(j)]ρc),\Delta_c(j) = \mathrm{dist}_{G_c}\bigl([0]_{\rho_c},\, [\sigma_k(j)]_{\rho_c}\bigr),(4)✦ where [i]ρc[i]_{\rho_c} denotes the cycle vertex of ii under ρc\rho_c.

An optional core label is either empty or a connected typed core cc, with arity 00 when empty and |c||c| when a core cc. At real parameters ϑ,r,τ\vartheta, r, \tau, the parametric core label mass assigns 1/τ1/\tau to the empty label and (1/τ)(1/\tau) times the inventory word monomial weight ϑf(c)(rτ)|c|\vartheta^{f(c)}(r\tau)^{|c|} to a core cc✦; evaluating at (ϑp,u,τp)(\vartheta_p, \sqrt{u}, \tau_p) gives the root core mark mass and defines the root core mark distribution κroot(p)\kappa_{\mathrm{root}}^{(p)} on optional core labels. Conditioning κroot(p)\kappa_{\mathrm{root}}^{(p)} on labels of arity k∈ℕk \in \mathbb{N} produces the conditional core mark distribution κk(p)\kappa_k^{(p)}, or the point mass at the empty label when no label has arity kk, assembling into the conditional core mark family κ(p)=(κk(p))k≥0\kappa^{(p)} = (\kappa_k^{(p)})_{k \ge 0}.✦ For each m∈ℕm \in \mathbb{N}, the core generating polynomial coefficient cm(ϑ)c_m(\vartheta), the block generating polynomial coefficient Φm(ϑ)\Phi_m(\vartheta), and the actual FK block mass bm(p)b_m^{(p)} are cm(ϑ)=∑w∈𝒲2mcoreϑf(w),Φm(ϑ)=𝟏m=0+cm(ϑ),bm(p)=Φm(ϑp)(uτp2)mτp,c_m(\vartheta) = \sum_{w \in \mathcal{W}_{2m}^{\mathrm{core}}} \vartheta^{f(w)}, \qquad \Phi_m(\vartheta) = \mathbf{1}_{m=0} + c_m(\vartheta), \qquad b_m^{(p)} = \Phi_m(\vartheta_p)\,\frac{(u\tau_p^2)^m}{\tau_p},(5) where 𝒲2mcore\mathcal{W}_{2m}^{\mathrm{core}} denotes the words in 𝒲2m\mathcal{W}_{2m} satisfying the connected core word condition. Applying the doubled-mass critical even offspring construction to the actual FK block masses (5) produces the critical FK corner offspring distribution π(p)\pi^{(p)}.✦ For a spine pair z=(k,i)∈ℕ×ℕz = (k, i) \in \mathbb{N} \times \mathbb{N} and an optional core label aa, the core label metric increment is defined from (4) by g((k,i),a)={Δc(k−1−i)if a=c is a core with |c|=k and i<k,0otherwise,g((k, i), a) = \begin{cases} \Delta_c(k - 1 - i) & \text{if } a = c\text{ is a core with } |c| = k \text{ and } i < k, \\ 0 & \text{otherwise,} \end{cases}(6)✦ and the mean core metric increment under parameter pp is βp=∫∫g((k,i),a)dκk(p)(a)dπsp(p)(k,i),\beta_p = \int \!\!\int g((k, i), a)\,\mathrm{d}\kappa_k^{(p)}(a)\,\mathrm{d}\pi_{\mathrm{sp}}^{(p)}(k, i),(7)✦ where πsp(p)\pi_{\mathrm{sp}}^{(p)} is the offspring spine ladder distribution of π(p)\pi^{(p)}.

The Claim

Theorem 1. Let π\pi be a critical even offspring distribution, let (Ω,𝖯)(\Omega, \mathsf{P}) be a probability space carrying a real-valued Brownian motion X=(Xt)t≥0X = (X_t)_{t \ge 0}, let AA be a measurable space equipped with a probability mark kernel κ=(κk)k≥0\kappa = (\kappa_k)_{k \ge 0} into AA, and let b:(ℕ×ℕ)×A→ℝb : (\mathbb{N} \times \mathbb{N}) \times A \to \mathbb{R} be a label such that a↦b(z,a)a \mapsto b(z, a) is measurable for every z∈ℕ×ℕz \in \mathbb{N} \times \mathbb{N} and |b((k,i),a)|≤k|b((k, i), a)| \le k for all k,i∈ℕk, i \in \mathbb{N} and a∈Aa \in A. Write μb=∫∫b((k,i),a)dκk(a)dπsp(k,i)\mu_b = \int \!\!\int b((k, i), a)\,\mathrm{d}\kappa_k(a)\,\mathrm{d}\pi_{\mathrm{sp}}(k, i). Then for every ε>0\varepsilon > 0, the marked spine sum (2) satisfies limn→∞ℙnπ,κ({(d,𝒂):max0≤v≤2n|Bb(d,v,𝒂)−μbHv(d)|>ε2n+1})=0.\lim_{n \to \infty} \mathbb{P}_n^{\pi,\kappa}\!\left(\left\{(d, \mathbf{a}) : \max_{0 \le v \le 2n} \bigl|B_b(d, v, \mathbf{a}) - \mu_b H_v(d)\bigr| > \varepsilon\sqrt{2n+1}\right\}\right) = 0.(8)✦ Under any critical even offspring distribution π\pi alone, the spine tail truncation (3) satisfies limm→∞∫tail⁡m(z)dπsp(z)=0.\lim_{m \to \infty} \int \operatorname{tail}_m(z)\,\mathrm{d}\pi_{\mathrm{sp}}(z) = 0.(9)✦ Moreover, for any FK parameter p∈(1/2,1)p \in (1/2, 1) and any probability space (Ω,μ)(\Omega, \mu) carrying a real-valued Brownian motion X=(Xt)t≥0X = (X_t)_{t \ge 0}, the core label metric increment (6) and its mean (7) satisfy, for every ε>0\varepsilon > 0, limn→∞ℙnπ(p),κ(p)({(d,𝒂):max0≤v≤2n|Bg(d,v,𝒂)−βpHv(d)|>ε2n+1})=0.\lim_{n \to \infty} \mathbb{P}_n^{\pi^{(p)},\kappa^{(p)}}\!\left(\left\{(d, \mathbf{a}) : \max_{0 \le v \le 2n} \bigl|B_g(d, v, \mathbf{a}) - \beta_p H_v(d)\bigr| > \varepsilon\sqrt{2n+1}\right\}\right) = 0.(10)✦

In the paper, the result reads: let b=b(k,i,A)b = b(k, i, A) be a fixed measurable label with 0≤b≤k0 \le b \le k; then μb<∞\mu_b < \infty, 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}), and max⁡v∈TN|Bb(v)−(μb/ν)W(v)|=oP(N)\max_{v \in T_N} |B_b(v) - (\mu_b/\nu) W(v)| = o_P(\sqrt{N}), where Bb(d,v,𝒂)B_b(d, v, \mathbf{a}), Hv(d)H_v(d), Wv(d)W_v(d), and μb\mu_b stand for Bb(v)B_b(v), H(v)H(v), W(v)W(v), and μb\mu_b, and TNT_N denotes the conditioned tree of size NN.

What Is Checked

Claims (8) and (9) are stated over critical even offspring distributions π\pi and their offspring spine ladder distributions πsp\pi_{\mathrm{sp}}, together with the spine tail truncation (3) in (9) and, in (8), marked tree code laws ℙnπ,κ\mathbb{P}_n^{\pi,\kappa} on size 2n+12n+1, a probability space carrying a real-valued Brownian motion, and a measurable label bb bounded in absolute value by the offspring degree. Claim (10) is stated over an FK parameter p∈(1/2,1)p \in (1/2, 1), a probability space carrying a real-valued Brownian motion, the critical FK corner offspring distribution π(p)\pi^{(p)} built from the actual FK block masses (5), the conditional core mark distribution κ(p)\kappa^{(p)}, and the core label metric increment (6) with mean (7).

About these constructions, the library establishes that for every FK parameter p∈(1/2,1)p \in (1/2, 1) the actual FK block masses (5) are nonnegative for all m∈ℕm \in \mathbb{N}✦ and strictly positive at m=0m = 0 and m=1m = 1. It also establishes that any typed-letter sequence along a list of positions whose typed stack execution from an empty stack terminates in an empty stack admits a two-stack matching certificate✦, and that every stream x:ℕ→ℕx : \mathbb{N} \to \mathbb{N} admits an index satisfying the ladder epoch condition.✦