Approximating entropy from sublinear samples
Mickey Brautbar, Alex Samorodnitsky · 2007
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α suffices for a factor-α approximation, α < 1. We introduce a new parameter of a distribution- its effective alphabet size qef (P). This is a more intrinsic property of the distribution depending only on its entropy moments. We show qef ≤