OctoInformBeta

OpenAI preprint, September 2026 · §4. Conditioning on block types

Lemma 4.1: Finite conditional laws satisfy mean entropy bounds and, under an entropy gap, linear retained loss

Block types control the loss of translation entropy.

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

Conditioning on block types records the symbol counts in successive blocks of an affine random walk. The question is how much randomness remains in the translation after these counts are known.

A weighted affine iterated function system on a finite alphabet II consists of maps φi\varphi_i with signed slopes rir_i, real translations tit_i, and weights pip_i satisfying (1): φi(x)=rix+ti,0<|ri|<1,pi>0,∑i∈Ipi=1.\varphi_i(x)=r_i x+t_i,\qquad 0<|r_i|<1,\qquad p_i>0,\qquad \sum_{i\in I}p_i=1.(1)✦ A self-similar probability measure μ\mu for this system is a probability measure on ℝ\mathbb R satisfying (2): μ=∑i∈Ipi(φi)*μ.\mu=\sum_{i\in I}p_i(\varphi_i)_*\mu.(2)✦

For a word w=(w0,…,wm−1)∈Imw=(w_0,\ldots,w_{m-1})\in I^m, its complete affine map φw\varphi_w and word probability pwp_w are the affine map and real number given by (3); the empty word has complete map (1,0)(1,0): φw=φw0∘⋯∘φwm−1,φw(x)=Rwx+Tw,pw=∏j=0m−1pwj.\varphi_w=\varphi_{w_0}\circ\cdots\circ\varphi_{w_{m-1}},\qquad \varphi_w(x)=R_wx+T_w,\qquad p_w=\prod_{j=0}^{m-1}p_{w_j}.(3) The random complete map Gm=(Rm,Tm)G_m=(R_m,T_m) is obtained by choosing ww with probability pwp_w. The attainable set 𝒢m\mathcal G_m of the random complete map GmG_m is the set of complete affine maps of words of length mm, and its mass function mmm_m assigns each map its total word probability, as in (4); collisions require equality of both signed slope and translation: 𝒢m={(Rw,Tw):w∈Im},mm(g)=∑w∈Im(Rw,Tw)=gpw.\mathcal G_m=\{(R_w,T_w):w\in I^m\},\qquad m_m(g)=\sum_{\substack{w\in I^m\\(R_w,T_w)=g}}p_w.(4) The map-walk entropy HmH_m, its rate hh, and the positive Lyapunov exponent χ\chi use base-two logarithms, as in (5): Hm=−∑g∈𝒢mmm(g)log⁡2mm(g),h=infm≥1Hmm,χ=−∑i∈Ipilog⁡2|ri|.H_m=-\sum_{g\in\mathcal G_m}m_m(g)\log_2m_m(g),\qquad h=\inf_{m\ge1}\frac{H_m}{m},\qquad \chi=-\sum_{i\in I}p_i\log_2|r_i|.(5)

The block type Bb,n(w)B_{b,n}(w) of a word of length bnbn is the sequence of symbol-count vectors in its nn consecutive blocks of length bb, defined by (6).✦ Let WW be a random word of length bnbn, chosen with word probabilities pwp_w, and write Ωb,n=Bb,n(W)\Omega_{b,n}=B_{b,n}(W) for its block type and k=|I|k=|I|. Bb,n(w)j,i=#{0≤ℓ<b:wjb+ℓ=i},0≤j<n,i∈I.B_{b,n}(w)_{j,i} =\#\{0\le \ell<b:w_{jb+\ell}=i\},\qquad 0\le j<n,\ i\in I.(6)

Conditional Laws and Entropies

