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

08/19/2018

∙

by   Shota Saito, et al.

∙

0

∙

share

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.