Improved Bounds on Guessing Moments via Rényi Measures

Igal Sason, Sergio Verdu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations


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 provided, characterizing the exact locus of their attainable values.

Original languageEnglish (US)
Title of host publication2018 IEEE International Symposium on Information Theory, ISIT 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages5
ISBN (Print)9781538647806
StatePublished - Aug 15 2018
Event2018 IEEE International Symposium on Information Theory, ISIT 2018 - Vail, United States
Duration: Jun 17 2018Jun 22 2018

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8095


Other2018 IEEE International Symposium on Information Theory, ISIT 2018
Country/TerritoryUnited States

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics


  • Error probability
  • Guessing moments
  • M-ary hypothesis testing
  • MAP decision rules
  • Rényi information measures


Dive into the research topics of 'Improved Bounds on Guessing Moments via Rényi Measures'. Together they form a unique fingerprint.

Cite this