For real weights axa_x on a finite set XX and an observable f:X→Yf:X\to Y, the observable entropy ℋa(f)\mathcal H_a(f) is the Shannon entropy in nats of its fiber masses; the weights used for the conditional probability laws below are strictly positive.✦ The conditional observable entropy ℋa(f∣τ)\mathcal H_a(f\mid\tau) of an observable f:X→Yf:X\to Y given a tag τ:X→Z\tau:X\to Z is the difference between the joint observable entropy and the tag entropy, as in (7): ma(f,y)=∑x∈Xf(x)=yax,ℋa(f)=−∑y∈f(X)ma(f,y)ln⁡ma(f,y),ℋa(f∣τ)=ℋa((f,τ))−ℋa(τ).\begin{aligned} m_a(f,y)&=\sum_{\substack{x\in X\\f(x)=y}}a_x,\\ \mathcal H_a(f)&=-\sum_{y\in f(X)}m_a(f,y)\ln m_a(f,y),\\ \mathcal H_a(f\mid\tau)&=\mathcal H_a((f,\tau))-\mathcal H_a(\tau). \end{aligned}(7) The weights need not sum to one. For random variables, ℋ\mathcal H uses their joint law, and H=ℋ/ln⁡2H=\mathcal H/\ln2 denotes entropy in bits. For x∈Xx\in X, the tag fiber FxF_x is the subset of XX with tag τ(x)\tau(x)✦, its mass MxM_x is the sum of its weights✦, and qxq_x is the normalized weight function on FxF_x given in (8): Fx={v∈X:τ(v)=τ(x)},Mx=∑v∈Fxav,qx(v)=avMx.F_x=\{v\in X:\tau(v)=\tau(x)\},\qquad M_x=\sum_{v\in F_x}a_v,\qquad q_x(v)=\frac{a_v}{M_x}.(8) A finite probability law λ\lambda on ℝ\mathbb R has finite support with strictly positive point masses summing to one.✦ For a real observable ff, its conditional observable law λx\lambda_x and the entropy in bits of a finite law are given by (9), where δz\delta_z denotes the probability measure concentrated at zz: λx=∑v∈Fxqx(v)δf(v),H(λ)=−∑z∈supp⁡λλ{z}log⁡2λ{z}.\lambda_x=\sum_{v\in F_x}q_x(v)\delta_{f(v)},\qquad H(\lambda)=-\sum_{z\in\operatorname{supp}\lambda} \lambda\{z\}\log_2\lambda\{z\}.(9) Zero masses contribute zero to every entropy sum. The observable distribution of a real observable on a finite probability space is the finitely supported probability law whose mass at each value is the sum of the weights of all source points taking that value.✦

Let JJ be a finite type alphabet of size qq, and let τ:I→J\tau:I\to J be a tag. For a word w∈Inw\in I^n, its word of types τn(w)\tau_n(w) is the sequence defined by τn(w)=(τ(w0),…,τ(wn−1))\tau_n(w)=(\tau(w_0),\ldots,\tau(w_{n-1})).✦ Applying the conditional law in (9) with X=InX=I^n, weights pvp_v, tag τn\tau_n and observable v↦Tvv\mapsto T_v defines the type-conditioned translation law νw\nu_w.✦ For a real function FF on InI^n and a random word WW of length nn with word probabilities pwp_w, write 𝔼nF(W)=∑w∈InpwF(w)\mathbb E_n F(W)=\sum_{w\in I^n}p_wF(w). This conditioning fixes only the first nn types; future symbols remain unconditioned.

For a measure η\eta and a discrete observable ff, the partition entropy ℋη(f)\mathcal H_\eta(f) is the entropy in nats of its real fiber masses, as in (10): mη(f,y)=η(f−1{y}),ℋη(f)=−∑ymη(f,y)ln⁡mη(f,y).m_\eta(f,y)=\eta(f^{-1}\{y\}),\qquad \mathcal H_\eta(f)=-\sum_y m_\eta(f,y)\ln m_\eta(f,y).(10)✦ For real parameters s,us,u, the shifted grid index ks,uk_{s,u} is the integer-valued function on ℝ\mathbb R given in (11), and the grid entropy ℋsu(η)\mathcal H_s^u(\eta) is its partition entropy under a measure η\eta on ℝ\mathbb R; the entropy bounds use positive scales. Here HsuH_s^u is measured in bits, whereas ℋsu\mathcal H_s^u and the averaged grid entropy ℋ¯\overline{\mathcal H} are in nats. ks,u(x)=⌊x/s+u⌋,ℋsu(η)=ℋη(ks,u),Hsu(η)=ℋsu(η)ln⁡2,ℋ¯(η,s)=∫01ℋsu(η)du.\begin{aligned} k_{s,u}(x)&=\lfloor x/s+u\rfloor,\qquad \mathcal H_s^u(\eta)=\mathcal H_\eta(k_{s,u}),\qquad H_s^u(\eta)=\frac{\mathcal H_s^u(\eta)}{\ln2},\\ \overline{\mathcal H}(\eta,s)&=\int_0^1\mathcal H_s^u(\eta)\,du. \end{aligned}(11)

A measure μ\mu on ℝ\mathbb R is compactly supported when some B≥0B\ge0 satisfies μ(ℝ\[−B,B])=0\mu(\mathbb R\setminus[-B,B])=0.✦

