OctoInform Beta

OpenAI preprint, September 2026 · §7. Bit complexity · §7

§7 (proof of Theorem 7.1): generating bits: A copying loop between two phases without coins reads every tape bit, and blocks of log⁡2s\log_2 s bits decode to independent uniform indices below ss

The solver reads all its random bits first.

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

The randomized solver for mean-payoff games amplifies twice: it takes the coordinatewise median of JJ trials of a recursive call, and the strict majority of JJ trials of an orientation, a choice of YY or ZZ. Here ss, a power of two, is the number of iterates among which the solver chooses and JJ is the number of trials of either amplification; both are global parameters of the solver, fixed by the game. Run on a machine with a random tape, the solver consumes fair bits, and the question is how many it reads and when, and with what law the random indices it uses come out of them.

In the library the solver is one program in three phases. A preparation phase reads the input code ⟨G⟩\langle G\rangle of the game GG, a binary string of length LL, and computes how many bits to draw; a copying loop moves that many bits from the tape into a register; a post phase cuts the register into blocks, reads each block as a number, runs the solver’s control machine, the part of the solver that carries out the two amplifications, on these numbers and writes out its answer.

Fair Bits and Blocks

A random tree over a set XX is a finite binary tree whose internal nodes flip a fair coin and whose leaves carry elements of XX. Walking down it reads one bit per coin; its depth is the largest number of coins on a branch, and for a rational-valued function ff on XX, 𝔼τf\mathbb{E}_\tau f is the expectation of ff at the leaf reached. For a map gg on XX, the image g*τg_*\tau is the random tree τ\tau with every leaf xx relabelled g(x)g(x).

The fair bit draw ℬk\mathcal{B}_k is the random tree that flips kk fair coins and returns the string of their outcomes in the order flipped.✦ For a bit string β\beta, val(β)\mathrm{val}(\beta) is the number β\beta spells in binary. The uniform draw 𝒰k\mathcal{U}_k is the random tree that draws an index uniformly from {0,…,2k−1}\{0,\dots,2^k-1\}. For a block length ℓ\ell and a count NN, the sample draw 𝒮ℓ,N\mathcal{S}_{\ell,N} is the random tree that draws NN indices one after another, each by 𝒰ℓ\mathcal{U}_\ell, and returns the list of them in the order drawn, each in unary.✦

For a block length ℓ\ell, a count NN and a bit string β\beta of length at least ℓN\ell N, let β(i)\beta^{(i)} be the ii-th block of ℓ\ell consecutive bits of β\beta. The block decoding decℓ,N(β)\mathrm{dec}_{\ell,N}(\beta) of β\beta is the list of the numbers its first NN blocks spell: decℓ,N(β)=(val(β(1)),…,val(β(N))).\mathrm{dec}_{\ell,N}(\beta)=\bigl(\mathrm{val}(\beta^{(1)}),\dots,\mathrm{val}(\beta^{(N)})\bigr).(1)✦

A digit string is a string of binary digits. For a block length ℓ\ell, a bound SS, a digit string β\beta and a count NN, the chunk run runℓ,S(β,N)\mathrm{run}_{\ell,S}(\beta,N) is the list obtained by cutting β\beta into consecutive blocks of ℓ\ell digits, reading each of the first NN blocks as a number and reducing it below SS, in the order of the blocks.✦ The state of the chunk run runℓ,S(β,N)\mathrm{run}_{\ell,S}(\beta,N) consists of the block length and the bound for each sample, the list of samples drawn so far, and the string of random digits not yet used.

The Three Phases

Let GG be a mean-payoff game on nn vertices with edge weights w(e)w(e) and transformed weights t(e)=(n+1)w(e)+1t(e)=(n+1)w(e)+1, let W=max⁡{1,max⁡e|t(e)|}W=\max\{1,\max_e|t(e)|\}, and let B*=8nWB_*=8nW be the top width of GG; ss is the global sample count at B*B_*. The iteration count of a binary input code dd of length LL is N(d)=225000⌈log⁡2(L+2)⌉2.N(d)=2^{25000\lceil\log_2(L+2)\rceil^2}.(2)✦ The trial count is J=2(s(n+1))6+1J=2\,(s(n+1))^{6}+1.

A counter is a list of units, and a counter of length kk stands for the number kk. The preparation value of dd is the counter of length ℓN(d)\ell N(d), the product of the block length and the number of blocks, together with the auxiliary data a=((ℓ,S),N(d),(B,c0))a=((\ell,S),N(d),(B,c_0)), read off dd parsed as a game: a block length ℓ\ell and a bound SS for each sample, the number N(d)N(d) of blocks, the width BB, and the initial state c0c_0 of the solver’s control machine with its environment.✦ The preparation amount amt(d)\mathrm{amt}(d) of dd is the length of the counter in the preparation value of dd, the number of random bits the solver draws.✦ The preparation program 𝖯𝗋𝖾\mathsf{Pre} is the five-register program that runs the input boxing program, which puts the input code into the registers, moves register 1 into register 0 and computes the preparation value of the input.✦

A postprocessing input is a pair (β,a)(\beta,a) of a digit string β\beta and auxiliary data a=((ℓ,S),N,(B,c0))a=((\ell,S),N,(B,c_0)).✦ The samples samples(β,a)\mathrm{samples}(\beta,a) of a postprocessing input (β,a)(\beta,a) are the chunk run of the reversed string βrev\beta^{\mathrm{rev}} under the parameters stored in aa: samples(β,a)=runℓ,S(βrev,N).\mathrm{samples}(\beta,a)=\mathrm{run}_{\ell,S}(\beta^{\mathrm{rev}},N).(3)✦

