Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
is truncating the power series for log a bad idea? –  Suvrit Oct 23 '11 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 '11 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 '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

up vote 8 down vote accepted

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

share|improve this answer
    
@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
    
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 2 days ago
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.