Entropy and compression: a simple proof of an inequality of Khinchin-Ornstein-Shields

DOI10.1134/S0032946020010020MaRDI QIDQ2190980zbMATH OpenOpenAlexFDO

Authors Riccardo Aragona, Filippo Mignosi, M. Spezialetti, Francesca Marzi

Publication date 23 June 2020

Published in Problems of Information Transmission (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1907.04713

zbMATH Keywords

entropyergodic sourceslossless data compressionone-to-one code sequenceShannon-Mcmillan theorem

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Measures of information, entropy (94A17) Coding theorems (Shannon theory) (94A24) Source coding (94A29)

Abstract: This paper concerns the folklore statement that ``entropy is a lower bound for compression. More precisely we derive from the entropy theorem a simple proof of a pointwise inequality firstly stated by Ornstein and Shields and which is the almost-sure version of an average inequality firstly stated by Khinchin in 1953. We further give an elementary proof of original Khinchin inequality that can be used as an exercise for Information Theory students and we conclude by giving historical and technical notes of such inequality.

Recommendations

• Entropy and data compression schemes
• Inequalities for Shannon entropy and Kolmogorov complexity
• A coding theorem connected on R-norm entropy
• Compression and entropy
• scientific article; zbMATH DE number 3920366

Cites work

• A Mathematical Theory of Communication
• A Note on the Ergodic Theorem of Information Theory
• A sandwich proof of the Shannon-McMillan-Breiman theorem
• A simple proof of the Moy-Perez generalization of the Shannon-McMillan theorem
• Compression and entropy
• Correction Notes: Correction to "The Individual Ergodic Theorem of Information Theory"
• Elements of Information Theory
• scientific article; zbMATH DE number 3143967 (Why is no real title available?)
• scientific article; zbMATH DE number 3492150 (Why is no real title available?)
• scientific article; zbMATH DE number 2061729 (Why is no real title available?)
• scientific article; zbMATH DE number 918233 (Why is no real title available?)
• scientific article; zbMATH DE number 3316587 (Why is no real title available?)
• scientific article; zbMATH DE number 3079993 (Why is no real title available?)
• Information theory and network coding
• Information theory. Coding theorems for discrete memoryless systems
• New bounds on the expected length of one-to-one codes
• Optimal Lossless Data Compression: Non-Asymptotics and Asymptotics
• Sample converses in source coding theory
• Second-order noiseless source coding theorems
• The Basic Theorems of Information Theory
• The Individual Ergodic Theorem of Information Theory
• The Shannon-McMillan theorem for ergodic quantum lattice systems
• The source coding theorem revisited: A combinatorial approach
• The strong ergodic theorem for densities: Generalized Shannon-McMillan- Breiman theorem
• Universal almost sure data compression
• Universal codeword sets and representations of the integers

Cited in

(1)

• Entropy compression versus Lovász local lemma

This page was built for publication: Entropy and compression: a simple proof of an inequality of Khinchin-Ornstein-Shields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2190980)