OctoInformBeta

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

Lemma 5.3 [Cost of conditioning]: (2n+1)3/2(2n+1)^{3/2} tree code and (2n+1)1/2(2n+1)^{1/2} bridge partition limits, a cycle identity for positive lengths, and a uniform local limit

Asymptotics along odd lengths 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

Take a Galton-Watson tree TT whose critical, finite-variance offspring distribution is supported on even integers, so that its vertex count |T||T| is necessarily odd. The question is the cost of conditioning TT to have size N=2n+1N = 2n + 1: at what rate does the probability that |T|=2n+1|T| = 2n + 1 decay as n→∞n \to \infty?

Offspring Distributions and Tree Codes

A critical even offspring distribution pp is a real-valued function k↦p(k)k \mapsto p(k) on ℕ\mathbb{N} that is nonnegative at every kk, sums to ∑k=0∞p(k)=1\sum_{k=0}^{\infty} p(k) = 1, vanishes at every odd kk, satisfies p(0)>0p(0) > 0 and p(2)>0p(2) > 0, has mean ∑k=0∞kp(k)=1\sum_{k=0}^{\infty} k\, p(k) = 1, and has a finite second moment ∑k=0∞k2p(k)<∞\sum_{k=0}^{\infty} k^2 p(k) < \infty.✦ The offspring probability mass function νp\nu_p of a critical even offspring distribution pp is the probability law on ℕ\mathbb{N} assigning mass p(k)p(k) to each k∈ℕk \in \mathbb{N}.✦ For a critical even offspring distribution pp and a natural number NN, the independent and identically distributed (i.i.d.) offspring product measure νp⊗N\nu_p^{\otimes N} on ℕN\mathbb{N}^N is the product measure of νp\nu_p over the indices 0≤i<N0 \le i < N.✦

The offspring distribution variance σ2\sigma^2 of a critical even offspring distribution pp is the real sum (1): σ2=∑k=0∞(k−1)2p(k).\sigma^2 = \sum_{k=0}^{\infty} (k - 1)^2 p(k).(1)✦ The offspring standard deviation σ\sigma of a critical even offspring distribution pp is the square root σ2\sqrt{\sigma^2} of the offspring distribution variance.✦

For a natural number NN and a sequence d∈ℕNd \in \mathbb{N}^N indexed by 0≤i<N0 \le i < N, the total step S(d)S(d) of dd is the integer sum (2): S(d)=∑0≤i<N(di−1).S(d) = \sum_{0 \le i < N} (d_i - 1).(2)✦ Given a natural number NN, a degree sequence d∈{0,…,N−1}Nd \in \{0, \dots, N - 1\}^N, and a step j∈ℕj \in \mathbb{N}, the degree sequence partial walk Wj(d)W_j(d) is the integer (3): Wj(d)=∑0≤i<min⁡(j,N)(di−1).W_j(d) = \sum_{0 \le i < \min(j, N)} (d_i - 1).(3)✦

A discrete bridge sequence dd of length N∈ℕN \in \mathbb{N} is a degree sequence in {0,…,N−1}N\{0, \dots, N - 1\}^N whose degree sequence partial walk satisfies WN(d)=−1W_N(d) = -1; let ℬN\mathcal{B}_N denote the set of all discrete bridge sequences of length NN.✦ Given a critical even offspring distribution pp and a discrete bridge sequence d∈ℬNd \in \mathcal{B}_N of length N∈ℕN \in \mathbb{N}, the bridge weight wbr(p,d)w_{\mathrm{br}}(p, d) is the real product ∏0≤i<Np(di)\prod_{0 \le i < N} p(d_i).✦ The bridge partition function Zbr(p,N)Z_{\mathrm{br}}(p, N) of length N∈ℕN \in \mathbb{N} under a critical even offspring distribution pp is the real sum (4): Zbr(p,N)=∑d∈ℬNwbr(p,d).Z_{\mathrm{br}}(p, N) = \sum_{d \in \mathcal{B}_N} w_{\mathrm{br}}(p, d).(4)✦

