The Complexity of Estimating Rényi Entropy

It was recently shown that estimating the Shannon entropy H(p) of a discrete k-symbol distribution p re-quires Θ(k / log k) samples, a number that grows near-linearly in the support size. In many applications H(p) can be replaced by the more general Rényi en-tropy of order α, Hα(p). We determine the number of samples needed to estimate Hα(p) for all α, showing that α < 1 requires super-linear, roughly k1/α sam-ples, noninteger α> 1 requires near-linear, roughly k samples, but integer α> 1 requires only Θ(k1−1/α) samples. In particular, estimating H2(p), which arises in security, DNA reconstruction, closeness test-ing, and other applications, requires only Θ( k) sam-ples. The estimators achieving these bounds are sim-ple and run in time linear in the number of samples.