跳到正文
研踪PaperTrail

论文库

检索计算机领域论文,按研究方向、作者或关键词筛选。

部分采集异常
正在读取账号与研究记录…

全站更新概况

+729新增论文
+575其中 AI 相关
+82已有论文修订
+95新增 AI 导读

arXiv 最近完成扫描:2026-11-21 12:19 · 全站最近入库:2026-11-21 12:19各信源进度 →

统计口径与数据新鲜度

统计 2026-11-20 16:20 — 2026-11-21 16:20(北京时间) · 点击数字查看对应简报;AI 相关包含在新增论文内。

最近完成检查:2026-11-21 12:19最近发现新增版本:2026-11-21 12:19库内论文最新更新时间:2026-11-20 02:59

每分钟刷新已保存的数据。空检查不代表采集异常;新收录可能包含历史论文。AI 导读按新增版本计数。

29,158 已收录论文24,181 AI 相关8,992 有修订112 HF 社区发现

浏览论文库

时间范围跟随排序:版本更新、本站收录或首次发表。最新收录可能包含历史论文。部分信源异常,查看状态 →

找到 1 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-21 12:17(北京时间)
版本更新 · v4arXiv:2610.26396

The Exhaustive Peres Transform: Extraction and Universal Coding

Aur{é}lien Garivier

原文摘要

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.

cs.IT