Low degree polynomial approximation for the entropy function

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.

• is truncating the power series for log a bad idea? – Suvrit Oct 23 '11 at 17:31
• It would also be good to know what "good" means in your context. Uniform approximation? Mean squared? Or even Kullback-Leibler? – Dirk Oct 23 '11 at 17:34
• @Suvrit: truncating the power series for log is probably a bad idea, since for very small $p_i$ this will converge very poorly. – Igor Rivin Oct 23 '11 at 18:57
• How about then using one of the polynomial techniques listed here: en.wikipedia.org/wiki/Approximation_theory – Suvrit Oct 23 '11 at 19:29
• @dirk I'm actually curious about both uniform approximation and mean squared approximation – user17253 Oct 23 '11 at 19:38

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

• added a reference on the quality of the approximation – Carlo Beenakker Oct 24 '11 at 11:41
• Nice, but how is that "a low degree polynomial"? – fedja Oct 25 '11 at 2:38
• Is the Renyi entropy a polynomial on $(p_1,\ldots,p_n)$? On top of having a $\log$ before the $P_{\alpha}$ the power on $\alpha$ is non-integral as $\alpha\to 1$. – Cristóbal Guzmán Apr 21 '14 at 0:47