Entropy and Compression: A simple proof of an inequality of Khinchin-Ornstein-Shields
| Autor: | Aragona, Riccardo, Marzi, Francesca, Mignosi, Filippo, Spezialetti, Matteo |
|---|---|
| Rok vydání: | 2019 |
| Předmět: | |
| Zdroj: | Problems of Information Transmission, Vo.l 56 No. 1, 2020. A view-only published version here: https://rdcu.be/b3Cco |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1134/S0032946020010020 |
| Popis: | 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. Comment: Compared to version 1, in version 2 we added a simpler proof than the one given by Shields of a more general theorem (Theorem 4, pg. 7) presented by Ornstein and Shields. Consequently we also modified the title of the paper. In version 3 we have reordered the sections of the paper, simplified the proof of Theorem 4 (now Theorem 3) and significantly reduced the proof of Theorem 3 (now Theorem 4) |
| Databáze: | arXiv |
| Externí odkaz: |
|