Approximating the Entropy of Large Alphabets
Mickey Brautbar, Alex Samorodnitsky · Electronic colloquium on computational complexity · 2005
We consider the problem of approximating the entropy of a discrete distribution P on a domain of size q, given access to n independent samples from the distribution. It is known that n q is necessary, in general for a good additive estimate of the entropy. A problem of multiplicative entropy estimate was recently addressed by Batu, Dasgupta, Kumar, and Rubinfeld. They show that n = q suces for a factor- approximation, < 1. We introduce a new parameter of a distribution - its ee ctive alphabet size qef (P ). This is a more intrinsic property of the distribution depending only on its entropy moments. We show qef ~ O(q). When the distribution P is essentially concentrated on a small part of the domain qef q. We strengthen the result of Batu et al. by showing it holds with qef replacing q. This has several implications. In particular the rate of convergence of the maximum-likelihood entropy estimator (the empirical entropy) for both nite and innite alphabets is shown to be dictated by the eectiv e alphabet size of the distribution. Several new, and some known, facts about this estimator follow easily. Our main result is algorithmic. Though the eectiv e alphabet size is, in general, an unknown parameter of the distribution, we give an ecien t procedure (with access to the alphabet size only) that achieves a factor- approximation of the entropy with n = e O exp n 1=4 log 3=4 q log 1=4 qef o