# How to compute Shannon information?

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$)?

-
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

## 1 Answer

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}$$

-
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