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.

Projective Maximum Entropy: Universality and Acceptance-Region Calibration

Maximum-entropy reference distributions are usually constructed on the normalized probability simplex. This formulation is less natural for unnormalized statistical models, in which positive multiples represent the same shape, and it does not directly explain how a prescribed admissible region should determine the deformation parameter of a bounded-support reference distribution. We formulate maximum entropy on the projective space of nonnegative measures and establish three results of statistical relevance. First, a universality theorem shows that every admissible monotone transform of the same normalized power functional has exactly the same optimizer under linear moment constraints. The result unifies the maximum-entropy implications of Tsallis and Rényi entropies, Hölder composite scores, pseudo-spherical scores, Bregman--Hölder constructions, and related homogeneous divergences without asserting a new distribution family. Second, the common optimizer is characterized as a $q$-exponential density; under mean and covariance constraints it is a compactly supported $q$-Gaussian for positive deformation and a Student-type density for negative deformation. Third, a prescribed Mahalanobis acceptance region with squared radius $R^2>d+2$ uniquely determines the deformation parameter $γ_R=2/(R^2-d-2)$. The resulting affine-equivariant reference density is the unique projective maximum-entropy solution, and its support coincides with the specified ellipsoid without an additional support constraint. This provides a principled method for constructing bounded-support statistical reference distributions from robust location and scatter estimates or from externally specified admissible regions.