OctoInformBeta

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

§4 (setting): selector tables, terminal tables, and the routed set: Finite selector tables route points to dyadic terminal cells

Independent terminal labels fix the expected density.

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 finite router assigns each real point to a leaf and reads a Boolean label from a cell of the dyadic grid at that leaf. For a set B⊆ℝB\subseteq\mathbb R, its density in one period is the quantity ρ(B)\rho(B) in (1), where λ\lambda is Lebesgue measure: ρ(B)=λ(B∩[0,1]).\rho(B)=\lambda(B\cap[0,1]).(1)

Fix nonnegative integers MM and dd. The child set CC consists of the indices 0,…,M0,\ldots,M, with MM the default child.✦ A decision node u∈𝒩u\in\mathcal N is a word in CC of length less than dd✦; a terminal path ℓ∈ℒ\ell\in\mathcal L is a word of length dd.✦ C={0,…,M},𝒩=⋃r<dCr,ℒ=Cd.C=\{0,\ldots,M\},\qquad \mathcal N=\bigcup_{r<d}C^r,\qquad \mathcal L=C^d.(2) Here MM counts nondefault children, so the total number of children, denoted MM in the paper, is M+1M+1.

For a real mesh parameter qq and a real point xx, the periodic mesh key kq(x)k_q(x) is the integer obtained by taking the floor of qq times the fractional part {x}\{x\} of xx.✦ The dyadic key Jb(x)J_b(x) of a real point xx at a natural-number level bb is the integer obtained by specializing the periodic mesh key as in (3); its grid cells are half-open and include their left endpoints: kq(x)=⌊q{x}⌋,Jb(x)=k2b+2(x)∈{0,…,2b+2−1}.k_q(x)=\lfloor q\{x\}\rfloor,\qquad J_b(x)=k_{2^{b+2}}(x)\in\{0,\ldots,2^{b+2}-1\}.(3)✦

