OctoInformBeta

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

§5 (setting): exploration walks and excursions: Conditioned Lukasiewicz tree codes, height processes, mean spine degree σ2+1\sigma^2 + 1, and marked spine sums

Exploration walks and spine laws for conditioned Galton-Watson 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

Take a critical even Galton-Watson tree conditioned to have N=2n+1N = 2n + 1 vertices and list its vertex out-degrees in preorder. Centered partial sums of these degrees trace a discrete excursion that determines the height of each vertex, while reversing the prefix up to a vertex picks out the degrees and child positions along its ancestral spine and sums vertex marks over that spine.

Critical Even Offspring Laws and Tree Codes

A critical even offspring distribution pp is a nonnegative real-valued mass function on the nonnegative integers ℕ\mathbb{N} summing to 11 such that p(k)=0p(k) = 0 for every odd k∈ℕk \in \mathbb{N}, 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.✦ The offspring distribution variance σ2\sigma^2 of a critical even offspring distribution pp is the nonnegative real number defined by (1): σ2=∑k=0∞(k−1)2p(k).\sigma^2 = \sum_{k=0}^{\infty} (k - 1)^2 p(k).(1)✦

For a critical even offspring distribution pp and each N∈ℕN \in \mathbb{N}, the independent and identically distributed (i.i.d.) offspring product measure p⊗Np^{\otimes N} on ℕN\mathbb{N}^N is the product measure of NN copies of pp.✦ Writing ℤ\mathbb{Z} for the integers, the total step Δ(d)\Delta(d) of an array d=(d0,…,dN−1)∈ℕNd = (d_0, \dots, d_{N-1}) \in \mathbb{N}^N is the integer given by (2): Δ(d)=∑i=0N−1(di−1).\Delta(d) = \sum_{i=0}^{N-1} (d_i - 1).(2)✦ For a critical even offspring distribution pp and 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 measure p⊗(2n+1)p^{\otimes(2n+1)} conditioned on the event {d∈ℕ2n+1:Δ(d)=−1}\{d \in \mathbb{N}^{2n+1} : \Delta(d) = -1\}.✦

Given N∈ℕN \in \mathbb{N}, a degree sequence d=(d0,…,dN−1)∈{0,…,N−1}Nd = (d_0, \dots, d_{N-1}) \in \{0, \dots, N-1\}^N, and step j∈ℕj \in \mathbb{N}, the degree sequence partial walk wj(d)w_j(d) of dd at step jj is the integer ∑i=0N−1𝟏{i<j}(di−1)∈ℤ\sum_{i=0}^{N-1} \mathbf{1}_{\{i < j\}} (d_i - 1) \in \mathbb{Z}.✦ 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.✦ Given N∈ℕN \in \mathbb{N}, the valid tree code condition on a sequence d∈{0,…,N−1}Nd \in \{0, \dots, N-1\}^N is the condition that wN(d)=−1w_N(d) = -1 and wj(d)≥0w_j(d) \ge 0 for every 0≤j<N0 \le j < N.✦ A Lukasiewicz tree code dd of length NN is a sequence in {0,…,N−1}N\{0, \dots, N-1\}^N satisfying the valid tree code condition, and 𝒞N\mathcal{C}_N denotes the set of Lukasiewicz tree codes of length NN.✦

When N≥1N \ge 1 and m∈{0,…,N−1}m \in \{0, \dots, N-1\}, the cyclic rotation ρm\rho_m sends d∈{0,…,N−1}Nd \in \{0, \dots, N-1\}^N entrywise to (ρmd)i=d(i+m)mod⁡N(\rho_m d)_i = d_{(i+m) \bmod N} (0≤i<N0 \le i < N)✦ and induces a permutation of the discrete bridge sequences of length NN.✦ Every discrete bridge sequence dd of length N≥1N \ge 1 admits a unique good rotation index m*(d)∈{0,…,N−1}m^*(d) \in \{0, \dots, N-1\} such that ρm*(d)(d)\rho_{m^*(d)}(d) satisfies the valid tree code condition.✦ The canonical tree code of a discrete bridge sequence dd of length N≥1N \ge 1 is the Lukasiewicz tree code ρm*(d)(d)∈𝒞N\rho_{m^*(d)}(d) \in \mathcal{C}_N.✦ For any N∈ℕN \in \mathbb{N}, each array d∈ℕNd \in \mathbb{N}^N with total step Δ(d)=−1\Delta(d) = -1 defines a discrete bridge sequence of length NN✦, and for n∈ℕn \in \mathbb{N} the tree code map τn:ℕ2n+1→𝒞2n+1\tau_n : \mathbb{N}^{2n+1} \to \mathcal{C}_{2n+1} sends each array in ℕ2n+1\mathbb{N}^{2n+1} to a Lukasiewicz tree code of length 2n+12n+1.

Spine Ladder Law and Spine Records

