Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given a string of random symbols with yet a priori unknown distribution, what are the known algorithms to compute its Shannon entropy?

$$H = - \sum_i \; p_i \log p_i$$

Is there an algorithm to compute it without calculating the probabilities $p_i$ first? Having calculated the entropy $H_n$ of the first $n$ symbols can I find the entropy $H_{n+m}$ of the $n+m$ symbols (knowing about the first $n$ symbols only $H_n$)?

share|improve this question
1  
If you assume the probabilities you found for the first $n$ symbols are correct for the next $m$, the entropy scales by the number of symbols, so you will have $H_{m+n}=\frac{m+n}nH_n$ –  Ross Millikan Feb 1 '12 at 18:34
    
@RossMillikan and what if they are almost correct, but I want to improve them with the next $m$ symbols? –  Yrogirg Feb 2 '12 at 4:36
    
If you calculate the $p_i$ over all $m+n$ symbols, then you have $H_n=\frac n{m+n}H_{m+n}$ but I suspect that is not the type of result you want. If they are almost correct, it will almost scale. But I don't think there is an easy middle ground. –  Ross Millikan Feb 2 '12 at 5:39
add comment

1 Answer

up vote 2 down vote accepted

Is there an algorithm to compute it without calculating the probabilities $p_i$ first?

I doubt it, but I don't have a proof.

Having calculated the entropy $H_n$ of the first $n$ symbols can I find the entropy $H_{n+m}$ of the $n+m$ symbols (knowing about the first $n$ symbols only $H_n$)?

No. Suppose $H_n = 0$ and the final $m$ symbols are $b\ldots b$. You don't know whether $H_{n+m} = 0$ or $$H_{n+m} = -\sum_{i\in\{n,m\}} \frac{i}{n+m} \log \frac{i}{n+m}$$

share|improve this answer
    
Assume that the input string in some sense is "good", that is [a,a,b,b,b,a,b,a,a,b..] and not [a..a,b..b]. What then? –  Yrogirg Feb 2 '12 at 4:38
    
@Yrogirg, if you define "good" tightly enough and have a sufficiently precise value of $H_n$ then you might be able to recover the frequencies and calculate the true probabilities; otherwise, don't expect much joy. –  Peter Taylor Feb 2 '12 at 14:36
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.