Skip to main content
5 of 7
Updated links.

Using Andre's identitiy, I derived a more general formula. I uploaded the PDF with the derivations here. Comments are more than welcome.

For convenience I also give proofs 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.