After a quick internet search I found no method for incremental entropy computation. 


### Question 1


Let $\{x\_i\}\_{i=1}^n$ and $\{x\_i\}\_{i=1+n}^{n+m}$ be two samples and let $S\_i^j:=\sum\_{k=i}^j x\_k$. Define entropy $$H\_i^j:=-\sum\_{k=i}^j\frac{x\_k}{S\_i^j}\log\_2\frac{x\_k}{S\_i^j}.$$ Is there an algorithm --- computationally cheaper than complete recomputation --- to compute $H\_1^{n+m}$ using only $H\_1^n$ and $H\_{n+1}^{m+n}$ or similar statistics? 


### Question 2


Is there an algorithm to incrementally compute entropy as new numbers $x\_i$ come in, much like there's such an [algorithm for variance](http://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#Online_algorithm)?



Incremental entropy computation
Using Andre's identitiy, I derived more general formulas (and algorithms). I made the note with derivations [available on arXiv](http://arxiv.org/abs/1403.6348). Comments are more than welcome. 


For convenience I also give proofs of (some of) the results here.


**Lemma.** Let $\{x\_i\}\_{i=1}^n$ be a sample of positive real numbers $x\_i>0$, let $S\_n:=x\_1+x\_2+\ldots+x\_n$ be the sum of sample elements, and let $H\_n:=-\sum\_{i=1}^n\frac{x\_i}{S\_n}\log\_2\frac{x\_i}{S\_n}$ be the sample entropy. For any positive real number $R>0$ we have $$-\sum\_{i=1}^n\frac{x\_i}{R+S\_n}\log\_2\frac{x\_i}{R+S\_n}=\frac{S\_n}{R+S\_n}H\_n-\frac{S\_n}{R+S\_n}\log\_2\frac{S\_n}{R+S\_n}.$$
**Proof.** To see this notice that $\frac{x\_i}{R+S\_n}=1\cdot\frac{x\_i}{R+S\_n}=\frac{S\_n}{S\_n}\frac{x\_i}{R+S\_n}=\frac{x\_i}{S\_n}\frac{S\_n}{R+S\_n}.$ The lemma follows by plugging this into $-\sum\_{i=1}^n\frac{x\_i}{R+S\_n}\log\_2\frac{x\_i}{R+S\_n}$ and doing some algebra.


Now we can prove Andre's claim.


**Claim.** Let $\{x\_i\}\_{i=1}^n$ be a sample and $H\_n$ and $S\_n$ be the sample entropy and the sum of the sample elements, respectively. Suppose new element $x\_{n+1}$ ``comes in''. Then we have $$H\_{n+1}=\frac{S\_n}{S\_{n+1}}H\_n-\frac{S\_n}{S\_{n+1}}\log\_2\frac{S\_n}{S\_{n+1}}-\frac{x\_{n+1}}{S\_{n+1}}\log\_2\frac{x\_{n+1}}{S\_{n+1}}.$$
**Proof.** Clearly, we have $$H\_{n+1}=-\sum\_{i=1}^{n+1}\frac{x\_i}{S\_{n+1}}\log\_2\frac{x\_i}{S\_{n+1}}=-\sum\_{i=1}^{n}\frac{x\_i}{S\_{n+1}}\log\_2\frac{x\_i}{S\_{n+1}}-\frac{x\_{n+1}}{S\_{n+1}}\log\_2\frac{x\_{n+1}}{S\_{n+1}}.$$
Claim follows by applying the lemma.


**Theorem 1.** Let $\{x\_i\}\_{i=1}^n$ and $\{y\_i\}\_{i=1}^m$ be two samples of positive real numbers and let $H\_n$ and $S\_n$ and $H\_m$ and $S\_m$ be the corresponding sample entropies and sums of sample elements, respectively. Let $z\_i:=x\_i$ for $1\le i\le n$ and $z\_i:=y\_{i-n}$ for $n+1\le i\le n+m$, i.e., define $z\_i$ as the ''sample union''. Let $Z\_{n+m}:=S\_n+S\_m$ and let $H\_{n+m}$ be the entropy of the ``sample union''. Then we have $$H\_{n+m}=\frac{S\_n}{Z\_{n+m}}H\_n-\frac{S\_n}{Z\_{n+m}}\log\_2\frac{S\_n}{Z\_{n+m}}+\frac{S\_m}{Z\_{n+m}}H\_m-\frac{S\_m}{Z\_{n+m}}\log\_2\frac{S\_m}{Z\_{n+m}}.$$ 
**Proof.** As in the previous proof, write $$H\_{n+m}=-\sum\_{i=1}^{n+m}\frac{z\_i}{Z\_{n+m}}\log\_2\frac{z\_i}{Z\_{n+m}}=-\sum\_{i=1}^n\frac{x\_i}{Z\_{n+m}}\log\_2\frac{x\_i}{Z\_{n+m}}-\sum\_{i=1}^m\frac{y\_i}{Z\_{n+m}}\log\_2\frac{y\_i}{Z\_{n+m}}.$$ The theorem follows by applying the lemma twice.


**Theorem 2.** Let $\{x\_i\}\_{i=1}^n$ be a sample of positive real numbers, and let $S\_n$ and $H\_n$ the sum of sample elements and sample entropy, respectively. Suppose elements $x\_{i\_j}$ increase by $r\_j>0$ for $1\le j\le k<n$. Let $r:=r\_1+r\_2+\ldots+r\_k$. Then the entropy becomes $$\frac{S\_n}{S\_n+r}H\_n-\frac{S\_n}{S\_n+r}\log\_2\frac{S\_n}{S\_n+r}-\sum\_{j=1}^k\left(\frac{x\_{i\_j}+r\_j}{S\_n+r}\log\_2\frac{x\_{i\_j}+r\_j}{S\_n+r}-\frac{x\_{i\_j}}{S\_n}\log\_2\frac{x\_{i\_j}}{S\_n}\right).$$
**Proof.** The idea is to substract the old therms and apply the lemma for the new terms.


