2018/08/19 by Shota Saito, Saito, Shota, Toshiyasu Matsushima +1
Computer Science · Engineering · #Computability, Logic, AI Algorithms #FOS: Computer and information sciences #Information Theory (cs.IT) #Wireless Communication Security Techniques
paper · pdf · doi:10.48550/arxiv.1808.06190
openalex publication_date 2018/08/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper investigates the problem of guessing subject to distortion, which was introduced by Arikan and Merhav. While the primary concern of the previous study was asymptotic analysis, our primary concern is non-asymptotic analysis. We prove non-asymptotic achievability and converse bounds of the moment of the number of guesses without side information (resp. with side information) by using a quantity based on the Rényi entropy (resp. the Arimoto-Rényi conditional entropy). Also, we introduce an error probability and show similar results. Further, from our bounds, we derive a single-letter characterization of the asymptotic exponent of guessing moment for a stationary memoryless source.