Tight Bounds on the Rényi Entropy via Majorization with Applications to Guessing and Compression
This paper provides tight bounds on the Rényi entropy of a function of a discrete random variable with a finite number of possible values, where the considered function is not one to one. To that end, a tight lower bound on the Rényi entropy of a discrete random variable with a fin...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2018-11-01
|
| Series: | Entropy |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1099-4300/20/12/896 |
| _version_ | 1798040546578530304 |
|---|---|
| author | Igal Sason |
| author_facet | Igal Sason |
| author_sort | Igal Sason |
| collection | DOAJ |
| description | This paper provides tight bounds on the Rényi entropy of a function of a discrete random variable with a finite number of possible values, where the considered function is not one to one. To that end, a tight lower bound on the Rényi entropy of a discrete random variable with a finite support is derived as a function of the size of the support, and the ratio of the maximal to minimal probability masses. This work was inspired by the recently published paper by Cicalese et al., which is focused on the Shannon entropy, and it strengthens and generalizes the results of that paper to Rényi entropies of arbitrary positive orders. In view of these generalized bounds and the works by Arikan and Campbell, non-asymptotic bounds are derived for guessing moments and lossless data compression of discrete memoryless sources. |
| first_indexed | 2024-04-11T22:09:07Z |
| format | Article |
| id | doaj.art-b75068a31a7442a0956fce2c41bfe224 |
| institution | Directory Open Access Journal |
| issn | 1099-4300 |
| language | English |
| last_indexed | 2024-04-11T22:09:07Z |
| publishDate | 2018-11-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Entropy |
| spelling | doaj.art-b75068a31a7442a0956fce2c41bfe2242022-12-22T04:00:37ZengMDPI AGEntropy1099-43002018-11-01201289610.3390/e20120896e20120896Tight Bounds on the Rényi Entropy via Majorization with Applications to Guessing and CompressionIgal Sason0Department of Electrical Engineering, Technion—Israel Institute of Technology, Haifa 3200003, IsraelThis paper provides tight bounds on the Rényi entropy of a function of a discrete random variable with a finite number of possible values, where the considered function is not one to one. To that end, a tight lower bound on the Rényi entropy of a discrete random variable with a finite support is derived as a function of the size of the support, and the ratio of the maximal to minimal probability masses. This work was inspired by the recently published paper by Cicalese et al., which is focused on the Shannon entropy, and it strengthens and generalizes the results of that paper to Rényi entropies of arbitrary positive orders. In view of these generalized bounds and the works by Arikan and Campbell, non-asymptotic bounds are derived for guessing moments and lossless data compression of discrete memoryless sources.https://www.mdpi.com/1099-4300/20/12/896MajorizationRényi entropyRényi divergencecumulant generating functionsguessing momentslossless source codingfixed-to-variable source codesHuffman algorithmTunstall codes |
| spellingShingle | Igal Sason Tight Bounds on the Rényi Entropy via Majorization with Applications to Guessing and Compression Entropy Majorization Rényi entropy Rényi divergence cumulant generating functions guessing moments lossless source coding fixed-to-variable source codes Huffman algorithm Tunstall codes |
| title | Tight Bounds on the Rényi Entropy via Majorization with Applications to Guessing and Compression |
| title_full | Tight Bounds on the Rényi Entropy via Majorization with Applications to Guessing and Compression |
| title_fullStr | Tight Bounds on the Rényi Entropy via Majorization with Applications to Guessing and Compression |
| title_full_unstemmed | Tight Bounds on the Rényi Entropy via Majorization with Applications to Guessing and Compression |
| title_short | Tight Bounds on the Rényi Entropy via Majorization with Applications to Guessing and Compression |
| title_sort | tight bounds on the renyi entropy via majorization with applications to guessing and compression |
| topic | Majorization Rényi entropy Rényi divergence cumulant generating functions guessing moments lossless source coding fixed-to-variable source codes Huffman algorithm Tunstall codes |
| url | https://www.mdpi.com/1099-4300/20/12/896 |
| work_keys_str_mv | AT igalsason tightboundsontherenyientropyviamajorizationwithapplicationstoguessingandcompression |