For a word w∈Inw\in I^n and real parameters A,A′A,A', the contraction depth d(w)d(w) and fine scale sns_n are the real numbers given in (12). The entropy loss ℓs(w)\ell_s(w) of a word w∈Inw\in I^n at a scale s>0s>0 is the difference between Shannon and grid entropy of νw\nu_w in nats. The retained loss LnL_n is the sum of the entropy losses ℓsn(w)\ell_{s_n}(w), weighted by pwp_w, over words w∈Inw\in I^n whose contraction depth is at most A′nA'n. d(w)=−log⁡2|Rw|,sn=2−⌈An⌉,ℓs(w)=(ln⁡2)(H(νw)−Hs0(νw)),Ln=∑w∈Ind(w)≤A′npwℓsn(w).\begin{aligned} d(w)&=-\log_2|R_w|,\qquad s_n=2^{-\lceil An\rceil},\\ \ell_s(w)&=(\ln2)\bigl(H(\nu_w)-H_s^0(\nu_w)\bigr),\\ L_n&=\sum_{\substack{w\in I^n\\d(w)\le A'n}}p_w\ell_{s_n}(w). \end{aligned}(12)

The Claim

Theorem 1. For every weighted affine system, the block translation entropy satisfies (13) for integers b,n≥0b,n\ge0: ℋ(Tbn∣Ωb,n)≥Hbnln⁡2−nkln⁡(b+1).\mathcal H(T_{bn}\mid\Omega_{b,n}) \ge H_{bn}\ln2-nk\ln(b+1).(13)✦ For integers b,n≥1b,n\ge1, the entropy-rate bound is (14): ℋ(Tbn∣Ωb,n)≥n(bhln⁡2−kln⁡(b+1)).\mathcal H(T_{bn}\mid\Omega_{b,n}) \ge n\bigl(bh\ln2-k\ln(b+1)\bigr).(14)✦ For the positive finite weights and observables of (7), conditional entropy is the mean in (15): ∑x∈Xaxℋqx(f)=ℋa(f∣τ).\sum_{x\in X}a_x\mathcal H_{q_x}(f)=\mathcal H_a(f\mid\tau).(15)✦

Suppose the tag τ:I→J\tau:I\to J has constant signed slope on each type: ri=rjr_i=r_j whenever τ(i)=τ(j)\tau(i)=\tau(j). For every integer n≥0n\ge0, the mean translation entropy satisfies (16): 𝔼nH(νW)≥Hn−nlog⁡2q.\mathbb E_n H(\nu_W)\ge H_n-n\log_2q.(16)✦ If μ\mu is a compactly supported self-similar probability measure, then for every n≥0n\ge0 and s>0s>0 the mean grid bound is (17): 𝔼nHs0(νW)≤Hs0(μ)+1.\mathbb E_n H_s^0(\nu_W)\le H_s^0(\mu)+1.(17)✦

For retained loss, let μ\mu be a self-similar probability measure and let De≥0D_{\mathrm e}\ge0, C∈ℝC\in\mathbb R, A>0A>0 and A′>χA'>\chi. Suppose the averaged entropy bound and strict gap in (18) hold; DeD_{\mathrm e} is the entropy coefficient: ℋ¯(μ,s)≤Deln⁡(1/s)+C(0<s<1),DeAln⁡2<hln⁡2−ln⁡q.\overline{\mathcal H}(\mu,s) \le D_{\mathrm e}\ln(1/s)+C\quad(0<s<1),\qquad D_{\mathrm e}A\ln2<h\ln2-\ln q.(18) There are ε>0\varepsilon>0 and an integer N≥1N\ge1 such that (19) holds: Ln≥εn(n≥N).L_n\ge\varepsilon n\qquad(n\ge N).(19)✦

In the paper, under the system, deficit hypothesis, parameters and conditional laws of the preceding setting, with block length bb, block entropy parameter hbh_b, retained events EnE_n and scales ρn\rho_n, the result reads: for every n≥1n\ge1 and s>0s>0, 𝔼H(νω,n)=H(Gbn∣Ωn)≥nhb\mathbb E H(\nu_{\omega,n})=H(G_{bn}\mid\Omega_n)\ge nh_b and 𝔼Hs0(νω,n)≤Hs0(μ)+1\mathbb E H_s^0(\nu_{\omega,n})\le H_s^0(\mu)+1, where Ωn\Omega_n is the first nn types and the laws νω,n\nu_{\omega,n} condition on the entire infinite type environment ω\omega, and there are ε>0\varepsilon>0 and an integer n0n_0 such that 𝔼[𝟏En(H(νω,n)−Hρn0(νω,n))]≥εn\mathbb E[\mathbf 1_{E_n}(H(\nu_{\omega,n})-H_{\rho_n}^0(\nu_{\omega,n}))] \ge\varepsilon n for every n≥n0n\ge n_0.

What Is Checked

The statements concern finite weighted affine systems and their conditional observable laws, with compact support for the self-similar measure in the grid bound and the averaged entropy and gap assumptions for retained loss.

Every word has strictly positive probability✦, and for strictly positive weights on a finite set the normalized weights on each tag fiber sum to one.✦