The Exhaustive Peres Transform: Extraction and Universal Coding
Aurélien Garivier
Abstract
Peres's iteration of von Neumann's procedure, run to exhaustion and keeping everything it does not extract, is a bijection of {0,1}^N that splits every string into fair bits and a residual. The residual is self-delimiting and determines the number of ones, so the fair bits are exactly uniform given the residual under every exchangeable law. Each residual one accounts for a power of two of the weight of the input; consequently, on every input of length N, the residual has fewer than sqrt(3) N^0.793 ones. This deterministic sparsity gives a short proof, with an explicit remainder, that the number of fair bits per symbol tends almost surely to the entropy, for Bernoulli sources and, by binarisation, on every finite alphabet. For coding, the Bernoulli likelihood factorises along the recursion, and code B, which stores the fair bits and codes the residual at plug-in biases, has the length of the two-part code. Alternatively, code G stores the fair bits and writes the Elias gamma codes of the gaps of the residual: it needs no parameter, no estimate and no arithmetic coder. On every string its length is at most the logarithm of the type class plus O(N^0.793 log N); a concatenation of J pieces costs, without transmitting the cuts, its piecewise empirical entropy plus a term that is sublinear when J = o(N). After a Burrows-Wheeler transform of the reversed string, code G competes on every individual sequence with the empirical conditional entropy of every order at once, which gives universality for stationary ergodic sources.