Improved Bounds on Lossless Source Coding and Guessing Moments via R\'enyi Measures

Understand

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\'enyi 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.