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 \ge 1.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 }^2{k}^{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 }_{\epsilon }(k\log k)$ sample complexity in the high-order regime.