TY - JOUR
T1 - Improved Bounds on Lossless Source Coding and Guessing Moments via Rényi Measures
AU - Sason, Igal
AU - Verdu, Sergio
N1 - Funding Information:
Manuscript received November 1, 2017; accepted January 27, 2018. Date of publication February 7, 2018; date of current version May 18, 2018. This paper was presented in part at the 2018 International Zurich Seminar on Information and Communication and the 2018 IEEE International Symposium on Information Theory. This work was supported in part by the Israeli Science Foundation under Grant 12/12, in part by ARO-MURI under Contract W911NF-15-1-0479, and in part by the Center for Science of Information, NSF Science and Technology Center under Grant CCF-0939370.
Publisher Copyright:
© 1963-2012 IEEE.
PY - 2018/6
Y1 - 2018/6
N2 - This paper provides upper and lower bounds on the optimal guessing moments of a random variable taking values on a finite set when side information may be available. These moments quantify the number of guesses required for correctly identifying the unknown object and, similarly to Arikan's bounds, they are expressed in terms of the Arimoto-Rényi conditional entropy. Although Arikan's bounds are asymptotically tight, the improvement of the bounds in this paper is significant in the non-asymptotic regime. Relationships between moments of the optimal guessing function and the MAP error probability are also established, characterizing the exact locus of their attainable values. The bounds on optimal guessing moments serve to improve non-asymptotic bounds on the cumulant generating function of the codeword lengths for fixed-to-variable optimal lossless source coding without prefix constraints. Non-asymptotic bounds on the reliability function of discrete memoryless sources are derived as well. Relying on these techniques, lower bounds on the cumulant generating function of the codeword lengths are derived, by means of the smooth Rényi entropy, for source codes that allow decoding errors.
AB - This paper provides upper and lower bounds on the optimal guessing moments of a random variable taking values on a finite set when side information may be available. These moments quantify the number of guesses required for correctly identifying the unknown object and, similarly to Arikan's bounds, they are expressed in terms of the Arimoto-Rényi conditional entropy. Although Arikan's bounds are asymptotically tight, the improvement of the bounds in this paper is significant in the non-asymptotic regime. Relationships between moments of the optimal guessing function and the MAP error probability are also established, characterizing the exact locus of their attainable values. The bounds on optimal guessing moments serve to improve non-asymptotic bounds on the cumulant generating function of the codeword lengths for fixed-to-variable optimal lossless source coding without prefix constraints. Non-asymptotic bounds on the reliability function of discrete memoryless sources are derived as well. Relying on these techniques, lower bounds on the cumulant generating function of the codeword lengths are derived, by means of the smooth Rényi entropy, for source codes that allow decoding errors.
KW - Arimoto-Rényi conditional entropy
KW - Cumulant generating function
KW - M-ary hypothesis testing
KW - Rényi divergence
KW - Rényi entropy
KW - guessing moments
KW - lossless source coding
KW - smooth Rényi entropy
UR - http://www.scopus.com/inward/record.url?scp=85041548235&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85041548235&partnerID=8YFLogxK
U2 - 10.1109/TIT.2018.2803162
DO - 10.1109/TIT.2018.2803162
M3 - Article
AN - SCOPUS:85041548235
SN - 0018-9448
VL - 64
SP - 4323
EP - 4346
JO - IRE Professional Group on Information Theory
JF - IRE Professional Group on Information Theory
IS - 6
ER -