CS Paper Radar

A First-Order Entropy Law for Canonical T-Complexity of Finite-Alphabet i.i.d. Sources

Thomas Schürmann

cs.IT math.ST ·submitted 2026-08-18 16:12 UTC · v1
theory

Abstract

Let $W_N$ be an exact length-$N$ block from a strictly positive i.i.d. source $\mathbf p$ on a fixed finite alphabet. We prove that the canonical T-complexity $c_T$ satisfies \[ \frac{c_T(W_N)}{e^{-γ}h(\mathbf p) N/\log N}\longrightarrow1 \] in probability and in $L^r$ for every fixed $1\le r<\infty$, where $h(\mathbf p)$ is the source entropy in nats and $γ$ is the Euler-Mascheroni constant. The proof combines an exact length budget for canonical recovery, a critical-scale $E_1$ estimate for an ideal backward chain, and an exact finite-block boundary representation. An exact Doob-transform identity expresses the finite-boundary law relative to the ideal law conditioned at each step to avoid the current history-dependent successor codeword. A history-uniform renewal estimate then makes the telescoping endpoint density uniformly asymptotic to one, so no one-step approximation errors accumulate.

Comment
10 pages, no figures

Closest papers

Nearest neighbours by meaning across the whole index.

Beyond the Static Barrier for Ordinary Dynamic Approximate Membership

cs.DS cs.CCcs.IT ·2026-08-23 ·Qizhi Chen, Zhebei Shen, Zhehan Yu
theory similarity 0.62
Abstract

We prove a strict space separation between static and ordinary dynamic approximate membership at every fixed error rate. For each fixed $\varepsilon\in(0,1)$, a capacity-$n$ ordinary dynamic filter over a universe of size $u$, with zero false negatives, pointwise false-positive probability at most $\varepsilon$, arbitrary history dependence, a free public random tape, and at most $H$ bits of persistent state, satisfies \[ H\ge \bigl(\log_2(1/\varepsilon)+a_\varepsilon^{\rm c}\bigr)n-o(n), \] under only $u/n\to\infty$. The constant $a_\varepsilon^{\rm c}$ is an explicit variational threshold obtained by preserving the dependence between the parent accepted mass and the successor reservoir. The structural step is a common-continuation transport lemma. A joint posterior KL bound gives a branch-specific survivor support; the same legal delete--insert word transports that support to one successor state, forcing an accepted reservoir. We then keep the parent outside mass $1-X$ in the conditional-entropy argument instead of replacing it by $1-\varepsilon$. This yields a two-variable analytic envelope, with no selected thresholds, dyadic witnesses, or numerical assumptions.

0.23

Learning Finite-Memory Binary Sources

cs.IT math.PR ·2026-10-29 ·Maciej Skorski
similarity 0.59
Abstract

Estimating biased finite-memory sources from a single trajectory is a fundamental problem with practical impact, for example in estimating entropy for cryptography. We study order-$d$ binary sources whose conditional probabilities have bias at most $ε$, and establish *sharp* sample complexity bounds: relative accuracy $γ$ with confidence $1-δ$ needs $γ^{-2}\,(\tfrac12-ε)^{-d}\,(\log d+\log\tfrac1δ)$ samples up to constants depending on $ε$, with matching upper and lower bounds and no dependence on mixing time or spectral gap. The proof rests on a sharp bound on expected hitting times of the sliding-window (de Bruijn) chain, which stay of order $1/π(w)$ uniformly in $d$ exactly when $ε<\tfrac3{10}$, and on majorization of the window masses by those of independent biased coins. Applied to published entropy-source validations, the bounds show that their trace lengths may be underpowered: $10^6$ bits cannot resolve all transitions of an $8$-bit model to better than about $4.5\%$ relative error.

0.17

Lower Bounds for all List-Decodable Deletion Codes

cs.IT cs.DMmath.CO ·2026-09-22 ·Andrew D. Lin
theory similarity 0.58
Abstract

A length-$n$ binary $k$-deletion code is a set of binary strings such that if we delete any $k$ bits of a string, leaving a length-$(n-k)$ binary string, we can uniquely recover the codeword. In this paper, we consider $t$-list decodable deletion codes, where after $k$ bits of a codeword are deleted, we can identify a list of size at most $t$ such that the original codeword lies in the list. We prove a lower bound of $Ω_k(2^n t\log^{1/t}n/n^{k+k/t})$ on the optimal size of a $t$-list decodable $k$-deletion code, giving a $\sqrt{\log n}$ improvement over the previously best known bounds for $2$-list decodable $2$-deletion codes [GH21] and providing the first nontrivial lower bound when $t>2$ or $k>2$. Our bound holds for all $t\leq n^k$, showing that $t=Ω(\log n)-$list decodable deletion codes have optimal size $Θ_k(2^n t/n^k)$, asymptotically matching the known upper bound. We also prove upper bounds on the number of common subsequences and common supersequences of a given length for any two binary strings.

0.06

A Conditional No-Hair Theorem for Transformers: How Language Models Forget Their Prompt

cs.AI ·2026-10-16 ·Shuyang Xiang
theory similarity 0.57
Abstract

