OctoInformBeta

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

Corollary 5.2 [Offspring and walk bounds]: Height tightness and vanishing limits in probability at square-root scale for maximum degree and spine-height deviations, with a bridge identity

Offspring and height bounds for critical even tree codes.

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

Consider a conditioned Galton-Watson tree of odd size N=2n+1N = 2n + 1 governed by a critical even offspring distribution. At scale N\sqrt{N}, how large can vertex heights and individual offspring counts grow, and how closely do degree sums along ancestral paths to the root track a constant multiple of vertex height?

Offspring Laws and Tree Codes

A critical even offspring distribution μ\mu is a nonnegative function μ:ℕ→ℝ\mu : \mathbb{N} \to \mathbb{R}, inducing an offspring probability law on ℕ\mathbb{N}, such that μ\mu vanishes on all odd integers, satisfies μ(0)>0\mu(0) > 0 and μ(2)>0\mu(2) > 0, and obeys (1): ∑k=0∞μ(k)=1,∑k=0∞kμ(k)=1,∑k=0∞k2μ(k)<∞.\sum_{k=0}^{\infty} \mu(k) = 1, \qquad \sum_{k=0}^{\infty} k\,\mu(k) = 1, \qquad \sum_{k=0}^{\infty} k^2 \mu(k) < \infty.(1)✦ The offspring distribution variance σ2\sigma^2 of μ\mu is given by (2): σ2=∑k=0∞(k−1)2μ(k).\sigma^2 = \sum_{k=0}^{\infty} (k - 1)^2 \mu(k).(2)✦

Given a critical even offspring distribution μ\mu and N∈ℕN \in \mathbb{N}, the independent and identically distributed (i.i.d.) offspring product measure ℙμ,Niid\mathbb{P}_{\mu, N}^{\mathrm{iid}} on ℕN\mathbb{N}^N is the NN-fold product of the offspring law of μ\mu.✦ The total step of a finite sequence d=(d0,…,dN−1)∈ℕNd = (d_0, \dots, d_{N-1}) \in \mathbb{N}^N is s(d)=∑i=0N−1(di−1)s(d) = \sum_{i=0}^{N-1} (d_i - 1).✦ Conditioning ℙμ,2n+1iid\mathbb{P}_{\mu, 2n+1}^{\mathrm{iid}} on the event {d∈ℕ2n+1:s(d)=−1}\{d \in \mathbb{N}^{2n+1} : s(d) = -1\} for n∈ℕn \in \mathbb{N} defines the conditioned offspring bridge law ℙμ,nbr\mathbb{P}_{\mu, n}^{\mathrm{br}} on ℕ2n+1\mathbb{N}^{2n+1}.✦

The degree sequence partial walk Wd(j)W_d(j) of d=(d0,…,dN−1)∈{0,…,N−1}Nd = (d_0, \dots, d_{N-1}) \in \{0, \dots, N-1\}^N (N∈ℕN \in \mathbb{N}) at step j∈ℕj \in \mathbb{N} is given by (3): Wd(j)=∑0≤i<min⁡(j,N)(di−1).W_d(j) = \sum_{0 \le i < \min(j, N)} (d_i - 1).(3) A sequence d∈{0,…,N−1}Nd \in \{0, \dots, N-1\}^N satisfies the valid tree-code condition when Wd(N)=−1W_d(N) = -1 and Wd(j)≥0W_d(j) \ge 0 for all 0≤j<N0 \le j < N.✦ A Lukasiewicz tree code of length NN is a sequence d∈{0,…,N−1}Nd \in \{0, \dots, N-1\}^N satisfying the valid tree-code condition, forming the set Code(N)\mathrm{Code}(N).✦ A discrete bridge sequence of length NN is a sequence d∈{0,…,N−1}Nd \in \{0, \dots, N-1\}^N satisfying Wd(N)=−1W_d(N) = -1, forming the set Bridge(N)\mathrm{Bridge}(N).✦ When N≥1N \ge 1 and m∈{0,…,N−1}m \in \{0, \dots, N-1\}, the cyclic rotation ρm\rho_m is the permutation on {0,…,N−1}N\{0, \dots, N-1\}^N, and by restriction on Bridge(N)\mathrm{Bridge}(N), sending dd to the sequence ρmd\rho_m d given by (ρmd)i=d(i+m)mod⁡N(\rho_m d)_i = d_{(i+m) \bmod N} for 0≤i<N0 \le i < N.

