Optimal Rényi and Logarithmic Additive Functional Entropy Estimation

Abstract

We characterize the minimax sample complexity of estimating Rényi entropy from independent samples on an alphabet of size at most $k$, when the known order $\alpha >1$ may vary with $k$. For every fixed additive accuracy $\epsilon \in (0,1/2)$ and success probability $2/3$, we prove matching bounds with constants independent of $k$ and $\alpha$. For $1<\alpha <\log k$, the rate is ${\Theta }_{\epsilon }(\alpha k^{1-1/\alpha }{X}_{\alpha }(k,\epsilon ))$, where a monotone scalar inequality defines $X_{\alpha }$ at noninteger orders. The bounds remain uniform as the order approaches one or an integer, or grows with the alphabet. Integer orders below $\log k$ have rate ${\Theta }_{\epsilon }(\alpha k^{1-1/\alpha })$; orders at least $\log k$ and min-entropy have rate ${\Theta }_{\epsilon }(k\log k)$. We extend the analysis to logarithms of positive additive functionals. For every fixed continuous $f$ satisfying $f(0)=0$, $f(x)>0$ for $x>0$, and $f(x)\sim a{x}^r$ at zero, with $a>0$ and $r>1$, estimating $-{\beta }^{-1}\log {\sum }_{i}f(p_i)$ at fixed accuracy, for fixed $\beta >0$, has sample complexity $\Theta (k^{1-1/r})$ for integer $r$ and $\Theta (k/\log k)$ otherwise. A replication reduction preserves the sampling experiment and transfers the rates for powers. Smooth flat functions show that regularity alone does not determine the complexity. The upper bound combines polynomial approximation, Gamma count statistics, and an independent pilot, with a global affine correction near order one. The lower bound uses interpolation to construct positive mean-one priors and controls their distinguishability and entropy separation after normalization. Exact count-variance identities and weighted approximation duality connect the two arguments.