Incremental entropy computation 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?
 A: Regarding Question 2: By omitting the index $i$ in your notation, it holds the identity
$$
H^{N+1} = \frac{S^N}{S^{N+1}} H^{N} - \frac{S^N}{S^{N+1}} \log \frac{S^N}{S^{N+1}} - \frac{x_{N+1}}{S^{N+1}}\log \frac{x_{N+1}}{S^{N+1}} .
$$
In this form, the formula is probably not well suited for numerical applications due to cancellations.
A: Using Andre's identitiy, I derived more general formulas (and algorithms). I made the note with derivations available on arXiv. 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.
A: I think that the following paper is closely related to your questions: http://hal.inria.fr/docs/00/60/90/65/PDF/RR-7663.pdf