For N∈ℕN \in \mathbb{N}, d∈{0,…,N−1}Nd \in \{0, \dots, N-1\}^N, and j∈ℕj \in \mathbb{N}, the tree vertex height Hd(j)H_d(j) is the cardinality in (4): Hd(j)=#{k∈{0,…,N−1}:k<j and Wd(k)≤Wd(r) for all r∈{0,…,N} with k≤r≤j}.H_d(j) = \#\bigl\{k \in \{0, \dots, N-1\} : k < j \text{ and } W_d(k) \le W_d(r) \text{ for all } r \in \{0, \dots, N\} \text{ with } k \le r \le j\bigr\}.(4)✦

For n∈ℕn \in \mathbb{N}, the tree-code map ψn:ℕ2n+1→Code(2n+1)\psi_n : \mathbb{N}^{2n+1} \to \mathrm{Code}(2n+1) sends each sequence in ℕ2n+1\mathbb{N}^{2n+1} to a Lukasiewicz tree code of length 2n+12n+1, and the conditioned tree-code law ℙμ,ncode\mathbb{P}_{\mu, n}^{\mathrm{code}} on Code(2n+1)\mathrm{Code}(2n+1) is the pushforward of ℙμ,nbr\mathbb{P}_{\mu, n}^{\mathrm{br}} under ψn\psi_n. Given a critical even offspring distribution μ\mu and N∈ℕN \in \mathbb{N}, the tree-code weight of d∈Code(N)d \in \mathrm{Code}(N) is wcode(μ,d)=∏i=0N−1μ(di)w_{\mathrm{code}}(\mu, d) = \prod_{i=0}^{N-1} \mu(d_i), and the tree-code partition function is Zcode(μ,N)=∑d∈Code(N)wcode(μ,d)Z_{\mathrm{code}}(\mu, N) = \sum_{d \in \mathrm{Code}(N)} w_{\mathrm{code}}(\mu, d)✦. The bridge weight of d∈Bridge(N)d \in \mathrm{Bridge}(N) under μ\mu and N∈ℕN \in \mathbb{N} is wbr(μ,d)=∏i=0N−1μ(di)w_{\mathrm{br}}(\mu, d) = \prod_{i=0}^{N-1} \mu(d_i)✦, with bridge partition function Zbr(μ,N)=∑d∈Bridge(N)wbr(μ,d)Z_{\mathrm{br}}(\mu, N) = \sum_{d \in \mathrm{Bridge}(N)} w_{\mathrm{br}}(\mu, d)✦. For a critical even offspring distribution μ\mu, an integer N∈ℕN \in \mathbb{N}, and an event E⊆{0,…,N−1}NE \subseteq \{0, \dots, N-1\}^N, the tree-code event mass Mcode(μ,N,E)M_{\mathrm{code}}(\mu, N, E) is the unnormalized mass ∑d∈E∩Code(N)wcode(μ,d)\sum_{d \in E \cap \mathrm{Code}(N)} w_{\mathrm{code}}(\mu, d), and the tree-code event probability Qμ,N(E)Q_{\mu, N}(E) is the ratio given by (5): Qμ,N(E)=Mcode(μ,N,E)Zcode(μ,N).Q_{\mu, N}(E) = \frac{M_{\mathrm{code}}(\mu, N, E)}{Z_{\mathrm{code}}(\mu, N)}.(5)

Spine Sums and Reversed Paths

Given S:ℕ→ℤS : \mathbb{N} \to \mathbb{Z} and a horizon b∈ℕb \in \mathbb{N}, the time-reversed path S⃖b:ℕ→ℤ\overleftarrow{S}_b : \mathbb{N} \to \mathbb{Z} is defined by (6): S⃖b(k)=S(b)−S(max⁡(b−k,0)),k∈ℕ.\overleftarrow{S}_b(k) = S(b) - S(\max(b - k, 0)), \qquad k \in \mathbb{N}.(6)✦ The running maximum of S:ℕ→ℤS : \mathbb{N} \to \mathbb{Z} up to N∈ℕN \in \mathbb{N} is MN(S)=max⁡0≤k≤NS(k)M_N(S) = \max_{0 \le k \le N} S(k).✦ When S:ℕ→αS : \mathbb{N} \to \alpha takes values in a linearly ordered set α\alpha and n∈ℕn \in \mathbb{N}, the weak record times up to nn form the finite set ℛn(S)\mathcal{R}_n(S) in (7): ℛn(S)={k∈ℕ:1≤k≤n and S(j)≤S(k) for all 0≤j≤k}.\mathcal{R}_n(S) = \{k \in \mathbb{N} : 1 \le k \le n \text{ and } S(j) \le S(k) \text{ for all } 0 \le j \le k\}.(7)✦

