Is the harmonic entropy estimator minimax optimal for infinite-alphabet distributions?

Why log-transformed counts blocked infinite alphabets

Estimating Shannon entropy H(X) = −E[log p(X)] from a finite sample is well understood when the support is finite. The plug-in estimator, which replaces each probability with its empirical frequency, is asymptotically normal when the sample is much larger than a fixed support, and minimax rates are known for large but finite alphabets. Extending those guarantees to countably infinite support has been harder, and the paper states that no prior literature addresses asymptotic normality or efficiency for unbounded distributions.

The paper attributes the gap to a structural mismatch. Bias and variance of entropy estimators require expectations of logarithm-transformed multinomial counts, and those expectations have no closed form. Analyses therefore rely on bounding arguments, which introduce approximation error and make the leading variance term hard to isolate. The harmonic estimator is introduced specifically to replace those bounds with exact algebraic expressions.

An exact identity linking harmonic counts to log-probabilities

The construction rests on the harmonic number J(m) = 1 + 1/2 + … + 1/m, with J(0) = 0. For a symbol observed m^(i) times among n draws, the estimator averages J(n−1) − J(m^(i) − 1) over all n sample points. The key result, Proposition II.2, is an identity showing that the expectation of a harmonic-transformed binomial count equals the local entropy −log p plus a remainder governed by sample size.

That identity is what makes the analysis tractable. Because the bias can be written exactly rather than bounded, the paper can characterize first- and second-order moments of harmonic-transformed binomial and multinomial counts without approximation error. The author notes the estimator has a more compact form using the digamma function, and that the harmonic-number version is sufficient to derive the central identities. The direction is explicitly modeled on the Kozachenko-Leonenko nearest-neighbor estimator for differential entropy, whose analysis uses an analogous identity linking the digamma function to expected log-probabilities of neighbors.

The minimax rate is 1/n when tails decay at least quadratically

Theorem I.1 states that over the class of distributions with p_j ≲ j^-2, the infimum over entropy estimators of the supremum over that class of expected squared error is of order 1/n as n grows. The rate is anchored by estimator variance, and the paper emphasizes that this variance convergence holds for both finite- and infinite-support distributions.

This complements rather than duplicates earlier large-alphabet results. Those results let support size grow with sample size, so variance dominates when the support is small relative to n and squared bias dominates otherwise. Here the parameter space is fixed while n increases, so the variance rate always governs. The paper notes that all these results agree on the convergence rate for fixed, finite support as n grows.

The risk decomposition in Corollary II.1 makes the boundary visible. For tail parameter α in (0, 1/2], meaning tails decaying as fast as or faster than j^-2, risk is dominated by variance and converges at O(1/n). For α in (1/2, 1), heavier tails let squared bias dominate and the rate slows to O(n^−2(1−α)).

Semiparametric efficiency requires strictly faster than quadratic decay

Theorem I.2 strengthens the tail condition to p_j = o(j^-2). Under that condition Var[log p(X)] is finite and √n[H(X_n) − H(X)] converges in distribution to a normal with variance Var[log p(X)], which the paper identifies as the semiparametric efficiency bound for this problem.

The distinction between the two theorems is not cosmetic. At the boundary p_j ≲ j^-2, squared bias is O(1/n), the same order as the variance, so the bias is comparable to the standard deviation and the scaled estimator does not converge to a zero-mean normal. The stricter condition is what makes the √n-scaled bias vanish. Readers comparing the two results should therefore keep the tail condition attached to each claim: the 1/n minimax rate and the efficiency statement apply to different, nested classes of distributions.

The harmonic estimator is less biased than the plug-in in every regime

Proposition V.1 states that the harmonic estimator is universally less biased than the plug-in estimator. The paper traces the plug-in's excess bias to approximation error introduced by the logarithm inside a binomial expectation. A Taylor expansion of −x log x about p_j produces a leading bias term of −(s−1)/(2n), where s is the number of support points, plus higher-order terms containing central moments that are not easily characterized; any remainder bound worsens as p_j approaches zero.

The paper also reports that existing bias-correction strategies for the plug-in are first-order approximations of the harmonic estimator, and that the plug-in is itself minimax rate-optimal over p_j ≲ j^-2. Even so, the harmonic estimator keeps an advantage: for p_j = o(j^-2) its asymptotic variance already attains the semiparametric efficiency bound, so the plug-in cannot improve on it there. The author conjectures that the plug-in is also semiparametrically efficient in that regime, but notes the harmonic estimator would retain its analytical tractability and its reduced bias, while sharing the plug-in's simple one-step form.

Heavy tails and negative bias mark the edge of the guarantees

The harmonic estimator is negatively biased in all settings, and in heavy-tailed regimes where p_j is not ≲ j^-2 its L2 convergence rate exceeds the minimax lower bound of Ω(1/n) because of increased bias. Whether the 1/n minimax rate extends into that regime remains open. A formal bias-correction procedure has not been developed; the paper suggests it might extend the rate beyond p_j ≲ j^-2, but that would require showing the corrected estimator keeps L2 risk dominated by O(1/n) on heavier-tailed distributions, or alternatively establishing a lower bound rate greater than Ω(1/n) together with an estimator matching it.

A second limitation concerns inference rather than estimation. Theorem I.2 establishes the asymptotic distribution but stops short of providing a consistent estimator for Var[log p(X)]. The paper describes a variance estimator built on harmonic-transformed counts that would require a bound on a fourth-order estimator moment; combined with the asymptotic normality, that would enable valid Wald-style confidence intervals for entropy. Until then, the efficiency result characterizes the limit distribution rather than supplying a complete inference procedure.

Tail decay, not estimator choice alone, decides the guarantee

The paper's most decision-relevant split is the tail condition. If a distribution's tail decays at least quadratically, the entropy estimation problem has an L2-minimax rate of 1/n, and the harmonic estimator attains it. If the tail decays strictly faster than quadratically, the harmonic estimator additionally achieves the semiparametric efficiency bound Var[log p(X)] and is asymptotically normal at the √n scale. If the tail is heavier than quadratic, the rate guarantee no longer holds and the estimator's negative bias dominates the risk.

Within the covered regimes, the harmonic estimator's case rests on two things the plug-in does not offer together: exact moment expressions that make the leading variance term isolable, and bias that is uniformly smaller. The author frames the broader value as a tractable platform for further theory, including a possible route to proving the plug-in conjecture and extension to mutual information and other entropy-based measures under similar nonparametric regimes. The concrete priority for a reader is therefore to check tail decay first, then read the efficiency claim as conditional on strictly faster-than-quadratic decay rather than as a general property of entropy estimation on infinite alphabets.

Sources used in this answer