Non-Asymptotic and Asymptotic Fundamental Limits of Guessing Subject to Distortion

08/19/2018
by   Shota Saito, et al.
0

This paper considers the problem of guessing random variables subject to distortion. We investigate both non-asymptotic and asymptotic fundamental limits of the minimum t-th moment of the number of guesses. These fundamental limits are characterized by the quantity related to the Rényi entropy. To derive the non-asymptotic bounds, we use our techniques developed in lossy compression. Moreover, using the results obtained in the non-asymptotic setting, we derive the asymptotic result and show that it coincides with the previous result by Arikan and Merhav.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset