Low degree polynomial approximation for the entropy function - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T09:19:17Z http://mathoverflow.net/feeds/question/78909 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/78909/low-degree-polynomial-approximation-for-the-entropy-function Low degree polynomial approximation for the entropy function Tom Gur 2011-10-23T16:54:37Z 2011-10-24T11:52:01Z <p>Let $X$ be a discrete random variable with possible values <code>$\{x_1,\ldots,x_n\}$</code>, and let $p$ denote the probability mass function of $X$. In addition, denote $p_i=p(x_i)$.</p> <p>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$$</p> <p>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.</p> http://mathoverflow.net/questions/78909/low-degree-polynomial-approximation-for-the-entropy-function/78924#78924 Answer by Carlo Beenakker for Low degree polynomial approximation for the entropy function Carlo Beenakker 2011-10-23T20:44:09Z 2011-10-24T11:52:01Z <p>The canonical choice is the Renyi entropy:</p> <p>$H_\alpha=\frac{1}{1-\alpha}\log P_\alpha$, with $P_{\alpha}(p_1,...,p_n)=\sum_{i=1}^{n}p_i^{\alpha}$</p> <p>your entropy (the Shannon entropy) is the limit $\alpha\rightarrow 1$ of $H_\alpha$</p> <p>this choice of approximation is useful because it has many meaningful applications, in a variety of contexts.</p> <p><a href="http://en.wikipedia.org/wiki/Renyi_entropy" rel="nofollow">http://en.wikipedia.org/wiki/Renyi_entropy</a></p> <p>For quantitative bounds on the rate of convergence of Renyi entropy towards Shannon entropy see</p> <p>N. Harvey, J. Nelson, K. Onak, Streaming algorithms for estimating entropy, IEEE ITW '08 proceedings, online at</p> <p><a href="http://www.math.uwaterloo.ca/~harvey/Publications/StreamingEntropy/ITW.pdf" rel="nofollow">http://www.math.uwaterloo.ca/~harvey/Publications/StreamingEntropy/ITW.pdf</a></p>