The valid tree code condition on a degree sequence d∈{0,…,N−1}Nd \in \{0, \dots, N - 1\}^N of length N∈ℕN \in \mathbb{N} is the requirement 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 N∈ℕN \in \mathbb{N} is a degree sequence in {0,…,N−1}N\{0, \dots, N - 1\}^N meeting the valid tree code condition, and 𝒞N\mathcal{C}_N denotes the set of all Lukasiewicz tree codes of length NN.✦ For a Lukasiewicz tree code d∈𝒞Nd \in \mathcal{C}_N of length N∈ℕN \in \mathbb{N} and a critical even offspring distribution pp, the tree code weight wcode(p,d)w_{\mathrm{code}}(p, d) is the real product ∏0≤i<Np(di)\prod_{0 \le i < N} p(d_i).✦ For a critical even offspring distribution pp and a natural number NN, the tree code partition function Zcode(p,N)Z_{\mathrm{code}}(p, N) is the real sum (5): Zcode(p,N)=∑d∈𝒞Nwcode(p,d).Z_{\mathrm{code}}(p, N) = \sum_{d \in \mathcal{C}_N} w_{\mathrm{code}}(p, d).(5)✦

The Claim

Theorem 1. Let pp be a critical even offspring distribution with offspring probability mass function νp\nu_p and offspring standard deviation σ\sigma. The tree code partition function along odd lengths 2n+12n + 1 satisfies (6): limn→∞(2n+1)2n+1Zcode(p,2n+1)=2σ2π.\lim_{n \to \infty} (2n + 1)\sqrt{2n + 1}\, Z_{\mathrm{code}}(p, 2n + 1) = \frac{2}{\sigma\sqrt{2\pi}}.(6)✦ For every integer N>0N > 0, the bridge and tree code partition functions are related by the cycle identity (7): Zbr(p,N)=NZcode(p,N).Z_{\mathrm{br}}(p, N) = N\, Z_{\mathrm{code}}(p, N).(7)✦ There exists a sequence (En)n≥0(E_n)_{n \ge 0} of nonnegative real numbers tending to 00 as n→∞n \to \infty such that, for every n∈ℕn \in \mathbb{N} and every integer j∈ℤj \in \mathbb{Z} with n+1+jn + 1 + j even, the uniform local bound (8) holds: |n+1νp⊗(n+1)({d∈ℕn+1:S(d)=j})−2πσπexp(−12(jσn+1)2)|≤En.\left| \sqrt{n + 1}\, \nu_p^{\otimes (n+1)}(\{d \in \mathbb{N}^{n+1} : S(d) = j\}) - \frac{\sqrt{2\pi}}{\sigma\pi} \exp\!\left(-\frac{1}{2}\left(\frac{j}{\sigma\sqrt{n + 1}}\right)^2\right) \right| \le E_n.(8)✦ Along odd lengths 2n+12n + 1, the bridge partition function satisfies (9): limn→∞2n+1Zbr(p,2n+1)=2πσπ.\lim_{n \to \infty} \sqrt{2n + 1}\, Z_{\mathrm{br}}(p, 2n + 1) = \frac{\sqrt{2\pi}}{\sigma\pi}.(9)✦

In the paper, the result reads: as NN tends to infinity through odd integers, πN:=ℙ(|T|=N)∼2σ2πN−3/2\pi_N := \mathbb{P}(|T| = N) \sim \frac{2}{\sigma\sqrt{2\pi}} N^{-3/2}, where TT is the critical even Galton-Watson tree and σ\sigma is its offspring standard deviation. The limit (6) replaces πN\pi_N by the tree code partition function Zcode(p,2n+1)Z_{\mathrm{code}}(p, 2n + 1) and expresses the asymptotic as the limit of a rescaled sequence along odd lengths N=2n+1N = 2n + 1 as n→∞n \to \infty.

What Is Checked

The claims are stated over a critical even offspring distribution pp with offspring probability mass function νp\nu_p, i.i.d. offspring product measure νp⊗N\nu_p^{\otimes N}, offspring distribution variance σ2\sigma^2, and offspring standard deviation σ\sigma, together with the total step S(d)S(d), the degree sequence partial walk Wj(d)W_j(d), discrete bridge sequences ℬN\mathcal{B}_N with bridge weights wbr(p,d)w_{\mathrm{br}}(p, d) and bridge partition function Zbr(p,N)Z_{\mathrm{br}}(p, N), and Lukasiewicz tree codes 𝒞N\mathcal{C}_N satisfying the valid tree code condition with tree code weights wcode(p,d)w_{\mathrm{code}}(p, d) and tree code partition function Zcode(p,N)Z_{\mathrm{code}}(p, N), for lengths N>0N > 0 and 2n+12n + 1 and integers n∈ℕn \in \mathbb{N} and j∈ℤj \in \mathbb{Z} with n+1+jn + 1 + j even.