The query complexity of estimating entropy

We investigate the query complexity of additively estimating entropy of a discrete probability distribution in two settings. Let p be an unknown probability distribution on [n]:= {1, 2, ..., n}, and define two kinds of queries: A SAMP query takes no input and returns x with probability p[x]; a PMF query takes as input x and returns the value p[x]. In the SAMP model of query complexity, the only allowed interaction with p is via SAMP queries. In the SAMP+PMF model, both SAMP and PMF queries are utilized to interact with p. In particular, we consider the task of estimating the entropy of a probability distribution. For the usual Shannon entropy, we review the matching upper and lower bounds established by Valiant and Valiant in the SAMP model, and describe the algorithm constructed by Canonne and Rubinfeld in the SAMP+PMF model. For the Renyi entropy, we analyze three different matching upper and lower bound pairs introduced by Acharya et al. in the SAMP model. We show that at least poly-logarithmic number of queries are necessary to estimate the Shannon entropy in the SAMP+PMF model, matching a recent upper bound of Canonne and Rubinfeld. In addition, we prove matching upper and lower bounds to estimate the Renyi entropy in the SAMP+PMF model.