Honest Confidence Intervals for Entropy on Large Alphabets

When the number of possible categories is about as large as the number of observations (words in a text, species in a survey, distinct queries in a log), the best known estimators of entropy and support size split symbols by how often they were seen. Frequent symbols get the ordinary empirical estimate. Rare and unseen symbols get a specially designed correction. These estimators reach the optimal error rate, but they come with two practical defects. The theory requires throwing away half the data to decide which symbols count as rare. And nobody reports whether the error bars around the estimate are trustworthy. This proposal addresses both by borrowing a lesson from high-dimensional statistics. There, small per-coordinate biases that are individually harmless add up across thousands of coordinates, and the result is confidence intervals that miss the truth far more often than advertised.

The core idea is to stop splitting the sample. If the same counts are used both to decide which symbols are rare and to estimate them, the estimator picks up a "selection bias" from symbols whose counts sit near the rare/frequent threshold. That bias can be computed exactly as a function of each symbol's true probability, and it is concentrated on symbols with counts of order $\log k$. At that level counts are informative enough to estimate the bias and subtract it. The output is a full-sample estimator plus an interval that accounts for bias explicitly. The deliverable is measured by coverage, meaning how often the nominal 95% interval actually contains the true entropy. Large-alphabet work has not used this criterion, while high-dimensional inference treats it as the main test.

What the two literatures contribute

The first literature supplies the estimator. Wu and Yang split the sample into two halves. One half identifies symbols whose probability is below roughly $\log k / n$. On those symbols, $-p\log p$ is replaced by its best approximating polynomial of degree about $\log k$, which can be estimated without bias from Poisson counts. This yields minimax mean-squared error $\asymp (k/(n\log k))^2 + \log^2 k / n$. Fukuchi and Sakuma generalize the same split construction to arbitrary additive functionals $\sum_i \phi(p_i)$. Charikar, Shiragur and Sidford apply it with profile maximum likelihood on the rare set, and they remark that splitting is an analytical artifact rather than a practical necessity. That remark motivates this proposal: it is a claim nobody has quantified, and quantifying it is our starting point.

The second literature supplies the diagnosis and the correction tool. Zhou and Li study additive functions of a $d$-dimensional mean observed under Gaussian noise. They show that the plug-in estimator's bias grows like $d/n$, so that nominal 95% intervals collapse as $d$ approaches $n$. They remove the bias with an iterative bootstrap that sums a Neumann series. Zhou, Li and Zhang extend this correction to non-Gaussian noise. Yadlowsky et al. document the same phenomenon in logistic regression, where 90% intervals fall to 60–70% coverage. They also show that an analytic leave-one-out approximation can replace data splitting.

We reuse two things from this side: the Neumann-series correction, transplanted from Gaussian to Poisson observations, and coverage as the yardstick. Both papers in the Zhou line treat all coordinates identically and assume smooth component functions. We instead apply the correction only to a band of moderately frequent symbols, and we leave the non-smooth tail to polynomial approximation.

Two results constrain the design. Jiao, Venkat, Han and Weissman prove that Dirichlet pseudo-count smoothing cannot improve the plug-in rate for entropy. de Campos and Benavoli show that fixed-strength Dirichlet priors become inadmissible as $k$ grows. Together they rule out a cheap Bayesian fix for the tail.

Core Claim

Under Poisson sampling, each symbol's count $N_i$ is independent with mean $n p_i$. Any split-free hybrid estimator, whether polynomial or plug-in, can therefore be written as $\hat H = \sum_i f(N_i)$ for a single count function $f$. This $f$ uses the polynomial estimator for counts at or below a threshold $\tau$, and a Miller–Madow-corrected plug-in above it. The bias is then a sum of a known function evaluated at each true probability:

$$ \mathbb{E}\hat H - H = \sum_{i=1}^k b(p_i), \qquad b(p) = \sum_{j\ge 0} f(j)\, e^{-np}\frac{(np)^j}{j!} \;-\; \big(-p\log p\big). $$

Here $b(p)$ splits into two parts. The first is a polynomial-approximation error, which is small and controlled on the tail. The second is a selection term created by truncating the polynomial estimator at $\tau$, which destroys its unbiasedness. The selection term is largest for $p$ near $\tau/n$. Up to about $n/\tau$ symbols can sit in that band. The selection bias is therefore cumulative in exactly the sense of Zhou and Li: each symbol contributes little, but there are many symbols.

A rough calculation shows why this matters. At the worst-case Wu–Yang rate with $k = n = 10^5$, the bias term is about $1/\log k \approx 0.09$ nats, while the standard deviation is about $\log k/\sqrt n \approx 0.04$. Bias, not variance, is what breaks intervals. Our claim is that the boundary part of the bias can be estimated well, because counts there are of order $\log k$. The tail part cannot be removed, but it can be bounded and folded into the interval width. Together these steps give near-nominal coverage at full-sample efficiency.

Research Program

The work has three parts.

The first is analysis. We will compute $b(p)$ in closed form for entropy and support size. We will then bound the selection term as a function of $\tau$ and the polynomial degree. Finally, we will characterize the alphabet-to-sample ratios at which the uncorrected split-free estimator's bias exceeds its standard deviation. In that regime, naive intervals must fail.

