the complexity of approximating entropy
(MATH) We consider the problem of approximating the entropy of a discrete distribution under several models. If the distribution is given explicitly as an array where the i -th location is the probability of the i -th element, then linear time is both necessary and sufficient for approximating the entropy.We consider a model in which the algorithm is given access only to independent samples from the distribution. Here, we show that a &lgr;-multiplicative approximation to the entropy can be obtained in O ( n (1+?) /&lgr; 2 < poly(log n ) ) time for distributions with entropy ?(&lgr; ?), where n is the size of the domain of the distribution and ? is an arbitrarily small positive constant. We show that one cannot get a multiplicative approximation to the entropy in general in this model. Even for the class of distributions to which our upper bound applies, we obtain a lower bound of ?( n max(1/(2&lgr; 2 ), 2/(5&lgr; 2 2)) .We next consider a hybrid model in which both the explicit distribution as well as independent samples are available. Here, significantly more efficient algorithms can be achieved: a &lgr;-multiplicative approximation to the entropy can be obtained in O ( &lgr;2 .Finally, we consider two special families of distributions: those for which the probability of an element decreases monotonically in the label of the element, and those that are uniform over a subset of the domain. In each case, we give more efficient algorithms for approximating the entropy.
complexity approximation entropy distributed model arrays locatability probability timing algorithm access size posit general class lower bound hybrid efficiency families label case log