SCIENCE@home

The Complexity of Estimating Rényi Entropy

Jayadev Acharya,A. Orlitsky,A. Suresh,Himanshu Tyagi

Published 2014 in ACM-SIAM Symposium on Discrete Algorithms

ABSTRACT

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 Renyi entropy of order α, Hα(p). We determine the number of samples needed to estimate Hα(p) for all α, showing that α 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 testing, and other applications, requires only Θ([EQUATION]k) samples. The estimators achieving these bounds are simple and run in time linear in the number of samples.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-47 of 47 references · Page 1 of 1

CITED BY

Showing 1-72 of 72 citing papers · Page 1 of 1