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

DOI10.1134/S0032946020010020zbMATH Open1457.94060arXiv1907.04713OpenAlexW3099805774MaRDI QIDQ2190980FDOQ2190980

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)

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.

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cites Work

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

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)