OctoInformBeta

OpenAI preprint, September 2026 · §4. Random routing and independent tests

Lemma 4.1 [A default choice on the center path]: The routing depth controls survival for each fixed real center

Default avoidance has an exact probability.

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

A fixed real center reads bits from periodic dyadic grids as it follows a path through a finite router. Let M,d∈ℕM,d\in\mathbb N. The router’s child set is 𝒞={0,…,M}\mathcal C=\{0,\ldots,M\}, with nondefault children i<Mi<M and default child MM.✦ The total number of children is m=M+1m=M+1, where mm uses the paper’s convention.

A decision node PP is a finite child sequence shorter than dd✦, and a terminal path LL is a child sequence of length dd.✦ Their sets are 𝒩=⋃0≤k<d𝒞k,ℒ=𝒞d.\mathcal N=\bigcup_{0\le k<d}\mathcal C^k, \qquad \mathcal L=\mathcal C^d.(1) Choose selector resolutions bS:𝒩×{0,…,M−1}→ℕb_S:\mathcal N\times\{0,\ldots,M-1\}\to\mathbb N and terminal resolutions bT:ℒ→ℕb_T:\mathcal L\to\mathbb N on the sets in (1).

For real q,xq,x, the periodic mesh key Kq(x)K_q(x) is the floor of qq times the fractional part {x}=x−⌊x⌋\{x\}=x-\lfloor x\rfloor.✦ At level b∈ℕb\in\mathbb N, put Nb=2b+2N_b=2^{b+2}. The finite dyadic grid key κb(x)\kappa_b(x) is the integer index jj of the half-open cell [j/Nb,(j+1)/Nb)[j/N_b,(j+1)/N_b) containing {x}\{x\}: Kq(x)=⌊q{x}⌋,κb(x)=KNb(x)∈{0,…,Nb−1}.K_q(x)=\lfloor q\{x\}\rfloor, \qquad \kappa_b(x)=K_{N_b}(x)\in\{0,\ldots,N_b-1\}.(2)

The selector address set SS consists of triples recording a decision node, a nondefault child and a grid entry.✦ The terminal address set TT consists of pairs recording a terminal path and a grid entry: S={(P,i,j):P∈𝒩,i,j∈ℕ,i<M,j<2bS(P,i)+2},T={(L,j):L∈ℒ,j∈ℕ,j<2bT(L)+2}.\begin{aligned} S&=\{(P,i,j):P\in\mathcal N,\ i,j\in\mathbb N,\ i<M, \ j<2^{b_S(P,i)+2}\},\\ T&=\{(L,j):L\in\mathcal L,\ j\in\mathbb N, \ j<2^{b_T(L)+2}\}. \end{aligned}(3) A Boolean selector table is a function σ:S→{0,1}\sigma:S\to\{0,1\}✦, and a terminal Boolean table is a function τ:T→{0,1}\tau:T\to\{0,1\}, on the addresses in (3).✦ The outcome space Ω={0,1}S×{0,1}T\Omega=\{0,1\}^S\times\{0,1\}^T is the set of pairs consisting of a Boolean selector table and a terminal Boolean table.

For 0≤p≤10\le p\le1, the Bernoulli bit law βp\beta_p assigns mass pp to 11 and mass 1−p1-p to 00✦; the fair bit law is β1/2\beta_{1/2}.✦ The independent fair selector law μS\mu_S and the independent Bernoulli terminal law νT,p\nu_{T,p} combine to give the independent table outcome law ℙp\mathbb P_p: μS=⨂a∈Sβ1/2,νT,p=⨂a∈Tβp,ℙp=μS⊗νT,p.\mu_S=\bigotimes_{a\in S}\beta_{1/2}, \qquad \nu_{T,p}=\bigotimes_{a\in T}\beta_p, \qquad \mathbb P_p=\mu_S\otimes\nu_{T,p}.(4) Probability values and their numerical expressions are taken in [0,∞][0,\infty]; ι(a)\iota(a) denotes a nonnegative real aa viewed in this interval.

