{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T00:49:18Z","timestamp":1760402958177,"version":"build-2065373602"},"reference-count":29,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2021,4,9]],"date-time":"2021-04-09T00:00:00Z","timestamp":1617926400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information"],"abstract":"<jats:p>Stationary memoryless sources produce two correlated random sequences Xn and Yn. A guesser seeks to recover Xn in two stages, by first guessing Yn and then Xn. The contributions of this work are twofold: (1) We characterize the least achievable exponential growth rate (in n) of any positive \u03c1-th moment of the total number of guesses when Yn is obtained by applying a deterministic function f component-wise to Xn. We prove that, depending on f, the least exponential growth rate in the two-stage setup is lower than when guessing Xn directly. We further propose a simple Huffman code-based construction of a function f that is a viable candidate for the minimization of the least exponential growth rate in the two-stage guessing setup. (2) We characterize the least achievable exponential growth rate of the \u03c1-th moment of the total number of guesses required to recover Xn when Stage 1 need not end with a correct guess of Yn and without assumptions on the stationary memoryless sources producing Xn and Yn.<\/jats:p>","DOI":"10.3390\/info12040159","type":"journal-article","created":{"date-parts":[[2021,4,9]],"date-time":"2021-04-09T10:05:21Z","timestamp":1617962721000},"page":"159","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On Two-Stage Guessing"],"prefix":"10.3390","volume":"12","author":[{"given":"Robert","family":"Graczyk","sequence":"first","affiliation":[{"name":"Signal and Information Processing Laboratory, ETH Zurich, 8092 Zurich, Switzerland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5681-1273","authenticated-orcid":false,"given":"Igal","family":"Sason","sequence":"additional","affiliation":[{"name":"Andrew and Erna Viterbi Faculty of Electrical and Computer Engineering, Technion\u2013Israel Institute of Technology, Haifa 3200003, Israel"}]}],"member":"1968","published-online":{"date-parts":[[2021,4,9]]},"reference":[{"key":"ref_1","unstructured":"Massey, J.L. (July, January 27). Guessing and entropy. Proceedings of the 1994 IEEE International Symposium on Information Theory, Trondheim, Norway."},{"key":"ref_2","unstructured":"McEliece, R.J., and Yu, Z. (1995, January 17\u201322). An inequality on entropy. Proceedings of the 1995 IEEE International Symposium on Information Theory, Whistler, BC, Canada."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1109\/18.481781","article-title":"An inequality on guessing and its application to sequential decoding","volume":"42","author":"Arikan","year":"1996","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Graczyk, R., and Lapidoth, A. (2019, January 7\u201312). Two-stage guessing. Proceedings of the 2019 IEEE International Symposium on Information Theory, Paris, France.","DOI":"10.1109\/ISIT.2019.8849243"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"1756","DOI":"10.1109\/18.705557","article-title":"Joint source-channel coding and guessing with application to sequential decoding","volume":"44","author":"Arikan","year":"1998","journal-title":"IEEE Trans. Information Theory"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"2062","DOI":"10.1109\/18.641578","article-title":"Comments on \u201cAn inequality on guessing and its application to sequential decoding\u201d","volume":"43","year":"1997","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_7","unstructured":"Cachin, C. (1997). Entropy Measures and Unconditional Security in Cryptography. [Ph.D. Thesis, ETH Zurich]."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"1860","DOI":"10.1109\/18.782106","article-title":"The Shannon cipher system with a guessing wiretapper","volume":"45","author":"Merhav","year":"1999","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"6975","DOI":"10.1109\/TIT.2019.2933000","article-title":"Guessing attacks on distributed-storage systems","volume":"65","author":"Bracher","year":"2019","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1041","DOI":"10.1109\/18.669158","article-title":"Guessing subject to distortion","volume":"44","author":"Arikan","year":"1998","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Bracher, A., Lapidoth, A., and Pfister, C. (2017, January 25\u201330). Distributed task encoding. Proceedings of the 2017 IEEE International Symposium on Information Theory, Aachen, Germany.","DOI":"10.1109\/ISIT.2017.8006878"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Bracher, A., Lapidoth, A., and Pfister, C. (2019). Guessing with distributed encoders. Entropy, 21.","DOI":"10.3390\/e21030298"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"796","DOI":"10.1109\/TIT.2012.2219036","article-title":"Guesswork, large deviations, and Shannon entropy","volume":"59","author":"Christiansen","year":"2013","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Sason, I. (2018). Tight bounds on the R\u00e9nyi entropy via majorization with applications to guessing and compression. Entropy, 20.","DOI":"10.3390\/e20120896"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"4323","DOI":"10.1109\/TIT.2018.2803162","article-title":"Improved bounds on lossless source coding and guessing moments via R\u00e9nyi measures","volume":"64","author":"Sason","year":"2018","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1109\/TIT.2006.887466","article-title":"Guessing under source uncertainty","volume":"53","author":"Sundaresan","year":"2007","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1109\/TIT.2019.2920538","article-title":"Universal randomized guessing with application to asynchronous decentralized brute-force attacks","volume":"66","author":"Merhav","year":"2020","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Salamatian, S., Beirami, A., Cohen, A., and M\u00e9dard, M. (2017, January 25\u201330). Centralized versus decentralized multi-agent guesswork. Proceedings of the 2017 IEEE International Symposium on Information Theory, Aachen, Germany.","DOI":"10.1109\/ISIT.2017.8006931"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Graczyk, R., and Lapidoth, A. (2020, January 21\u201326). Gray-Wyner and Slepian-Wolf guessing. Proceedings of the 2020 IEEE International Symposium on Information Theory, Los Angeles, CA, USA.","DOI":"10.1109\/ISIT44484.2020.9174298"},{"key":"ref_20","unstructured":"Cover, T.M., and Thomas, J.A. (2006). Elements of Information Theory, John Wiley & Sons. [2nd ed.]."},{"key":"ref_21","unstructured":"R\u00e9nyi, A. (1961, January 8\u20139). On measures of entropy and information. Proceedings of the 4th Berkeley Symposium on Probability Theory and Mathematical Statistics, Berkeley, CA, USA."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Marshall, A.W., Olkin, I., and Arnold, B.C. (2011). Inequalities: Theory of Majorization and Its Applications, Springer. [2nd ed.].","DOI":"10.1007\/978-0-387-68276-1"},{"key":"ref_23","first-page":"41","article-title":"Information measures and capacity of order \u03b1 for discrete memoryless channels","volume":"Volume 16","author":"Elias","year":"1977","journal-title":"Proceedings of the 2nd Colloquium on Information Theory"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"6801","DOI":"10.1109\/TIT.2014.2357799","article-title":"On the conditional R\u00e9nyi entropy","volume":"60","author":"Fehr","year":"2014","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1109\/TIT.2017.2757496","article-title":"Arimoto\u2013R\u00e9nyi conditional entropy and Bayesian M-ary hypothesis testing","volume":"64","author":"Sason","year":"2018","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"2220","DOI":"10.1109\/TIT.2017.2787181","article-title":"Bounds on the entropy of a function of a random variable and their applications","volume":"64","author":"Cicalese","year":"2018","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_27","unstructured":"Garey, M.R., and Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completness, W. H. Freedman and Company."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Cicalese, F., Gargano, L., and Vaccaro, U. (2019, January 7\u201312). An information theoretic approach to probability mass function truncation. Proceedings of the 2019 IEEE International Symposium on Information Theory, Paris, France.","DOI":"10.1109\/ISIT.2019.8849355"},{"key":"ref_29","unstructured":"Moser, S.M. (2020). Advanced Topics in Information Theory (Lecture Notes), Institute of Communications Engeering, National Chiao Tung University. [4th ed.]."}],"container-title":["Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2078-2489\/12\/4\/159\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T14:12:15Z","timestamp":1760364735000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2078-2489\/12\/4\/159"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,9]]},"references-count":29,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2021,4]]}},"alternative-id":["info12040159"],"URL":"https:\/\/doi.org\/10.3390\/info12040159","relation":{},"ISSN":["2078-2489"],"issn-type":[{"type":"electronic","value":"2078-2489"}],"subject":[],"published":{"date-parts":[[2021,4,9]]}}}