The second is the correction itself. Following the Neumann-series construction of Zhou and Li, we estimate $\sum_i b(p_i)$ by plugging in $\hat p_i = N_i/n$, but only for symbols with counts in a band $[\tau/2, 2\tau]$. We subtract this estimate and iterate once or twice, since each iteration reduces the bias by a further factor. The band restriction is the key design choice. Bootstrapping the whole alphabet would resample from an empirical distribution that has no unseen mass, and it would reproduce exactly the bias we are trying to estimate.

The third is the interval. Its center is the corrected estimate. Its half-width combines a standard-error term with an explicit bound on the residual tail-approximation bias. The standard error is estimated from the Poisson variance of $f(N_i)$ evaluated at the observed counts. The residual-bias bound is the sup-norm approximation error times an estimated number of tail symbols. That tail-size estimate comes from observed rare symbols plus a support-size estimate. This follows the "bias-aware interval" logic: we do not pretend the leftover bias is zero.

We expect the tail-size bound to be loose. Measuring how loose is part of the study.

Baselines

The naive reference point is the empirical plug-in entropy with a delta-method normal interval. Jiao et al. establish that its risk is $\asymp S^2/n^2 + \ln^2 S/n$, so its intervals should collapse once $n$ is not much larger than $k$. Miller–Madow and the jackknife, each paired with a normal interval, form the classical second tier. Valiant and Valiant and Wu and Yang report that both remain badly biased when $n \ll k$.

The strongest existing competitor is the sample-split polynomial estimator of Wu and Yang. It is the method our selection-bias correction is meant to replace, and it has the sharpest guarantee. We will give it an interval of the same bias-aware form as ours, so that the comparison isolates the effect of splitting rather than the interval recipe. The file reports its minimax rate but no numeric error or coverage value. We found no reported result on Lacuna for the coverage of any large-alphabet entropy interval.

The Unseen linear program of Valiant and Valiant will be included as a point estimator, with a parametric bootstrap interval drawn from its reconstructed distribution. That interval is a natural competitor because the reconstruction contains unseen mass. Dirichlet smoothing is included only as a sanity check, given the negative results above.

All methods receive the same samples, the same Poissonized sampling, and the same grid over threshold constants and polynomial degrees. Each method's tuning is chosen on held-out synthetic instances, not on the evaluation instances.

Two ablations isolate our key ingredient. One is the split-free estimator with no boundary correction. The other is the corrected estimator with the residual-bias term removed from the interval width.

Beating the strongest baseline has a specific meaning. It requires coverage within two points of nominal across all distribution families, together with a median interval length at least 20% shorter than split Wu–Yang at equal coverage. A shorter interval that under-covers does not count.

Why not just…?

Why not just bootstrap the plug-in or polynomial estimator? Resampling counts from the empirical distribution assigns zero probability to every unseen symbol. The bootstrap world therefore lacks the very tail that causes the bias, and the interval centers on a biased value. This is the discrete version of what Zhou and Li find for plug-ins with $d \sim n$. Our coverage experiments will include a full-alphabet nonparametric bootstrap so that this failure is measured rather than asserted.

Why not just keep sample splitting, as the theory does? This is a real threat at large $n$. Splitting makes the polynomial part nearly unbiased, and losing half the data may cost little when $n$ is much larger than $k/\log k$. The experiments settle the question by comparing interval length at matched coverage along the full sample-size grid. If splitting matches us everywhere, the contribution reduces to the bias analysis. We will report that outcome as such.

Why not just optimize the count function $f$ directly to minimize worst-case bias plus variance? This is a strong point estimator, and it is close in spirit to the Unseen approach. We include it as a baseline. It does not by itself produce a bias estimate or an honest interval, and our boundary correction and residual-bias width apply to any $f$, including an optimized one. We will test whether the correction still improves coverage for the optimized $f$. If it does not, the optimized $f$ plus a plain standard error is the better method, and we will say so.

Why not just use Dirichlet pseudo-counts on the tail? Jiao et al. prove that no choice of pseudo-count fixes the rate, and de Campos and Benavoli show that fixed priors are inadmissible at large $k$. We include Laplace and Jeffreys smoothing only to confirm that their intervals under-cover.

Proposed Experiments

The synthetic suite follows the benchmarks used in the cited work. It covers uniform, Zipf with exponents 0.5, 1, 2 and 5, geometric, and the even geometric–Zipf mixture, at $k = 10^5$, with $n$ swept from $10^3$ to $3\times 10^7$ as in Wu and Yang. Each configuration gets 1,000 replicates. We report bias, root-mean-squared error, empirical coverage of nominal 95% intervals, and median interval length.

For a real-data check we subsample 10% fragments of Hamlet, following Valiant and Valiant. We measure coverage of the full-play vocabulary of 4,268 words, using the support-size version of the method. We also measure coverage of the full-play word entropy, computed from the complete text. Both are reported across many random fragments.

The decisive check has three parts. First, the uncorrected split-free estimator must under-cover, worst when $k/n$ is large, with the shortfall tracking our predicted boundary bias. If coverage is already fine, the motivating claim is wrong. Second, adding the boundary correction must recover most of the lost coverage. Third, the corrected estimator must produce shorter intervals than split Wu–Yang at equal coverage across the mid-range of $n$.

A secondary diagnostic plots estimated against true boundary bias across instances. This tests whether band-restricted plug-in estimation of $\sum_i b(p_i)$ is accurate when counts are only of order $\log k$.