A selector level assignment bSb_S assigns a natural number to each pair (u,i)(u,i) with u∈𝒩u\in\mathcal N and i<Mi<M; a terminal level assignment bTb_T assigns a natural number to each ℓ∈ℒ\ell\in\mathcal L. For selector and terminal level assignments bS,bTb_S,b_T, the selector and terminal address sets SS and TT are the finite sets in (4): S={(u,i,j):u∈𝒩,0≤i<M,0≤j<2bS(u,i)+2},T={(ℓ,j):ℓ∈ℒ,0≤j<2bT(ℓ)+2}.\begin{split} S&=\{(u,i,j):u\in\mathcal N,\ 0\leq i<M,\ 0\leq j<2^{b_S(u,i)+2}\},\\ T&=\{(\ell,j):\ell\in\mathcal L,\ 0\leq j<2^{b_T(\ell)+2}\}. \end{split}(4) A selector table σ\sigma is a Boolean function on SS✦, and a terminal table τ\tau is a Boolean function on TT✦; write their entries as σu,i(j)\sigma_{u,i}(j) and τℓ(j)\tau_\ell(j). For u∈𝒩u\in\mathcal N, 0≤i<M0\leq i<M, ℓ∈ℒ\ell\in\mathcal L and x∈ℝx\in\mathbb R, the queried selector address aS(u,i,x)∈Sa_S(u,i,x)\in S and terminal address aT(ℓ,x)∈Ta_T(\ell,x)\in T are the tuples in (5): aS(u,i,x)=(u,i,JbS(u,i)(x)),aT(ℓ,x)=(ℓ,JbT(ℓ)(x)).a_S(u,i,x)=(u,i,J_{b_S(u,i)}(x)),\qquad a_T(\ell,x)=(\ell,J_{b_T(\ell)}(x)).(5) For a selector table σ\sigma on SS, a finite word uu in CC, a child index 0≤i<M0\leq i<M and a real point xx, the extended selector value vσ(u,i,x)v_\sigma(u,i,x) is the Boolean value in (6): vσ(u,i,x)={σ(aS(u,i,x)),|u|<d,0,|u|≥d.v_\sigma(u,i,x)= \begin{cases} \sigma(a_S(u,i,x)),& |u|<d,\\ 0,& |u|\geq d. \end{cases}(6)✦

The first successful child c(s)∈Cc(s)\in C for a list of bits s=(s0,…,sM−1)s=(s_0,\ldots,s_{M-1}) is the minimum in (7): c(s)=min⁡({i<M:si=1}∪{M}).c(s)=\min\bigl(\{i<M:s_i=1\}\cup\{M\}\bigr).(7)✦ A child rule χ\chi assigns a child in CC to each finite word in CC and each real point. For a finite word uu in CC and a real point xx, the iterated routing path Rnχ(u,x)R_n^\chi(u,x) after n≥0n\geq0 steps is the word obtained by the recursion (8), where ⌢\frown denotes concatenation: R0χ(u,x)=u,Rn+1χ(u,x)=Rnχ(u,x)⌢[χ(Rnχ(u,x),x)].R_0^\chi(u,x)=u,\qquad R_{n+1}^\chi(u,x)=R_n^\chi(u,x)\frown [\chi(R_n^\chi(u,x),x)].(8)✦

For an address map a:E×ℝ→Ka:E\times\mathbb R\to K, an element e∈Ee\in E and a Boolean table tt on KK, the address-selected set 𝒮(a;e,t)\mathcal S(a;e,t) is the subset of ℝ\mathbb R defined in (9): 𝒮(a;e,t)={x∈ℝ:t(a(e,x))=1}.\mathcal S(a;e,t)=\{x\in\mathbb R:t(a(e,x))=1\}.(9)✦

For 0≤p≤10\leq p\leq1, the Bernoulli bit law βp\beta_p on {0,1}\{0,1\} assigns mass pp to 11 and 1−p1-p to 00✦; β1/2\beta_{1/2} is the fair bit law.✦ For 0≤p≤10\leq p\leq1, the independent fair selector law QSQ_S on selector tables and the independent Bernoulli terminal law QT,pQ_{T,p} on terminal tables are the product probability measures in (10): QS=⨂s∈Sβ1/2,QT,p=⨂t∈Tβp.Q_S=\bigotimes_{s\in S}\beta_{1/2},\qquad Q_{T,p}=\bigotimes_{t\in T}\beta_p.(10)

The Claim

Theorem 1. Let bS,bTb_S,b_T be level assignments as above, let 0≤p≤10\leq p\leq1, and let μ\mu and ν\nu be probability measures on selector tables and on {0,1}\{0,1\}, respectively. The joint table law ℙp\mathbb P_p on pairs of tables is the product measure in (11): ℙp=QS⊗QT,p.\mathbb P_p=Q_S\otimes Q_{T,p}.(11)✦ For a selector table σ\sigma, the selector child choice χσ\chi_\sigma is the child rule in (12), and the routed leaf LσL_\sigma is the function from ℝ\mathbb R to ℒ\mathcal L in (13), with routing starting at the empty word ⌀\varnothing: χσ(u,x)=c((vσ(u,i,x))0≤i<M).\chi_\sigma(u,x)=c\bigl((v_\sigma(u,i,x))_{0\leq i<M}\bigr).(12)✦ Lσ(x)=Rdχσ(⌀,x)∈ℒ.L_\sigma(x)=R_d^{\chi_\sigma}(\varnothing,x)\in\mathcal L.(13)✦ For a pair of tables ω=(σ,τ)\omega=(\sigma,\tau) and a real point xx, the routed terminal address a(σ,x)∈Ta(\sigma,x)\in T and the routed set Bω⊆ℝB_\omega\subseteq\mathbb R are given by (14): a(σ,x)=aT(Lσ(x),x),Bω=𝒮(a;σ,τ).a(\sigma,x)=a_T(L_\sigma(x),x),\qquad B_\omega=\mathcal S(a;\sigma,\tau).(14) Every realization ω\omega gives a Borel, one-periodic routed set BωB_\omega satisfying (15) and (16), where ℬ(ℝ)\mathcal B(\mathbb R) is the Borel sigma algebra: Bω∈ℬ(ℝ).B_\omega\in\mathcal B(\mathbb R).(15)✦ x+1∈Bω⇔x∈Bω.x+1\in B_\omega\quad\Longleftrightarrow\quad x\in B_\omega.(16)✦ With the selector and terminal laws μ\mu and ν\nu, the density identity is (17): ∫ρ(Bω)d(μ⊗⨂t∈Tν)(ω)=ν({1}).\int \rho(B_\omega)\, d\left(\mu\otimes\bigotimes_{t\in T}\nu\right)(\omega)=\nu(\{1\}).(17)✦

In the paper, the result reads: each nondefault edge ee carries independent fair Boolean selector entries indexed by the dyadic cells at level beb_e, each leaf ℓ\ell carries independent Bernoulli-pp terminal entries indexed by the cells at the endpoint b(ℓ)b(\ell) of its incoming edge, all entries are mutually independent, routing chooses the first successful nondefault child and otherwise the last child, and, writing L(z)L(z) for the routed leaf, the set B={z:τL(z)(Jb(L(z))(z))=1}B=\{z:\tau_{L(z)}(J_{b(L(z))}(z))=1\} is measurable and one-periodic in every realization with 𝔼ρ(B)=p\mathbb E\rho(B)=p.

What Is Checked

The construction is stated for every M,d≥0M,d\geq0 and every pair of natural-number level assignments bS,bTb_S,b_T, while (17) permits an arbitrary selector probability law and independent terminal bits with a common probability law ν\nu.