{"id":"arxiv/2610.28581","url":"https://arxiv.org/abs/2610.28581","tags":["cs.IT","cs.DS","math.PR","math.ST"],"score":0,"title":"Birthday Estimators Are Uniformly Optimal for Renyi Entropy","domain":"cs.IT","source":"arxiv","authors":["Maciej Skórski"],"reviews":0,"subject":"cs.IT","summary":"Collisions are a basic probe of unknown distributions, used for testing and for counting substructures in graphs, and they underlie Rényi entropy, a fundamental measure of uncertainty with applications in cryptography, machine learning, physics, and biology. Motivated by this, we study the natural birthday estimator. We prove Bernstein-type concentration for it and show that it is minimax optimal, uniformly and jointly in alphabet size, order, accuracy, and confidence, with no sample splitting, clipping, or median aggregation. This, in particular, settles the sample complexity of…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-20","reactions":{}}