arxivcs.ITcs.CCcs.LGmath.ST2026-07-18
Tight Sample Bounds for Renyi and Min-Entropy Estimation
Estimating entropy from samples is fundamental in information theory and property testing. Shannon entropy measures average uncertainty and can be estimated to constant additive accuracy over a $k$-symbol alphabet using $Θ(k/\log k)$ samples. Min-entropy depends only on the most…