Tight Sample Bounds for Renyi and Min-Entropy Estimation

Abstract

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-$\alpha$ R'{e}nyi entropy, $H_\alpha$. We characterize the sample complexity of estimating min-entropy and R'{e}nyi entropy for $k$ and integer $\alpha>1$; our lower bounds also hold for noninteger $\alpha\ge1.001$. We prove that min-entropy estimation to constant additive accuracy has sample complexity $\Theta(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 $\Theta(\log^2 k)$ more samples than Shannon entropy and corrects a previously stated $\Theta(k/\log k)$ characterization. For every integer $2\le\alpha\le c_0\log k$, we prove the matching fixed-accuracy bound $\Theta_{c_0}(\alpha k^{1-1/\alpha})$. Previous results gave $\Omega_\alpha(k^{1-1/\alpha})$ for fixed integer $\alpha>1$ and $O_{c_0}(\alpha^2k^{1-1/\alpha})$ for all integer $\alpha>1$. Our upper bound analyzes an unbiased falling-factorial estimator based on $\alpha$-way collisions, while a hidden-heavy-coordinate construction gives the matching lower bound and shows that the factor $\alpha$ is unavoidable. For every real $1.001\le\alpha\le c_0\log k$, we prove the uniform lower bound $\Omega_{c_0}(\alpha k^{1-1/\alpha})$. Finally, since $0\le H_\alpha(p)-H_\infty(p)\le\log k/(\alpha-1)$, min-entropy uniformly approximates $H_\alpha$ when $\alpha$ is a sufficiently large multiple of $\log k$. Combining this reduction with our min-entropy bounds gives $\Theta_\varepsilon(k\log k)$ sample complexity in the high-order regime.