Let $X$ be a discrete random variable with possible values
$\{x_1,\ldots,x_n\}$, and let $p$ denote the probability mass function of
$X$. In addition, denote $p_i=p(x_i)$.
The entropy of $X$ is defined as follows
$$H(X)=H(p_1,\ldots,p_n)=-\sum_{i=1}^n p_i\log p_i$$
I'm looking for a low degree (up to $\log n$) polynomial $P(p_1,\ldots,p_n)$ which provides as good as possible approximation for the entropy of the distribution.
Best Answer
The canonical choice is the Renyi entropy:
$H_\alpha=\frac{1}{1-\alpha}\log P_\alpha$, with $P_{\alpha}(p_1,...,p_n)=\sum_{i=1}^{n}p_i^{\alpha}$
your entropy (the Shannon entropy) is the limit $\alpha\rightarrow 1$ of $H_\alpha$
this choice of approximation is useful because it has many meaningful applications, in a variety of contexts.
http://en.wikipedia.org/wiki/Renyi_entropy
For quantitative bounds on the rate of convergence of Renyi entropy towards Shannon entropy see
N. Harvey, J. Nelson, K. Onak, Streaming algorithms for estimating entropy, IEEE ITW '08 proceedings, online at
http://www.math.uwaterloo.ca/~harvey/Publications/StreamingEntropy/ITW.pdf