We ask how much an autoregressive transformer retains of its prompt after generating $t$ tokens. Consider two different prompts followed by the same continuation text, so that any difference in their hidden states comes from the prompt alone, and we find that the distance between their hidden states decays approximately as a power law $t^{-α}$, where $α=1$ is the rate at which a fixed prompt's share of uniform attention shrinks and smaller values mean longer memory. Trained models forget fast ($α\approx0.55$--$0.7$), untrained ones slowly ($α\approx0.2$--$0.5$). We prove that this offset is $O\big(P(\log t)^{L-1}/t\big)$ for a prompt of length $P$ and depth $L$. The bound holds for finite-depth pre-LN softmax transformers with bounded attention logits, under one additional condition: the pre-norm activations stay away from zero. The mechanism is geometric: the prompt's direct influence is diluted as the context grows, and \emph{relay} --- continuation tokens passing on what earlier tokens read from the prompt --- can only add logarithmic factors. This is what we call the \emph{conditional no-hair theorem}: given the text generated so far, the prompt's influence on the next token vanishes as $t$ grows, so any property of the prompt that survives, such as its language, must be carried by the text itself. An exactly solvable linear relay model shows that the bound cannot be improved and reproduces the rise of the local exponent towards $1$ seen in untrained networks. Cancelling the dilution with a logit bias stops the decay early in training and reverses it after, so dilution is necessary for the forgetting we measure; untrained networks and the solvable model show it is also sufficient.

0.34

Coding for Multiple Reverse-Complement and Palindromic Duplications

cs.IT ·2026-09-01 ·Aryeh Lev Zabokritskiy
theory similarity 0.57
Abstract · 33 pages

Reverse-complement (RC) and palindromic (PAL) duplications insert a reversed copy of a length-$k$ block immediately after the block; an RC duplication also applies a fixed involutive complement to the inserted symbols. We study $q$-ary codes correcting $t$ such operations applied in sequence, where later operations may copy inserted symbols. For fixed $q\geq2$ and $k,t\geq1$, we prove that every length-$n$ code $C$ for either channel has redundancy $n-\log_q|C|\geq t\log_q n-O_{q,k,t}(1)$; for fixed $q,k$ and $1\leq t=t(n)=o(n)$ the lower bound is $t\log_q(n/t)-O_{q,k}(t)$. For fixed $k$, known codes for one length-$k$ insertion burst attain redundancy $\log_q n+O_{q,k}(1)$ for a single duplication of either type. For every even $k$ and any involutive complement, we show that the two channels are equivalent for every number of errors: the bijection complementing every other coordinate turns each RC duplication into a PAL duplication. This bijection therefore converts any $t$-error-correcting RC code into a PAL code of the same size, and conversely, with linear-time transfer of encoders and decoders. For every even $k$, we also determine the maximum number of descendants of one word under exactly two errors; by the bijection, it is the same for both channels. For fixed even $k$, a direct count using this maximum proves the existence of two-error-correcting PAL and RC codes with redundancy at most $4\log_q n+O_{q,k}(1)$. A known existence bound for two deletion bursts transfers to insertions with the same leading term as ours and a larger additive constant. For two errors, the converse gives $2\log_q n-O_{q,k}(1)$, a factor of two below these existence bounds.

0.31

MacKay-Neal Codes for DNA Channels under Block-MAP Decoding

cs.IT ·2026-10-28 ·Kenta Kasai
theory similarity 0.56
Abstract · 14 pages

We prove achievability below the symmetric information rate (SIR) under block maximum a posteriori (MAP) decoding for a fixed-degree MacKay-Neal (MN) socket ensemble on the quaternary insertion-deletion-substitution channel used to model DNA reads. For every integer $\ell\ge4$, the $(\ell,3,3)$ socket ensemble, with one transmitted bit fixed and an independent uniform known offset, has limiting rate $r_\star=6/\ell$ bits per stored nucleotide. If the joint SIR $J_t$ of a fixed number $t$ of reads under independent, uniformly distributed input nucleotides exceeds $r_\star$, the ensemble-average full extended-word block error is $O(1/n)$, and deterministic graph-offset sequences attain the same limiting rate and message-average error bound. This result concerns the discrete rate family $6/\ell$, not arbitrary rates approaching a given SIR. The channel permits arbitrarily many insertions and unbounded drift, with no alignment supplied to the receiver. The proof combines established MN parity and distance estimates with a strict arbitrary-candidate-list bound and a list construction that accounts for hidden output boundaries.

0.26

Fano's Inequality and Channel Capacity in the Individual-Sequence Regime

cs.IT ·2026-11-04 ·Neri Merhav
theory similarity 0.56
Abstract · 31 pages; submitted for publication

We derive an individual-sequence analogue of Fano's inequality, replacing entropy by Lempel--Ziv (LZ) complexity and probability of error by empirical error frequency. In the setting considered, an arbitrary encoder maps a message to a channel input sequence $\{x_t\}$, the channel maps the input to an output $\{y_t\}$ in a completely arbitrary manner, and a block finite-state decoder produces an estimate of the channel input from the output. The individual-sequence Fano inequality lower-bounds the empirical symbol-error frequency in terms of the LZ complexity of the channel input conditioned on the channel output. This leads to a channel coding converse: reliable communication at a given rate is possible only if that rate does not exceed the individual-sequence LZ channel capacity, defined as the LZ mutual information maximized over channel inputs and minimized (worst-case) over a noise set. We also prove a matching achievability theorem for the class of \emph{symbol-wise invertible} channels, in which the channel output at each time $t$ is $y_t = f(x_t, v_t)$, $v_t$ being a `noise' variable, and $f(\cdot,v)$ is a bijection for every fixed $v$. This class includes group-additive channels $y_t = x_t \oplus v_t$ studied by Feder and coworkers. For such a channel, any rate below the LZ capacity is achievable with vanishing per-message error frequency, simultaneously for every $v^n$ in a given noise set $\mathcal{N}$, provided $\mathcal{N}$ is closed under block permutations; this condition is satisfied by any noise set that depends on $v^n$ only via its type class with respect to such blocks. The achievability uses a universal decoder that requires no knowledge of the channel and no feedback.

0.22

The Exhaustive Peres Transform: Extraction and Universal Coding

cs.IT ·2026-10-19 ·Aur{é}lien Garivier
similarity 0.56
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.

0.29