Welcome to MathOverflow

Question

3

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.

flag	asked Oct 23 2011 at 16:54 Tom Gur 105●1●4

is truncating the power series for log a bad idea? – S. Sra Oct 23 2011 at 17:31

1

It would also be good to know what "good" means in your context. Uniform approximation? Mean squared? Or even Kullback-Leibler? – Dirk Oct 23 2011 at 17:34

1

@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 2011 at 18:57

How about then using one of the polynomial techniques listed here: en.wikipedia.org/wiki/Approximation_theory – S. Sra Oct 23 2011 at 19:29

@dirk I'm actually curious about both uniform approximation and mean squared approximation – Tom Gur Oct 23 2011 at 19:38

Carlo Beenakker · Accepted Answer · 2011-10-24 11:52:01Z UTC

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

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.