For a decision node PP and nondefault child ii, the queried selector address a(P,i,x)a(P,i,x) uses the key in (2). The extended selector value vσ(P,i;x)v_\sigma(P,i;x) is a bit defined for every finite child sequence PP: a(P,i,x)=(P,i,κbS(P,i)(x)),vσ(P,i;x)={σ(a(P,i,x)),|P|<d,0,|P|≥d.\begin{aligned} a(P,i,x)&=(P,i,\kappa_{b_S(P,i)}(x)),\\ v_\sigma(P,i;x)&= \begin{cases} \sigma(a(P,i,x)),& |P|<d,\\ 0,& |P|\ge d. \end{cases} \end{aligned}(5)

The first successful child c(f)c(f) of a Boolean vector f=(fi)i<Mf=(f_i)_{i<M} is its least successful index, with the default chosen if none succeeds.✦ The center first-success rule CxC_x, with xx fixed, and the pointwise first-success rule CσC_\sigma, with σ\sigma fixed, are child rules obtained by applying cc to the selector values in (5): c(f)=min⁡({i<M:fi=1}∪{M}),Cx(P,σ)=c((vσ(P,i;x))i<M),Cσ(P,x)=c((vσ(P,i;x))i<M).\begin{aligned} c(f)&=\min\bigl(\{i<M:f_i=1\}\cup\{M\}\bigr),\\ C_x(P,\sigma)&=c\bigl((v_\sigma(P,i;x))_{i<M}\bigr),\\ C_\sigma(P,x)&=c\bigl((v_\sigma(P,i;x))_{i<M}\bigr). \end{aligned}(6)

For a child rule χ(P,z)\chi(P,z) and a state zz, the iterated routing path Rχ(k,P;z)R_\chi(k,P;z) starts from PP and successively appends the selected child.✦ For a finite child sequence QQ and a child ii, write Q⌢[i]Q\frown[i] for appending ii to QQ; the iterated routing path is defined by Rχ(0,P;z)=P,Rχ(k+1,P;z)=Rχ(k,P;z)⌢[χ(Rχ(k,P;z),z)].\begin{aligned} R_\chi(0,P;z)&=P,\\ R_\chi(k+1,P;z)&=R_\chi(k,P;z) \frown[\chi(R_\chi(k,P;z),z)]. \end{aligned}(7) With ⌀\varnothing the empty path, the rules in (6) give the center route Pˆkx(σ)=RCx(k,⌀;σ)\widehat P_k^x(\sigma)=R_{C_x}(k,\varnothing;\sigma) and the pointwise route Pkσ(x)=RCσ(k,⌀;x)P_k^\sigma(x)=R_{C_\sigma}(k,\varnothing;x) through (7). The default avoidance event Ex⊆ΩE_x\subseteq\Omega consists of the table pairs whose center route takes no default child before depth dd: Ex={(σ,τ)∈Ω:Cx(Pˆkx(σ),σ)≠M for every 0≤k<d}.E_x=\{(\sigma,\tau)\in\Omega: C_x(\widehat P_k^x(\sigma),\sigma)\ne M \text{ for every }0\le k<d\}.(8)✦

The Claim

Theorem 1. Let M,dM,d be natural numbers, let bS,bTb_S,b_T be arbitrary selector and terminal resolutions, and fix a real center xx. For 0≤p≤10\le p\le1, the outcome law (4) assigns to the event (8) the probability ℙp(Ex)=(1−2−M)d.\mathbb P_p(E_x)=(1-2^{-M})^d.(9)✦ The event also has the pointwise routing description Ex={(σ,τ)∈Ω:Cσ(Pkσ(x),x)≠M for every 0≤k<d}.E_x=\{(\sigma,\tau)\in\Omega: C_\sigma(P_k^\sigma(x),x)\ne M \text{ for every }0\le k<d\}.(10)✦ For any positive real pp, if the real power (1−2−M)d(1-2^{-M})^d is less than pp, then the corresponding extended nonnegative power satisfies (1−(12)M)d<ι(p).\left(1-\left(\frac12\right)^M\right)^d<\iota(p).(11)✦

In the paper, the result reads: for every fixed real center xx, the probability that its route never chooses child mm is (1−21−m)d<p(1-2^{1-m})^d<p, with the previously chosen tree parameters and mm denoting its total number of children.

What Is Checked

The identities (9) and (10) are stated over arbitrary finite routers and resolution assignments, fixed real centers and the independent table laws with p∈[0,1]p\in[0,1]; the numerical bound (11) is stated for any positive real pp satisfying the real inequality preceding (11).