Non-Asymptotic Fundamental Limits of Guessing Subject to Distortion

Shota Saito; Toshiyasu Matsushima

doi:10.1109/ISIT.2019.8849434

Non-Asymptotic Fundamental Limits of Guessing Subject to Distortion

Shota Saito, Toshiyasu Matsushima

School of Fundamental Science and Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

2 Citations (Scopus)

Abstract

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.

Original language	English
Title of host publication	2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	652-656
Number of pages	5
ISBN (Electronic)	9781538692912
DOIs	https://doi.org/10.1109/ISIT.2019.8849434
Publication status	Published - 2019 Jul
Event	2019 IEEE International Symposium on Information Theory, ISIT 2019 - Paris, France Duration: 2019 Jul 7 → 2019 Jul 12

Publication series

Name	IEEE International Symposium on Information Theory - Proceedings
Volume	2019-July
ISSN (Print)	2157-8095

Conference

Conference	2019 IEEE International Symposium on Information Theory, ISIT 2019
Country/Territory	France
City	Paris
Period	19/7/7 → 19/7/12

ASJC Scopus subject areas

Theoretical Computer Science
Information Systems
Modelling and Simulation
Applied Mathematics

Access to Document

10.1109/ISIT.2019.8849434

Cite this

Saito, S., & Matsushima, T. (2019). Non-Asymptotic Fundamental Limits of Guessing Subject to Distortion. In 2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings (pp. 652-656). Article 8849434 (IEEE International Symposium on Information Theory - Proceedings; Vol. 2019-July). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT.2019.8849434

Non-Asymptotic Fundamental Limits of Guessing Subject to Distortion. / Saito, Shota; Matsushima, Toshiyasu.
2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 2019. p. 652-656 8849434 (IEEE International Symposium on Information Theory - Proceedings; Vol. 2019-July).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Saito, S & Matsushima, T 2019, Non-Asymptotic Fundamental Limits of Guessing Subject to Distortion. in 2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings., 8849434, IEEE International Symposium on Information Theory - Proceedings, vol. 2019-July, Institute of Electrical and Electronics Engineers Inc., pp. 652-656, 2019 IEEE International Symposium on Information Theory, ISIT 2019, Paris, France, 19/7/7. https://doi.org/10.1109/ISIT.2019.8849434

@inproceedings{94362e38ef644a9aa466fcaf4b8ba4e2,

title = "Non-Asymptotic Fundamental Limits of Guessing Subject to Distortion",

abstract = "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{\'e}nyi entropy (resp. the Arimoto-R{\'e}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.",

author = "Shota Saito and Toshiyasu Matsushima",

note = "Funding Information: ACKNOWLEDGMENT This work was supported in part by JSPS KAKENHI Grant Numbers JP17K06446 and JP19K14989. Publisher Copyright: {\textcopyright} 2019 IEEE.; 2019 IEEE International Symposium on Information Theory, ISIT 2019 ; Conference date: 07-07-2019 Through 12-07-2019",

year = "2019",

month = jul,

doi = "10.1109/ISIT.2019.8849434",

language = "English",

series = "IEEE International Symposium on Information Theory - Proceedings",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "652--656",

booktitle = "2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings",

}

TY - GEN

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

AU - Saito, Shota

AU - Matsushima, Toshiyasu

PY - 2019/7

Y1 - 2019/7

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85073164750&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85073164750&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2019.8849434

DO - 10.1109/ISIT.2019.8849434

M3 - Conference contribution

AN - SCOPUS:85073164750

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 652

EP - 656

BT - 2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2019 IEEE International Symposium on Information Theory, ISIT 2019

Y2 - 7 July 2019 through 12 July 2019

ER -

Non-Asymptotic Fundamental Limits of Guessing Subject to Distortion

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this