2018/01/04 by Igal Sason, Sergio Verdú, Sason, Igal +1 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · #DNA and Biological Computing #Error Correcting Code Techniques #FOS: Computer and information sciences #Information Theory (cs.IT) #Wireless Communication Security Techniques
paper · pdf · doi:10.48550/arxiv.1801.01265
openalex publication_date 2018/01/04 · openalex created_date 2022/10/05 · openalex updated_date 2026/07/28
This paper provides upper and lower bounds on the optimal guessing moments of\na random variable taking values on a finite set when side information may be\navailable. These moments quantify the number of guesses required for correctly\nidentifying the unknown object and, similarly to Arikan's bounds, they are\nexpressed in terms of the Arimoto-R 'enyi conditional entropy. Although\nArikan's bounds are asymptotically tight, the improvement of the bounds in this\npaper is significant in the non-asymptotic regime. Relationships between\nmoments of the optimal guessing function and the MAP error probability are also\nestablished, characterizing the exact locus of their attainable values. The\nbounds on optimal guessing moments serve to improve non-asymptotic bounds on\nthe cumulant generating function of the codeword lengths for fixed-to-variable\noptimal lossless source coding without prefix constraints. Non-asymptotic\nbounds on the reliability function of discrete memoryless sources are derived\nas well. Relying on these techniques, lower bounds on the cumulant generating\nfunction of the codeword lengths are derived, by means of the smooth R 'enyi\nentropy, for source codes that allow decoding errors.\n