{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:28:12Z","timestamp":1760243292289,"version":"build-2065373602"},"reference-count":12,"publisher":"MDPI AG","issue":"7","license":[{"start":{"date-parts":[[2014,7,23]],"date-time":"2014-07-23T00:00:00Z","timestamp":1406073600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF 1065632","CCF 1018984"],"award-info":[{"award-number":["CCF 1065632","CCF 1018984"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>The minimum expected number of bits needed to describe a random variable is its entropy, assuming knowledge of the distribution of the random variable. On the other hand, universal compression describes data supposing that the underlying distribution is unknown, but that it belongs to a known set \u03a1 of distributions. However, since universal descriptions are not matched exactly to the underlying distribution, the number of bits they use on average is higher, and the excess over the entropy used is the redundancy. In this paper, we study the redundancy incurred by the universal description of strings of positive integers (Z+), the strings being generated independently and identically distributed (i.i.d.) according an unknown distribution over Z+ in a known collection P. We first show that if describing a single symbol incurs finite redundancy, then P is tight, but that the converse does not always hold. If a single symbol can be described with finite worst-case regret (a more stringent formulation than redundancy above), then it is known that describing length n i.i.d. strings only incurs vanishing (to zero) redundancy per symbol as n increases. On the contrary, we show it is possible that the description of a single symbol from an unknown distribution of P incurs finite redundancy, yet the description of length n i.i.d. strings incurs a constant (&gt; 0) redundancy per symbol encoded. We then show a sufficient condition on single-letter marginals, such that length n i.i.d. samples will incur vanishing redundancy per symbol encoded.<\/jats:p>","DOI":"10.3390\/e16074168","type":"journal-article","created":{"date-parts":[[2014,7,23]],"date-time":"2014-07-23T11:03:10Z","timestamp":1406113390000},"page":"4168-4184","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Characterizing the Asymptotic Per-Symbol Redundancy of Memoryless Sources over Countable Alphabets in Terms of Single-Letter Marginals"],"prefix":"10.3390","volume":"16","author":[{"given":"Maryam","family":"Hosseini","sequence":"first","affiliation":[{"name":"Department of Electrical Engineering, University of Hawaii at Manoa, Honolulu, HI 96822, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Narayana","family":"Santhanam","sequence":"additional","affiliation":[{"name":"Department of Electrical Engineering, University of Hawaii at Manoa, Honolulu, HI 96822, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2014,7,23]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"1469","DOI":"10.1109\/TIT.2004.830761","article-title":"Universal compression of memoryless sources over unknown alphabets","volume":"50","author":"Orlitsky","year":"2004","journal-title":"IEEE Tran. Inf. Theory"},{"key":"ref_2","unstructured":"Boucheron, S., Garivier, A., and Gassiat, E. (2008). Coding on countably infinite alphabets., arXiv.org: 0801.2456."},{"key":"ref_3","unstructured":"Santhanam, N., Anantharam, V., Kavcic, A., and Szpankowski, W. (July, January 29). Data driven weak universal redundancy. Honolulu, HI, USA."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"2124","DOI":"10.1109\/18.720534","article-title":"Universal prediction","volume":"44","author":"Merhav","year":"1998","journal-title":"IEEE Tran. Inf. Theory"},{"key":"ref_5","unstructured":"Rosenthal, J.S. (2008). A First Look at Rigorous Probability Theory, World Scientific. [2nd ed. ]."},{"key":"ref_6","unstructured":"Santhanam, N. (2006). Probability Estimation and Compression Involving Large Alphabets, Ph.D. Thesis, University of California, San Diego, CA, USA."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Kingman, J.F.C. (1980). The Mathematics of Genetic Diversity, SIAM.","DOI":"10.1137\/1.9781611970357"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1007\/BF00485351","article-title":"Predicting the unpredictable","volume":"90","author":"Zabell","year":"1992","journal-title":"Synthese"},{"key":"ref_9","unstructured":"Earman, J., and Norton, J.D. (1997). The Cosmos of Science: Essays of Exploration, The University of Pittsburgh Press. Chapter 12."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Zabell, S.L. (2005). Symmetry and Its Discontents: Essays on the History of Inductive Probability, Cambridge University Press. Cambridge Studies in Probability, Induction, and Decision Theory.","DOI":"10.1017\/CBO9780511614293"},{"key":"ref_11","unstructured":"Santhanam, N., and Anantharam, V. (2012). Agnostic insurance of model classes, arXiv.org: 1212:3866."},{"key":"ref_12","unstructured":"Orlitsky, A., and Santhanam, N. Lecture notes on universal compression. Available online: http:\/\/www-ee.eng.hawaii.edu\/~prasadsn\/."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/16\/7\/4168\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T21:13:59Z","timestamp":1760217239000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/16\/7\/4168"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,7,23]]},"references-count":12,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2014,7]]}},"alternative-id":["e16074168"],"URL":"https:\/\/doi.org\/10.3390\/e16074168","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2014,7,23]]}}}