Statistics of the Compression Ratio of a Variable-to-Variable Code: Exact Moments and Asymptotic Behavior
Entropy · 10.08.2026 · 28 (8) · 898
DOI: 10.3390/e28080898 ↗Kurz gefasst
Fachartikel in der Zeitschrift Entropy, online erschienen am 10.08.2026. Verfasst von Neri Merhav. Beteiligte Einrichtung: The Viterbi Faculty of Electrical and Computer Engineering, Technion-Israel Institute of Technology, Technion City, Haifa 3200003, Israel. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 27 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
A variable-to-variable (V2V) length code parses a source sequence into phrases of variable length and maps each phrase to a binary codeword of, generally, a different random length. After encoding n phrases, the realized compression ratio Rn=Λn/Σn—total codeword length over total source-symbol count—is the finite-sample counterpart of the code’s asymptotic rate ρ, to which it converges only as n→∞. This paper first derives exact formulas for all integer moments of Rn for a given discrete memoryless source (DMS). Specifically, we obtain a closed-form formula for every moment E{Rnk} as a one-dimensional integral involving only single-phrase moment generating functions of the pair (L,l)—the phrase length, in source symbols, and codeword length, in bits. From these moments we derive an Edgeworth approximation to the cumulative distribution function (CDF) of Rn that is substantially more accurate than the central limit theorem (CLT) approximation. Using the Laplace method of integration, we also derive explicit closed-form formulas for the bias constant C=limn→∞n(E{Rn}−ρ) and for the variance constant limn→∞n·Var{Rn}. The analysis extends to Markov sources via state-indexed matrices with a redundancy formula obtained in closed form. On the coding-theoretic side, we cast V2V length codes as finite-state encoders and apply a generalized Kraft inequality for a compression-rate lower bound, and give a structural decomposition of the bias coefficient that separates cleanly across variable-to-fixed (V2F) length codes, fixed-to-variable (F2V) length codes, and V2V length codes. Applied to the Khodak code of Bugeaud, Drmota, and Szpankowski, this decomposition shows that its improved performance is reflected in its smaller bias constant.
Schlagwörter
Stichwörter der Autor:innen
Autor:innen und Institutionen
- The Viterbi Faculty of Electrical and Computer Engineering, Technion-Israel Institute of Technology, Technion City, Haifa 3200003, Israel.
Zitieren
APA
Merhav, N. (2026). Statistics of the Compression Ratio of a Variable-to-Variable Code: Exact Moments and Asymptotic Behavior. Entropy, 28(8), 898. https://doi.org/10.3390/e28080898
Vancouver
Merhav N. Statistics of the Compression Ratio of a Variable-to-Variable Code: Exact Moments and Asymptotic Behavior. Entropy. 2026;28(8):898. doi:10.3390/e28080898
BibTeX
@article{Merhav2026,
author = {Merhav, Neri},
title = {Statistics of the Compression Ratio of a Variable-to-Variable Code: Exact Moments and Asymptotic Behavior},
journal = {Entropy},
year = {2026},
volume = {28},
number = {8},
pages = {898},
doi = {10.3390/e28080898}
}
EUVIMED