Guessing Revisited: A Large Deviations Approach

Understand

The problem of guessing a random string is revisited.

• A close relation between guessing and compression is first established.
• Then it is shown that if the sequence of distributions of the information spectrum satisfies the large deviation property with a certain rate function, then the limiting guessing exponent exists and is a scalar multiple of the Legendre-Fenchel dual of the rate function.
• Other sufficient conditions related to certain continuity properties of the information spectrum are briefly discussed.