The offspring walk partial sum of a sequence x:ℕ→ℕx : \mathbb{N} \to \mathbb{N} at time n∈ℕn \in \mathbb{N} is Ux(n)=∑k=0n−1(x(k)−1)U_x(n) = \sum_{k=0}^{n-1} (x(k) - 1).✦ At step t∈ℕt \in \mathbb{N}, the record type of x:ℕ→ℕx : \mathbb{N} \to \mathbb{N} is the pair τx(t)∈ℕ×ℕ\tau_x(t) \in \mathbb{N} \times \mathbb{N} given by (8): τx(t)=(x(max⁡(t−1,0)),max⁡{Ux(t)−Mmax⁡(t−1,0)(Ux),0}).\tau_x(t) = \bigl(x(\max(t - 1, 0)),\, \max\{U_x(t) - M_{\max(t - 1, 0)}(U_x),\, 0\}\bigr).(8)✦ For a mark function b:ℕ×ℕ→ℝb : \mathbb{N} \times \mathbb{N} \to \mathbb{R}, a sequence x:ℕ→ℕx : \mathbb{N} \to \mathbb{N}, and v∈ℕv \in \mathbb{N}, the record spine sum Σbrec(x,v)\Sigma_b^{\mathrm{rec}}(x, v) is the real number given by (9): Σbrec(x,v)=∑t∈ℛv(Ux)b(τx(t)).\Sigma_b^{\mathrm{rec}}(x, v) = \sum_{t \in \mathcal{R}_v(U_x)} b\bigl(\tau_x(t)\bigr).(9) Extending a finite sequence d=(d0,…,dN−1)∈ℕNd = (d_0, \dots, d_{N-1}) \in \mathbb{N}^N (N∈ℕN \in \mathbb{N}) by zero beyond NN yields the sequence d‾:ℕ→ℕ\bar{d} : \mathbb{N} \to \mathbb{N} 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 n,k∈ℕn, k \in \mathbb{N}, the reversed prefix index is ιn(k)=n−1−k\iota_n(k) = n - 1 - k when k<nk < n and ιn(k)=k\iota_n(k) = k when k≥nk \ge n.✦ Composing a sequence x:ℕ→ℕx : \mathbb{N} \to \mathbb{N} with ιn\iota_n gives the reversed prefix sequence revn(x)(k)=x(ιn(k))\mathrm{rev}_n(x)(k) = x(\iota_n(k)).✦ Evaluated on a Lukasiewicz tree code d∈Code(N)d \in \mathrm{Code}(N), a mark b:ℕ×ℕ→ℝb : \mathbb{N} \times \mathbb{N} \to \mathbb{R}, and v∈ℕv \in \mathbb{N}, the tree-code spine sum is Σbcode(d,v)=Σbrec(revv(d‾),v)\Sigma_b^{\mathrm{code}}(d, v) = \Sigma_b^{\mathrm{rec}}(\mathrm{rev}_v(\bar{d}), v).✦

The Claim

