The Exhaustive Peres Transform: Extraction and Universal Coding
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.
Related
- Joint Branch-Space Transform Coding for Diffusion Activation Quantization with Classifier-Free Guidance
- Constructive Universal Approximation by Infinite-Dimensional Neural Networks via Gaussian-Weighted Ridgelet Transform
- Universal Short-Time Fourier Transform: Data-Adaptive Window-Length Selection for Time-Frequency Analysis
- Optimal Universal Coding of Integers
- Variable-Length Feedback Coding With Universal Decoding and Bandit Channel Selection
BibTeX
@misc{garivier2026exhaustive,
title = {{The Exhaustive Peres Transform: Extraction and Universal Coding}},
author = {Aurélien Garivier},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.26396},
eprint = {2610.26396},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.26396},
}
RIS
TY - UNPB
TI - The Exhaustive Peres Transform: Extraction and Universal Coding
AU - Aur{é}lien Garivier
PY - 2026
DA - 2026/10/26
PB - arXiv
DO - 10.48550/arxiv.2610.26396
UR - https://arxiv.org/abs/2610.26396
AB - 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.
ER -