Low degree polynomial approximation for the entropy function

2011-10-23T16:54:37Z

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.

Answer by Carlo Beenakker for Low degree polynomial approximation for the entropy function

2011-10-23T20:44:09Z

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

Low degree polynomial approximation for the entropy function - MathOverflow

Low degree polynomial approximation for the entropy function

Answer by Carlo Beenakker for Low degree polynomial approximation for the entropy function