Paperlane

no. 16 · Tuesday 17 November 2026

The Exhaustive Peres Transform: Extraction and Universal Coding

Aur{é}lien Garivier

math.IT · v4

Abstract

Run to exhaustion, Peres's iteration of von Neumann's procedure yields 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, and the residual of every input of length N has fewer than sqrt(3) N^0.793 ones. This sparsity gives a short proof, with an explicit remainder, that the fair bits per symbol tend almost surely to the entropy for Bernoulli sources and every finite alphabet. The Bernoulli likelihood factorises along the recursion, and code B, which codes the residual at plug-in biases, has the length of the two-part code. Code G gamma-codes the gaps of the residual, with 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). What is more, a concatenation of J pieces costs its piecewise empirical entropy plus a term that is sublinear when J = o(N), without the cuts being sent. After a Burrows-Wheeler transform of the reversed string, both codes are universal for stationary ergodic sources: code B through a context tree of growing depth, with regret O(2^k log N) against Markov sources of order k, and code G with no tree, competing on every individual sequence with the empirical conditional entropy of every order. For laws invariant under permutations inside the pieces of a partition, the fair bits not mixed across the pieces are exactly uniform given everything else; after the BWT, the fair bits of every stationary source fall short of their length by o(N) bits of entropy, with an exponential tail for Markov sources. Experiments measure the finite-length price of these guarantees.

fields
Information Theory
pdf ↗ page arXiv:2610.26396 ↗