The postprocessing code of a postprocessing input (β,a)(\beta,a) is the computation that runs the solver’s control machine from c0c_0 on the samples of (β,a)(\beta,a), one step of the control machine for each sample, the sample serving as that step’s random index. The machine uses that index to pick one of its centers, the iterates of its update step.✦ The code then writes out, for each entry of the vector the machine returns, whether it exceeds half the width BB.✦ The postprocessing program 𝖯𝗈𝗌𝗍\mathsf{Post} is the five-register program that runs the postprocessing code and then the emitter that writes out its digits.✦

A program is coin-free when none of its steps reads a tape bit. For five-register programs PP and QQ, the random table 𝒯(P,Q)\mathcal{T}(P,Q) is the program that runs PP; then, for each unit of the counter PP leaves in register 0, reads one fresh tape bit and writes it into register 1; then moves register 1 into register 0, runs QQ and halts.✦

A configuration of a program consists of its control point, absent once the program has halted, the contents of its registers and the output written so far. The initial configuration of 𝒯(P,Q)\mathcal{T}(P,Q) on an input uu is at the start node, with uu in the first register, the other registers empty and no output; κy\kappa_y is the halted configuration of 𝒯(P,Q)\mathcal{T}(P,Q) with empty registers and output yy. A random tree τ\tau of configurations traces a program from a configuration cc when, for every infinite bit sequence and every position ii in it, running the program from cc on the tape that starts at position ii, for as many steps as the walk down τ\tau reading the sequence from position ii reads bits, gives the configuration at the leaf where that walk ends.✦

The Claim

Theorem 1.

  1. For every kk, val*ℬk=𝒰k.\mathrm{val}_*\,\mathcal{B}_k=\mathcal{U}_k.(4)✦

  2. For every block length ℓ\ell and count NN, (decℓ,N)*ℬℓN=𝒮ℓ,N.(\mathrm{dec}_{\ell,N})_*\,\mathcal{B}_{\ell N}=\mathcal{S}_{\ell,N}.(5)✦

  3. For a block length ℓ\ell and a bound SS with 2ℓ≤S2^\ell\le S, and a digit string β\beta with at least ℓN\ell N digits, runℓ,S(β,N)=decℓ,N(β).\mathrm{run}_{\ell,S}(\beta,N)=\mathrm{dec}_{\ell,N}(\beta).(6)✦

  4. For every game GG, with ss the global sample count at its top width B*B_*, amt(⟨G⟩)=log⁡2s⋅N(⟨G⟩).\mathrm{amt}(\langle G\rangle)=\log_2 s\cdot N(\langle G\rangle).(7)✦

  5. The preparation and postprocessing programs satisfy 𝖯𝗋𝖾is coin-free,\mathsf{Pre}\ \text{is coin-free},(8)✦ 𝖯𝗈𝗌𝗍is coin-free.\mathsf{Post}\ \text{is coin-free}.(9)✦

  6. Let PP and QQ be coin-free five-register programs, uu an input string, xx auxiliary data, ρ\rho a map on bit strings, and UU, TpreT_{\mathrm{pre}}, TpostT_{\mathrm{post}} natural numbers. Suppose that on every tape PP, started on uu, has halted after TpreT_{\mathrm{pre}} steps, storing the pair of a counter of length UU and xx, with no output; and that for every bit string cc of length UU, on every tape QQ, started with the pair (c,x)(c,x) stored, has halted after TpostT_{\mathrm{post}} steps with empty registers and output ρ(c)\rho(c). Then there is a random tree τ\tau of configurations of 𝒯(P,Q)\mathcal{T}(P,Q), of depth at most Tpre+36U+Tpost+20T_{\mathrm{pre}}+36U+T_{\mathrm{post}}+20 and with every leaf halted, that traces 𝒯(P,Q)\mathcal{T}(P,Q) from its initial configuration on uu, and such that for every rational-valued function ff on configurations 𝔼τf=2−U∑c∈{0,1}Uf(κρ(c)).\mathbb{E}_\tau f=2^{-U}\sum_{c\in\{0,1\}^U}f(\kappa_{\rho(c)}).(10)✦

In the paper, the result reads: the only random primitive selects an iterate index; since ss is a power of two, exactly log⁡2s\log_2 s fair bits select a uniform index from {0,…,s−1}\{0,\dots,s-1\}, without a rejection loop; the JJ trials of either amplification run sequentially, taking fresh bits from one tape.

What Is Checked

The claim is stated over random trees of fair coins and their images, the fair bit draw, the uniform draw and the sample draw; over the block decoding and the chunk run; over the iteration count, the preparation amount and the postprocessing samples; and over the programs 𝖯𝗋𝖾\mathsf{Pre} and 𝖯𝗈𝗌𝗍\mathsf{Post}, the random table 𝒯(P,Q)\mathcal{T}(P,Q) and the tracing of a program by a random tree.

The library also bounds the encoded size of what the post phase holds: after any number of steps, the state of the chunk run has encoded size at most 5(t+1)25(t+1)^2✦ and the accumulator of the control loop, the value it carries from step to step, at most 240(t+1)122^{40}(t+1)^{12}, where tt is the encoded size of the starting state together with the counter or list that drives the steps. The coordinatewise maximum and minimum of a vector and a list of vectors are computed by a left fold over the list; for every kk, the fold over the first kk vectors has encoded size at most 20(S+1)220(S+1)^2, where SS is the encoded size of the input.