OctoInformBeta

OpenAI preprint, September 2026 · §6. A common sampling schedule

Lemma 6.1: How far the schedule moves time, at what entropy cost, and what a shift by a≤na \le n changes after a uniform offset on {0,…,n}\{0, \dots, n\}

Shift bounds and smoothing for the common sampling schedule.

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 walk z0,z1,…z_0, z_1, \dots of Gaussian integers with steps at most DD, observed at a random time t*t^* reached from a starting time by a run of random advances, each read off from the differences of a stretch of the walk, and a final uniform offset. The question is how far past the start t*t^* can lie, and what the displacement of the walk over that stretch costs in entropy. When the final offset is uniform on {0,…,n}\{0, \dots, n\}, a second question is how much a further shift by a≤na \le n steps can change the probability of an event, or a conditional entropy, observed at that time.

Laws and Entropy

A finite probability law pp on a finite set Ω\Omega is a function p:Ω→ℝp \colon \Omega \to \mathbb{R} with p(ω)≥0p(\omega) \ge 0 for every ω\omega and ∑ω∈Ωp(ω)=1\sum_{\omega \in \Omega} p(\omega) = 1. The probability Pr⁡p[E]\Pr_p[E] of a property EE of the points of Ω\Omega is the total mass ∑ω:E(ω)p(ω)\sum_{\omega : E(\omega)} p(\omega) of the points where it holds.✦ The uniform law on a nonempty finite set Ω\Omega gives every element of Ω\Omega the mass 1/|Ω|1/|\Omega|; write UnU_n for the uniform law on {0,…,n}\{0, \dots, n\}.✦

The pushforward f*pf_* p of pp along a map ff from Ω\Omega to a finite set β\beta is the finite probability law on β\beta that gives each point bb the mass ∑f(ω)=bp(ω)\sum_{f(\omega) = b} p(\omega) of its preimage; for a random variable XX on Ω\Omega, the law of XX is X*pX_* p. Given a finite probability law pp on a finite set ι\iota and, for each i∈ιi \in \iota, a finite probability law q(⋅∣i)q(\cdot \mid i) on Ω\Omega, the joint law p⊗qp \otimes q is the finite probability law on ι×Ω\iota \times \Omega with mass p(i)q(ω∣i)p(i)\, q(\omega \mid i) at (i,ω)(i, \omega), the law of a pair drawn by taking ii from pp and then ω\omega from q(⋅∣i)q(\cdot \mid i).✦

The entropy of a finite probability law pp on a finite set α\alpha is the Shannon sum H(p)=−∑u∈αp(u)log⁡p(u),H(p) = -\sum_{u \in \alpha} p(u) \log p(u),(1)✦ with 0log⁡0=00 \log 0 = 0. For random variables XX and YY on Ω\Omega with values in finite sets α\alpha and β\beta, the entropy H(X)H(X) is the entropy of the law of XX✦, and the conditional entropy of XX given YY is H(X∣Y)=H(X,Y)−H(Y),H(X \mid Y) = H(X, Y) - H(Y),(2)✦ where H(X,Y)H(X, Y) is the entropy of the pair ω↦(X(ω),Y(ω))\omega \mapsto (X(\omega), Y(\omega)).

Forward Kernels and the Common Schedule

A forward kernel KK consists of a natural number BKB_K, its bound, and for every time r∈ℕr \in \mathbb{N} a finite probability law KrK_r on {0,…,BK}\{0, \dots, B_K\}, the law of the advance taken from time rr. The composite K⊳RK \triangleright R of forward kernels KK and RR is the forward kernel of bound BK+BRB_K + B_R whose law at time rr is that of the sum of offsets i+ji + j, with ii drawn from KrK_r and then jj from Rr+iR_{r+i}: (K⊳R)r(m)=∑i+j=mKr(i)Rr+i(j).(K \triangleright R)_r(m) = \sum_{i + j = m} K_r(i)\, R_{r+i}(j).(3)✦ The smoothing kernel 𝒰N\mathcal{U}_N of window NN is the forward kernel of bound NN whose law at every time is UNU_N.✦

Let zz be a walk of Gaussian integers and n≥0n \ge 0. The walk segment Zn={z0,…,zn}Z_n = \{z_0, \dots, z_n\} is the set of points the walk visits up to time nn. The difference set F−FF - F of a finite set FF of Gaussian integers is the set of all differences u−wu - w with u,w∈Fu, w \in F.✦ The difference representative of an element dd of Zn−ZnZ_n - Z_n is a pair (i,j)(i, j) of times in {0,…,n}\{0, \dots, n\} with zi−zj=dz_i - z_j = d, chosen once and for all✦, and the difference law of zz over nn steps is the finite probability law on such pairs obtained by drawing dd uniformly from Zn−ZnZ_n - Z_n and returning its representative.✦

The difference kernel Δn\Delta_n of zz with window nn is the forward kernel of bound nn whose law at time rr is that of the following advance: toss a fair coin, draw (i,j)(i, j) from the difference law of the shifted walk t↦zr+tt \mapsto z_{r+t} over nn steps, and advance by ii on heads and by jj on tails.✦ Given segment lengths n1,…,nkn_1, \dots, n_k and an offset window NN, the common schedule of zz is the forward kernel Δn1⊳(Δn2⊳(⋯⊳(Δnk⊳𝒰N)⋯))\Delta_{n_1} \triangleright \bigl(\Delta_{n_2} \triangleright \bigl(\cdots \triangleright (\Delta_{n_k} \triangleright \mathcal{U}_N) \cdots \bigr)\bigr)(4)✦ of difference transitions followed by a uniform offset. The terminal time t*t^* of the common schedule of zz started at time rr is r+mr + m, where mm is the advance drawn from the law of the schedule at rr.

The Claim

Theorem 1. Let zz be a walk of Gaussian integers, let n1,…,nkn_1, \dots, n_k and NN be natural numbers, and let SS be the bound of the common schedule of zz with segment lengths n1,…,nkn_1, \dots, n_k and offset window NN. Then S=n1+…+nk+N.S = n_1 + \dots + n_k + N.(5)✦ If moreover xx is a real number with ni≤exn_i \le e^x for every ii, N≤exN \le e^x and k+2≤exk + 2 \le e^x, then log⁡(1+S)≤2x.\log(1 + S) \le 2x.(6)✦

Let DD, gg, VV and LL be real numbers and qq and SS natural numbers, with D≥1D \ge 1, g≥0g \ge 0, S≥1S \ge 1, V/2≤qLV/2 \le qL, log⁡(1+S)≤2gV\log(1 + S) \le 2gV and log⁡36+2log⁡D≤gV\log 36 + 2\log D \le gV. Then log⁡36+2log⁡(DS)≤10gqL.\log 36 + 2\log(DS) \le 10\, g q L.(7)✦

Let pp be a finite probability law on a finite set Ω\Omega, t:Ω→ℕt \colon \Omega \to \mathbb{N} a random time, and a≤na \le n natural numbers. Draw (ω,s)(\omega, s) from p⊗Unp \otimes U_n, so that the offset ss is uniform on {0,…,n}\{0, \dots, n\} and independent of ω\omega, and put τ=t(ω)+s\tau = t(\omega) + s; probabilities and entropies are taken under this law. For every set EE of natural numbers, Pr⁡[τ∈E]≤Pr⁡[τ+a∈E]+an+1,\Pr[\tau \in E] \le \Pr[\tau + a \in E] + \frac{a}{n+1},(8)✦ and for all sequences (Xm)(X_m) and (Cm)(C_m) with values in finite sets α\alpha and β\beta, H(Xτ+a∣Cτ+a)≤H(Xτ∣Cτ)+2h(an+1)+an+1(log⁡|α|+2log⁡|β|),H(X_{\tau+a} \mid C_{\tau+a}) \le H(X_\tau \mid C_\tau) + 2h\Bigl(\frac{a}{n+1}\Bigr) + \frac{a}{n+1}\bigl(\log|\alpha| + 2\log|\beta|\bigr),(9)✦ where hh is the binary entropy.

In the paper, the result reads: for a scheduled scale VV in a band with parameter gg and all sufficiently large MM, the total forward shift from the checkpoint before VV to any later checkpoint is at most a deterministic SVS_V with log⁡(1+SV)≤2gV\log(1 + S_V) \le 2gV, so that its displacement has entropy OD(gV)O_D(gV), and from any earlier exact start the total variation distance between the laws of t*t^* and t*+at^* + a is at most T+−9T_+^{-9} for all integers 0≤a≤T+0 \le a \le T_+.

In the library, the bound SS of (5) plays the part of SVS_V, and the smoothing inequalities (8) and (9) stand in place of the total variation bound.

What Is Checked

The claim is stated over the common schedule (4) of a walk of Gaussian integers, composed by (3) from the smoothing kernel and from difference kernels built on the difference law of a walk segment and its difference set; and over the joint law p⊗Unp \otimes U_n of a finite probability law and the uniform law on offsets, with the probability of an event and the conditional entropy (2) taken under it. About these constructions the library proves that every difference of a walk segment is realised by a pair of times: for each d∈Zn−Znd \in Z_n - Z_n there are i,j∈{0,…,n}i, j \in \{0, \dots, n\} with zi−zj=dz_i - z_j = d.✦