{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,5]],"date-time":"2026-10-05T18:19:55Z","timestamp":1791224395214,"version":"4.1.0"},"reference-count":48,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2023,1,17]],"date-time":"2023-01-17T00:00:00Z","timestamp":1673913600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>Estimation of R\u00e9nyi entropy is of fundamental importance to many applications in cryptography, statistical inference, and machine learning. This paper aims to improve the existing estimators with regard to: (a) the sample size, (b) the estimator adaptiveness, and (c) the simplicity of the analyses. The contribution is a novel analysis of the generalized \u201cbirthday paradox\u201d collision estimator. The analysis is simpler than in prior works, gives clear formulas, and strengthens existing bounds. The improved bounds are used to develop an adaptive estimation technique that outperforms previous methods, particularly in regimes of low or moderate entropy. Last but not least, to demonstrate that the developed techniques are of broader interest, a number of applications concerning theoretical and practical properties of \u201cbirthday estimators\u201d are discussed.<\/jats:p>","DOI":"10.3390\/e25020185","type":"journal-article","created":{"date-parts":[[2023,1,17]],"date-time":"2023-01-17T04:28:47Z","timestamp":1673929727000},"page":"185","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Towards More Efficient R\u00e9nyi Entropy Estimation"],"prefix":"10.3390","volume":"25","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2997-7539","authenticated-orcid":false,"given":"Maciej","family":"Skorski","sequence":"first","affiliation":[{"name":"Faculty of Mathematics, Informatics and Mechanics, University of Warsaw, 00-927 Warszawa, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2023,1,17]]},"reference":[{"key":"ref_1","unstructured":"R\u00e9nyi, A. (July, January 20). On measures of information and entropy. Proceedings of the 4th Berkeley Symposium on Mathematics, Statistics and Probability, Berkeley, CA, USA."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Masisi, L., Nelwamondo, V., and Marwala, T. (2008, January 27\u201329). The use of entropy to measure structural diversity. Proceedings of the 2008 IEEE International Conference on Computational Cybernetics, Stara Lesna, Slovakia.","DOI":"10.1109\/ICCCYB.2008.4721376"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1556\/ComEc.6.2005.2.13","article-title":"Generalised entropy indices have a long history in ecology\u2014A comment","volume":"6","year":"2005","journal-title":"Community Ecol."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Leinster, T., and Meckes, M. (2016). Maximizing Diversity in Biology and Beyond. Entropy, 18.","DOI":"10.3390\/e18030088"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1016\/S0378-4371(00)00007-8","article-title":"Statistical mechanics based on Renyi entropy","volume":"280","author":"Lenzi","year":"2000","journal-title":"Phys. A Stat. Mech. Its Appl."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"174307","DOI":"10.1103\/PhysRevB.91.174307","article-title":"Exact correspondence between Renyi entropy flows and physical flows","volume":"91","author":"Ansari","year":"2015","journal-title":"Phys. Rev. B"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1016\/j.physletb.2015.11.061","article-title":"R\u00e9nyi entropy and the thermodynamic stability of black holes","volume":"752","author":"Czinner","year":"2016","journal-title":"Phys. Lett. B"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"798","DOI":"10.1016\/j.spl.2012.01.004","article-title":"Characterizations of symmetric distributions based on R\u00e9nyi entropy","volume":"82","author":"Fashandi","year":"2012","journal-title":"Stat. Probab. Lett."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1486","DOI":"10.1016\/j.ins.2009.12.012","article-title":"R\u00e9nyi entropy rate for Gaussian processes","volume":"180","author":"Golshani","year":"2010","journal-title":"Inf. Sci."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1016\/j.jtbi.2004.06.030","article-title":"R\u00e9nyi continuous entropy of DNA sequences","volume":"231","author":"Vinga","year":"2004","journal-title":"J. Theor. Biol."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Vinga, S., and Almeida, J.S. (2007). Local Renyi entropic profiles of DNA sequences. BMC Bioinform., 8.","DOI":"10.1186\/1471-2105-8-393"},{"key":"ref_12","unstructured":"Li, K., Zhou, W., Yu, S., and Dai, B. (2009, January 8\u201311). Effective DDoS Attacks Detection Using Generalized Entropy Metric. Proceedings of the Algorithms and Architectures for Parallel Processing, 9th International Conference, ICA3PP 2009, Taipei, Taiwan."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"2367","DOI":"10.3390\/e17042367","article-title":"An Entropy-Based Network Anomaly Detection Method","volume":"17","author":"Jasiul","year":"2015","journal-title":"Entropy"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"2251","DOI":"10.1016\/j.patcog.2011.12.017","article-title":"Determining the number of clusters using information entropy for mixed data","volume":"45","author":"Liang","year":"2012","journal-title":"Pattern Recognit."},{"key":"ref_15","unstructured":"Jenssen, R., Hild, K., Erdogmus, D., Principe, J., and Eltoft, T. (2003, January 20\u201324). Clustering using Renyi\u2019s entropy. Proceedings of the International Joint Conference on Neural Networks, Portland, OR, USA."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Cornforth, D.J., and Jelinek, H.F. (2016, January 11\u201314). Detection of congestive heart failure using Renyi entropy. Proceedings of the 2016 Computing in Cardiology Conference (CinC), Vancouver, BC, Canada.","DOI":"10.22489\/CinC.2016.196-231"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Cornforth, D.J., Tarvainen, M.P., and Jelinek, H.F. (2013, January 3\u20137). Using renyi entropy to detect early cardiac autonomic neuropathy. Proceedings of the 2013 35th Annual International Conference of the IEEE Engineering in Medicine and Biology Society (EMBC), Osaka, Japan.","DOI":"10.1109\/EMBC.2013.6610810"},{"key":"ref_18","first-page":"39","article-title":"Comparison of Decision Trees with R\u00e9nyi and Tsallis Entropy Applied for Imbalanced Churn Dataset","volume":"5","author":"Gajowniczek","year":"2015","journal-title":"Ann. Comput. Sci. Inf. Syst."},{"key":"ref_19","unstructured":"Knuth, D.E. (1998). The Art of Computer Programming, Volume 3: (2Nd Ed.) Sorting and Searching, Addison Wesley Longman Publishing Co., Inc."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/PL00003816","article-title":"Parallel Collision Search with Cryptanalytic Applications","volume":"12","author":"Wiener","year":"1999","journal-title":"J. Cryptol."},{"key":"ref_21","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_22","doi-asserted-by":"crossref","first-page":"2794","DOI":"10.1109\/TIT.2004.836665","article-title":"R\u00e9nyi Entropy, Guesswork Moments, and Large Deviations","volume":"50","author":"Pfister","year":"2004","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1109\/TIT.2010.2090221","article-title":"Guessing Revisited: A Large Deviations Approach","volume":"57","author":"Hanawal","year":"2011","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_24","unstructured":"Impagliazzo, R., and Zuckerman, D. (November, January 30). How to Recycle Random Bits. Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, NC, USA."},{"key":"ref_25","unstructured":"Mitzenmacher, M., and Vadhan, S. Why simple hash functions work: Exploiting the entropy in a data stream. Proceedings of the Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"1915","DOI":"10.1109\/18.476316","article-title":"Generalized privacy amplification","volume":"41","author":"Bennett","year":"1995","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Barak, B., Dodis, Y., Krawczyk, H., Pereira, O., Pietrzak, K., Standaert, F.X., and Yu, Y. (2011, January 14\u201318). Leftover Hash Lemma, Revisited. Proceedings of the Advances in Cryptology\u2014CRYPTO 2011\u201431st Annual Cryptology Conference, Santa Barbara, CA, USA.","DOI":"10.1007\/978-3-642-22792-9_1"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Dodis, Y., and Yu, Y. (2013, January 3\u20136). Overcoming Weak Expectations. Proceedings of the Theory of Cryptography\u201410th Theory of Cryptography Conference (TCC 2013), Tokyo, Japan.","DOI":"10.1007\/978-3-642-36594-2_1"},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Xu, D., and Erdogmuns, D. (2010). Renyi\u2019s Entropy, Divergence and Their Nonparametric Estimators. Information Theoretic Learning, Springer.","DOI":"10.1007\/978-1-4419-1570-2_2"},{"key":"ref_30","unstructured":"Cachin, C. Smooth entropy and R\u00e9nyi entropy. Proceedings of the 16th Annual International Conference on Theory and Application of cRyptographic Techniques (EUROCRYPT\u201997)."},{"key":"ref_31","unstructured":"Renner, R., and Wolf, S. (July2004, January 27). Smooth Renyi entropy and applications. Proceedings of the 2004 IEEE International Symposium on Information Theory (ISIT 2004), Chicago Downtown Marriott, Chicago, IL, USA."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1109\/TIT.2016.2620435","article-title":"Estimating Renyi Entropy of Discrete Distributions","volume":"63","author":"Acharya","year":"2017","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"531","DOI":"10.1016\/S0076-6879(09)67020-8","article-title":"Nonparametric Entropy Estimation Using Kernel Densities","volume":"Volume 467","author":"Lake","year":"2009","journal-title":"Methods in Enzymology"},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Acharya, J., Orlitsky, A., Suresh, A.T., and Tyagi, H. (2015, January 4\u20136). The Complexity of Estimating R\u00e9nyi Entropy. Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), San Diego, CA, USA.","DOI":"10.1137\/1.9781611973730.124"},{"key":"ref_35","unstructured":"Obremski, M., and Skorski, M. Renyi Entropy Estimation Revisited. Approximation, Randomization, and Combinatorial Optimization, Algorithms and Techniques (APPROX\/RANDOM 2017), Leibniz-Zentrum fuer Informatik."},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Schaub, A., Rioul, O., and Boutros, J.J. (2019, January 24\u201327). Entropy Estimation of Physically Unclonable Functions via Chow Parameters. Proceedings of the 2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton), Monticello, IL, USA.","DOI":"10.1109\/ALLERTON.2019.8919927"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"1","DOI":"10.4086\/cjtcs.2019.001","article-title":"Collision-Based Testers are Optimal for Uniformity and Closeness","volume":"25","author":"Diakonikolas","year":"2019","journal-title":"Chic. J. Theor. Comput. Sci."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1214\/aoms\/1177730196","article-title":"A Class of Statistics with Asymptotically Normal Distribution","volume":"19","author":"Hoeffding","year":"1948","journal-title":"Ann. Math. Stat."},{"key":"ref_39","unstructured":"Ferguson, T.S. (2005). U-Statistics. Lecture Notes for Statistics, University of California-Los Angeles."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"1145","DOI":"10.1007\/s10208-019-09427-x","article-title":"Mean Estimation and Regression Under Heavy-Tailed Distributions: A Survey","volume":"19","author":"Lugosi","year":"2019","journal-title":"Found. Comput. Math."},{"key":"ref_41","unstructured":"Skorski, M. (2022, November 02). Machine Learning Examples. Available online: https:\/\/github.com\/maciejskorski\/ml_examples\/blob\/master\/RenyiEntropyEstimation.ipynb."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1239\/jap\/1245676089","article-title":"Fixed precision MCMC estimation by median of products of averages","volume":"46","author":"Niemiro","year":"2009","journal-title":"J. Appl. Probab."},{"key":"ref_43","first-page":"219","article-title":"Completeness, Similar Regions, and Unbiased Estimation: Part II","volume":"15","author":"Lehmann","year":"1955","journal-title":"Sankhy\u0101 Indian J. Stat. (1933\u20131960)"},{"key":"ref_44","first-page":"305","article-title":"Completeness, Similar Regions, and Unbiased Estimation: Part I","volume":"10","author":"Lehmann","year":"1950","journal-title":"Sankhy\u0101 Indian J. Stat. (1933\u20131960)"},{"key":"ref_45","unstructured":"Goldreich, O., and Ron, D. (2000). On testing expansion in bounded-degree graphs. Electronic Colloquium on Computational Complexity (ECCC), Springer."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"4750","DOI":"10.1109\/TIT.2008.928987","article-title":"A Coincidence-Based Test for Uniformity Given Very Sparsely Sampled Discrete Data","volume":"54","author":"Paninski","year":"2008","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_47","doi-asserted-by":"crossref","unstructured":"Konca, S., Idris, M., and Gunawan, H. (2015). p-Summable Sequence Spaces with Inner Products. Bitlis Eren Univ. J. Sci. Technol., 5.","DOI":"10.17678\/beujst.06700"},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1007\/BF01651330","article-title":"Correlation Inequalities on Some Partially Ordered Sets","volume":"22","author":"Fortuin","year":"1971","journal-title":"Commun. Math. Phys."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/25\/2\/185\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T18:08:04Z","timestamp":1760119684000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/25\/2\/185"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,17]]},"references-count":48,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2023,2]]}},"alternative-id":["e25020185"],"URL":"https:\/\/doi.org\/10.3390\/e25020185","relation":{},"ISSN":["1099-4300"],"issn-type":[{"value":"1099-4300","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,1,17]]}}}