Theorem 1. Let μ\mu be a critical even offspring distribution with variance σ2\sigma^2.

  1. For every ε>0\varepsilon > 0, the maximum offspring count satisfies (10): limn→∞Qμ,2n+1({d∈{0,…,2n}2n+1:max0≤i≤2ndi>ε2n+1})=0.\lim_{n \to \infty} Q_{\mu, 2n+1}\!\left(\left\{d \in \{0, \dots, 2n\}^{2n+1} : \max_{0 \le i \le 2n} d_i > \varepsilon\sqrt{2n+1}\right\}\right) = 0.(10)✦

  2. For every n∈ℕn \in \mathbb{N} and all ν,a∈ℝ\nu, a \in \mathbb{R}, writing 𝟏{⋅}\mathbf{1}\{\cdot\} for the indicator of a condition and W⃖d,2n+1\overleftarrow{W}_{d, 2n+1} for the time-reversed path of WdW_d with horizon 2n+12n+1, the tree-code and bridge averages satisfy (11): ∑d∈Code(2n+1)wcode(μ,d)Zcode(μ,2n+1)⋅12n+1∑v=02n𝟏{|Wd(v)−νHd(v)|>a}=∑d∈Bridge(2n+1)wbr(μ,d)Zbr(μ,2n+1)𝟏{|M2n+1(W⃖d,2n+1)−ν#ℛ2n+1(W⃖d,2n+1)|>a}.\begin{aligned} \sum_{d \in \mathrm{Code}(2n+1)} &\frac{w_{\mathrm{code}}(\mu, d)}{Z_{\mathrm{code}}(\mu, 2n+1)} \cdot \frac{1}{2n+1} \sum_{v=0}^{2n} \mathbf{1}\bigl\{|W_d(v) - \nu H_d(v)| > a\bigr\} \\ &= \sum_{d \in \mathrm{Bridge}(2n+1)} \frac{w_{\mathrm{br}}(\mu, d)}{Z_{\mathrm{br}}(\mu, 2n+1)}\, \mathbf{1}\Bigl\{\bigl|M_{2n+1}(\overleftarrow{W}_{d, 2n+1}) - \nu\,\#\mathcal{R}_{2n+1}(\overleftarrow{W}_{d, 2n+1})\bigr| > a\Bigr\}. \end{aligned}(11)✦

  3. Given a probability space (Ω,P)(\Omega, P) equipped with a real Brownian motion BB and a threshold η>0\eta > 0, there exists C>0C > 0 such that for all sufficiently large n∈ℕn \in \mathbb{N}, the height tail satisfies (12): ℙμ,ncode({d∈Code(2n+1):max0≤v≤2n+1Hd(v)>C2n+1})≤η.\mathbb{P}_{\mu, n}^{\mathrm{code}}\!\left(\left\{d \in \mathrm{Code}(2n+1) : \max_{0 \le v \le 2n+1} H_d(v) > C\sqrt{2n+1}\right\}\right) \le \eta.(12)✦

  4. Given a probability space (Ω,P)(\Omega, P) equipped with a real Brownian motion BB, the first-coordinate mark b1(k,j)=kb_1(k, j) = k on ℕ×ℕ\mathbb{N} \times \mathbb{N}, and ε>0\varepsilon > 0, the spine-height deviation satisfies (13): limn→∞ℙμ,ncode({d∈Code(2n+1):max0≤v≤2n|Σb1code(d,v)−(σ2+1)Hd(v)|>ε2n+1})=0.\lim_{n \to \infty} \mathbb{P}_{\mu, n}^{\mathrm{code}}\!\left(\left\{ d \in \mathrm{Code}(2n+1) : \max_{0 \le v \le 2n} \bigl|\Sigma_{b_1}^{\mathrm{code}}(d, v) - (\sigma^2 + 1) H_d(v)\bigr| > \varepsilon\sqrt{2n+1}\right\}\right) = 0.(13)✦

In the paper, the result reads: for size N=2n+1N = 2n+1, max⁡vH(v)=OP(N)\max_v H(v) = O_P(\sqrt{N}), max⁡vW(v)=OP(N)\max_v W(v) = O_P(\sqrt{N}), ΔN=oP(N)\Delta_N = o_P(\sqrt{N}), and max⁡v|W(v)−νH(v)|=oP(N)\max_v |W(v) - \nu H(v)| = o_P(\sqrt{N}), where HH and WW correspond to HdH_d and WdW_d, ΔN\Delta_N is the maximum offspring count, ν\nu is the height-walk slope parameter, and OPO_P and oPo_P denote stochastic boundedness and convergence to zero in probability. The library casts the tree-code degree and height bounds in (10) and (12), while addressing the height-walk comparison through the spine-sum limit (13) and the exact bridge identity (11).

What Is Checked

The four claims of the theorem are formulated over a critical even offspring distribution μ\mu with variance σ2\sigma^2 and its induced conditioned laws ℙμ,ncode\mathbb{P}_{\mu, n}^{\mathrm{code}} and Qμ,2n+1Q_{\mu, 2n+1} on weighted length-(2n+1)(2n+1) tree codes and discrete bridges, together with the walk-height and reversed-path record functionals (and tree-code spine sums), assuming a real Brownian motion BB on a probability space (Ω,P)(\Omega, P) in (12) and (13). Every discrete bridge sequence dd of length N≥1N \ge 1 has a unique good rotation index m∈{0,…,N−1}m \in \{0, \dots, N-1\} such that the cyclic bridge rotation ρm(d)\rho_m(d) satisfies the valid tree-code condition, yielding the canonical tree code of dd.