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 Theta(k/log k) samples. Min-entropy depends only on the most likely symbol. Both are special cases of order-α R'enyi entropy, Hα. We characterize the sample complexity of estimating min-entropy and R'enyi entropy for k and integer α>1; our lower bounds also hold for noninteger α≥1.001. We prove that min-entropy estimation to constant additive accuracy has sample complexity Theta(klog 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 Theta(log2 k) more samples than Shannon entropy and corrects a previously stated Theta(k/log k) characterization. For every integer 2≤α≤ c0log k, we prove the matching fixed-accuracy bound Thetac0(α k1-1/α). Previous results gave Omegaα(k1-1/α) for fixed integer α>1 and Oc0(α2k1-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≤α≤ c0log k, we prove the uniform lower bound Omegac0(α k1-1/α). Finally, since 0≤ Hα(p)-H_∞(p)≤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 Theta_varepsilon(klog k) sample complexity in the high-order regime.