The Setting
The randomized solver for mean-payoff games amplifies twice: it takes the coordinatewise median of trials of a recursive call, and the strict majority of trials of an orientation, a choice of or . Here , a power of two, is the number of iterates among which the solver chooses and 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 of the game , a binary string of length , 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 is a finite binary tree whose internal nodes flip a fair coin and whose leaves carry elements of . 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 on , is the expectation of at the leaf reached. For a map on , the image is the random tree with every leaf relabelled .
The fair bit draw is the random tree that flips fair coins and returns the string of their outcomes in the order flipped.✦ For a bit string , is the number spells in binary. The uniform draw is the random tree that draws an index uniformly from . For a block length and a count , the sample draw is the random tree that draws indices one after another, each by , and returns the list of them in the order drawn, each in unary.✦
For a block length , a count and a bit string of length at least , let be the -th block of consecutive bits of . The block decoding of is the list of the numbers its first blocks spell: (1)✦
A digit string is a string of binary digits. For a block length , a bound , a digit string and a count , the chunk run is the list obtained by cutting into consecutive blocks of digits, reading each of the first blocks as a number and reducing it below , in the order of the blocks.✦ The state of the chunk run 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 be a mean-payoff game on vertices with edge weights and transformed weights , let , and let be the top width of ; is the global sample count at . The iteration count of a binary input code of length is (2)✦ The trial count is .
A counter is a list of units, and a counter of length stands for the number . The preparation value of is the counter of length , the product of the block length and the number of blocks, together with the auxiliary data , read off parsed as a game: a block length and a bound for each sample, the number of blocks, the width , and the initial state of the solver’s control machine with its environment.✦ The preparation amount of is the length of the counter in the preparation value of , the number of random bits the solver draws.✦ The preparation program 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 of a digit string and auxiliary data .✦ The samples of a postprocessing input are the chunk run of the reversed string under the parameters stored in : (3)✦
The postprocessing code of a postprocessing input is the computation that runs the solver’s control machine from on the samples of , 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 .✦ The postprocessing program 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 and , the random table is the program that runs ; then, for each unit of the counter leaves in register 0, reads one fresh tape bit and writes it into register 1; then moves register 1 into register 0, runs 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 on an input is at the start node, with in the first register, the other registers empty and no output; is the halted configuration of with empty registers and output . A random tree of configurations traces a program from a configuration when, for every infinite bit sequence and every position in it, running the program from on the tape that starts at position , for as many steps as the walk down reading the sequence from position reads bits, gives the configuration at the leaf where that walk ends.✦
The Claim
Theorem 1.
For every , (4)✦
For every block length and count , (5)✦
For a block length and a bound with , and a digit string with at least digits, (6)✦
For every game , with the global sample count at its top width , (7)✦
The preparation and postprocessing programs satisfy (8)✦ (9)✦
Let and be coin-free five-register programs, an input string, auxiliary data, a map on bit strings, and , , natural numbers. Suppose that on every tape , started on , has halted after steps, storing the pair of a counter of length and , with no output; and that for every bit string of length , on every tape , started with the pair stored, has halted after steps with empty registers and output . Then there is a random tree of configurations of , of depth at most and with every leaf halted, that traces from its initial configuration on , and such that for every rational-valued function on configurations (10)✦
In the paper, the result reads: the only random primitive selects an iterate index; since is a power of two, exactly fair bits select a uniform index from , without a rejection loop; the 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 and , the random table 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 ✦ and the accumulator of the control loop, the value it carries from step to step, at most , where 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 , the fold over the first vectors has encoded size at most , where is the encoded size of the input.