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 requires Θ(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 entropy of order α, H α (p). We determine the number of samples needed to estimate H α (p) for all α, showing that α < 1 requires a super-linear, roughly k 1/α samples, noninteger α > 1 requires a nearlinear k samples, but, perhaps surprisingly, integer α > 1 requires only Θ(k 1−1/α ) samples. In particular, estimating H 2 (p), which arises in security, DNA reconstruction, closeness testing, and other applications, requires only Θ( √ k) samples. The estimators achieving these bounds are simple and run in time linear in the number of samples