Skip to content
DraconiticResearch
Search Sources API
194,164 studies31 sourcesUpdated 4 min ago
PreprintCC BY 4.0arXiv

Birthday Estimators Are Uniformly Optimal for Renyi Entropy

  • Maciej Skórski
Open at sourcePDFDOICite

Abstract

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 integer-order Rényi entropy estimation up to absolute constants in all regimes, closing the gap between the best known upper and lower bounds. Our concentration bound rests on a sensitivity analysis of collision count, and the matching lower bound on a sharp analysis of detecting a hidden spike in a plateau distribution.

Related

  1. Optimal Rényi and Logarithmic Additive Functional Entropy Estimation
    Arman Adibi, Piotr Krysta
    arXivPreprintCC BY 4.0Full textStatisticsarXiv
  2. Bias-Corrected Estimators for Joint Entropy, Conditional Entropy, and Mutual Information in the Discrete Bivariate Case: Theory and an Application to Motor Insurance
    Amadou Diadie Ba
    arXivPreprintCC BY 4.0Full textStatisticsarXiv
  3. Eigenvector distributions and optimal shrinkage estimators for large covariance and precision matrices
    Xiucai Ding, Yun Li, Fan Yang
    Applied and Computational Harmonic AnalysisPeer-reviewedLicence not statedFull text5 citedStatisticsOpenAlex
  4. Optimal Two‐Phase Sampling Designs for Generalized Raking Estimators With Multiple Parameters of Interest
    Jasper B. Yang, Bryan E. Shepherd, Thomas Lumley +1
    Statistics in medicinePeer-reviewedCC BYFull textStatisticsEurope PMC
  5. Counterexamples to additivity of minimum output p-Rényi entropy of quantum channels for all p≥ 0
    Debbie Leung, Benjamin Lovitz, Ion Nechita +1
    arXivPreprintCC BY 4.0Full textMathematical physicsProbabilityarXiv

Cite

BibTeXRIS
BibTeX
@misc{skorski2026birthday,
  title = {{Birthday Estimators Are Uniformly Optimal for Renyi Entropy}},
  author = {Maciej Skórski},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.28581},
  eprint = {2610.28581},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.28581},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Birthday Estimators Are Uniformly Optimal for Renyi Entropy
AU  - Maciej Skórski
PY  - 2026
DA  - 2026/10/20
PB  - arXiv
DO  - 10.48550/arxiv.2610.28581
UR  - https://arxiv.org/abs/2610.28581
AB  - 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 integer-order Rényi entropy estimation up to absolute constants in all regimes, closing the gap between the best known upper and lower bounds. Our concentration bound rests on a sensitivity analysis of collision count, and the matching lower bound on a sharp analysis of detecting a hidden spike in a plateau distribution.
ER  -