The infinite offspring product measure p⊗ℕp^{\otimes \mathbb{N}} on ℕℕ\mathbb{N}^{\mathbb{N}} of a critical even offspring distribution pp is the countable product of copies of pp.✦ Given a stream x=(x0,x1,…)∈ℕℕx = (x_0, x_1, \dots) \in \mathbb{N}^{\mathbb{N}} and step n∈ℕn \in \mathbb{N}, the offspring walk partial sum Sn(x)S_n(x) is the integer defined by (3), and S(x):ℕ→ℤS(x) : \mathbb{N} \to \mathbb{Z} denotes the sequence j↦Sj(x)j \mapsto S_j(x): Sn(x)=∑k=0n−1(xk−1).S_n(x) = \sum_{k=0}^{n-1} (x_k - 1).(3)✦ The ladder epoch condition for an index n∈ℕn \in \mathbb{N} and a stream x∈ℕℕx \in \mathbb{N}^{\mathbb{N}} is the condition that either Sn+1(x)≥0S_{n+1}(x) \ge 0, or Sm+1(x)<0S_{m+1}(x) < 0 for every m∈ℕm \in \mathbb{N} and n=0n = 0.✦ The first weak ladder epoch τ(x)∈ℕ\tau(x) \in \mathbb{N} of a stream x∈ℕℕx \in \mathbb{N}^{\mathbb{N}} is the smallest index n∈ℕn \in \mathbb{N} satisfying the ladder epoch condition for xx✦, and the weak ladder overshoot O(x)O(x) of xx is the nonnegative integer max⁡(Sτ(x)+1(x),0)∈ℕ\max(S_{\tau(x)+1}(x), 0) \in \mathbb{N}.✦ The spine ladder variable pair L(x)L(x) of a stream x∈ℕℕx \in \mathbb{N}^{\mathbb{N}} is the pair (xτ(x),O(x))∈ℕ×ℕ(x_{\tau(x)}, O(x)) \in \mathbb{N} \times \mathbb{N}✦, and the offspring spine ladder distribution νsp\nu_{\mathrm{sp}} of a critical even offspring distribution pp on ℕ×ℕ\mathbb{N} \times \mathbb{N} is the pushforward measure of p⊗ℕp^{\otimes \mathbb{N}} under LL.✦

