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 likely symbol. Both are special cases of order-α R'{e}nyi entropy, H_α. We characterize the sample complexity of estimating min-entropy and R'{e}nyi entropy for k and integer α>1; our lower bounds also hold for noninteger α\ge1.001. We prove that min-entropy estimation to constant additive accuracy has sample complexity Θ(k\log k). The upper bound uses the largest empirical frequency and concentration via dyadic grouping. The matching lower bound hides a slightly heavier symbol at a uniformly random location. Thus, min-entropy requires Θ(\log^2 k) more samples than Shannon entropy and corrects a previously stated Θ(k/\log k) characterization. For every integer 2\leα\le c_0\log k, we prove the matching fixed-accuracy bound Θ_{c_0}(αk^{1-1/α}). Previous results gave Ω_α(k^{1-1/α}) for fixed integer α>1 and O_{c_0}(α^2k^{1-1/α}) for all integer α>1. Our upper bound analyzes an unbiased falling-factorial estimator based on α-way collisions, while a hidden-heavy-coordinate construction gives the matching lower bound and shows that the factor α is unavoidable. For every real 1.001\leα\le c_0\log k, we prove the uniform lower bound Ω_{c_0}(αk^{1-1/α}). Finally, since 0\le H_α(p)-H_\infty(p)\le\log k/(α-1), min-entropy uniformly approximates H_α when α is a sufficiently large multiple of \log k. Combining this reduction with our min-entropy bounds gives Θ_\varepsilon(k\log k) sample complexity in the high-order regime.