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 –  Tom Gur Oct 23 '11 at 19:38
add comment

1 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

-
@Carlo How can I quantify the quality of the approximation ? –  Tom Gur Oct 24 '11 at 11:05
added a reference on the quality of the approximation –  Carlo Beenakker Oct 24 '11 at 11:41
@Carlo Thanks ! –  Tom Gur Oct 24 '11 at 12:39
Nice, but how is that "a low degree polynomial"? –  fedja Oct 25 '11 at 2:38
add comment