For an array d=(d0,…,dN−1)∈ℕNd = (d_0, \dots, d_{N-1}) \in \mathbb{N}^N (N∈ℕN \in \mathbb{N}), the zero-extended stream d‾∈ℕℕ\bar{d} \in \mathbb{N}^{\mathbb{N}} is the stream with d‾k=dk\bar{d}_k = d_k for k<Nk < N and d‾k=0\bar{d}_k = 0 for k≥Nk \ge N.✦ For v∈ℕv \in \mathbb{N}, the reversed prefix index map ιv:ℕ→ℕ\iota_v : \mathbb{N} \to \mathbb{N} is ιv(k)=v−1−k\iota_v(k) = v - 1 - k for k<vk < v and ιv(k)=k\iota_v(k) = k for k≥vk \ge v✦, and the reversed prefix x(v)x^{(v)} of a stream x∈ℕℕx \in \mathbb{N}^{\mathbb{N}} at vv is the stream with xk(v)=xιv(k)x^{(v)}_k = x_{\iota_v(k)}.✦ For a sequence S:ℕ→ℤS : \mathbb{N} \to \mathbb{Z} and n∈ℕn \in \mathbb{N}, the running maximum Mn(S)M_n(S) of SS up to nn is the integer max⁡0≤j≤nSj\max_{0 \le j \le n} S_j✦, and the set ℛ(S,n)\mathcal{R}(S, n) of weak record times up to nn is given by (4): ℛ(S,n)={k∈{1,…,n}:Sj≤Sk for all 0≤j≤k}.\mathcal{R}(S, n) = \{k \in \{1, \dots, n\} : S_j \le S_k \text{ for all } 0 \le j \le k\}.(4)✦ Given N∈ℕN \in \mathbb{N}, a Lukasiewicz tree code d∈𝒞Nd \in \mathcal{C}_N, and v∈ℕv \in \mathbb{N}, the spine record set ℛsp(d,v)\mathcal{R}_{\mathrm{sp}}(d, v) of dd at vv is the set ℛ(S(d‾(v)),v)\mathcal{R}(S(\bar{d}^{(v)}), v).✦ For a stream x∈ℕℕx \in \mathbb{N}^{\mathbb{N}} and step t∈ℕt \in \mathbb{N}, putting t′=max⁡(t−1,0)t' = \max(t - 1, 0), the record type rec(x,t)\mathrm{rec}(x, t) is the pair defined by (5): rec(x,t)=(xt′,max⁡(St(x)−Mt′(S(x)),0)).\mathrm{rec}(x, t) = \bigl(x_{t'},\, \max\bigl(S_t(x) - M_{t'}(S(x)),\, 0\bigr)\bigr).(5)✦ For N∈ℕN \in \mathbb{N}, a Lukasiewicz tree code d∈𝒞Nd \in \mathcal{C}_N, v∈ℕv \in \mathbb{N}, and t∈ℛsp(d,v)t \in \mathcal{R}_{\mathrm{sp}}(d, v), the spine record type typev(d,t)\mathrm{type}_v(d, t) is the pair rec(d‾(v),t)\mathrm{rec}(\bar{d}^{(v)}, t)✦, and for v≤Nv \le N the spine record vertex of tt is the index v−t∈{0,…,N−1}v - t \in \{0, \dots, N-1\}.✦

The Claim

Definition 1. For a critical even offspring distribution pp and size parameter n∈ℕn \in \mathbb{N}, the conditioned tree code law μp,n\mu_{p,n} on 𝒞2n+1\mathcal{C}_{2n+1} is the pushforward measure (6): μp,n=(τn)*ℙp,nbr.\mu_{p,n} = (\tau_n)_* \mathbb{P}_{p,n}^{\mathrm{br}}.(6)✦ Given N∈ℕN \in \mathbb{N}, a sequence d∈{0,…,N−1}Nd \in \{0, \dots, N-1\}^N, and step j∈ℕj \in \mathbb{N}, the tree height process Hj(d)H_j(d) is the integer given by (7): Hj(d)=#{k∈{0,…,N−1}:k<j and wk(d)≤wr(d) for all k≤r≤min⁡(j,N)}.H_j(d) = \#\bigl\{k \in \{0, \dots, N-1\} : k < j \text{ and } w_k(d) \le w_r(d) \text{ for all } k \le r \le \min(j, N)\bigr\}.(7)✦ The exploration walk Wj(d)W_j(d) of an array d=(d0,…,dN−1)∈ℕNd = (d_0, \dots, d_{N-1}) \in \mathbb{N}^N (N∈ℕN \in \mathbb{N}) at step j∈ℕj \in \mathbb{N} is the integer defined by (8): Wj(d)=∑i=0N−1𝟏{i<j}(di−1).W_j(d) = \sum_{i=0}^{N-1} \mathbf{1}_{\{i < j\}} (d_i - 1).(8)✦ The offspring standard deviation σ\sigma of a critical even offspring distribution pp with variance σ2\sigma^2 is the nonnegative real number (9): σ=σ2.\sigma = \sqrt{\sigma^2}.(9)✦ For N∈ℕN \in \mathbb{N}, a mark set AA, a weight function b:(ℕ×ℕ)×A→ℝb : (\mathbb{N} \times \mathbb{N}) \times A \to \mathbb{R}, a Lukasiewicz tree code d∈𝒞Nd \in \mathcal{C}_N, an index v≤Nv \le N, and vertex marks a=(a0,…,aN−1)∈ANa = (a_0, \dots, a_{N-1}) \in A^N, the marked spine sum Bb(v)∈ℝB_b(v) \in \mathbb{R} is the sum (10): Bb(v)=∑t∈ℛsp(d,v)b(typev(d,t),av−t).B_b(v) = \sum_{t \in \mathcal{R}_{\mathrm{sp}}(d, v)} b\bigl(\mathrm{type}_v(d, t),\, a_{v-t}\bigr).(10)✦

Theorem 1. If pp is a critical even offspring distribution with variance σ2\sigma^2 and offspring spine ladder distribution νsp\nu_{\mathrm{sp}}, then (11) holds: ∫ℕ×ℕz1dνsp(z1,z2)=σ2+1.\int_{\mathbb{N} \times \mathbb{N}} z_1 \, d\nu_{\mathrm{sp}}(z_1, z_2) = \sigma^2 + 1.(11)✦

What Is Checked

The conditioned tree code law (6), tree height process (7), exploration walk (8), offspring standard deviation (9), spine mean identity (11), and marked spine sum (10) are stated over a critical even offspring distribution pp (a nonnegative real-valued mass function on ℕ\mathbb{N} summing to 11, vanishing on odd integers, with p(0)>0p(0) > 0, p(2)>0p(2) > 0, mean 11, and finite second moment), its variance σ2\sigma^2 and offspring spine ladder distribution νsp\nu_{\mathrm{sp}}, a size parameter n∈ℕn \in \mathbb{N} or length N∈ℕN \in \mathbb{N}, a degree sequence d∈{0,…,N−1}Nd \in \{0, \dots, N-1\}^N or array d∈ℕNd \in \mathbb{N}^N, and a Lukasiewicz tree code d∈𝒞Nd \in \mathcal{C}_N with index v≤Nv \le N, a mark set AA, vertex marks a∈ANa \in A^N, and a weight function b:(ℕ×ℕ)×A→ℝb : (\mathbb{N} \times \mathbb{N}) \times A \to \mathbb{R}.

Moreover, every stream x∈ℕℕx \in \mathbb{N}^{\mathbb{N}} admits an index n∈ℕn \in \mathbb{N} satisfying the ladder epoch condition.✦