<p>I derived update formulas and algorithms for entropy and Gini index and made the note <a href="http://arxiv.org/abs/1403.6348" rel="nofollow noreferrer">available on arXiv</a>. (The working version of the note is available <a href="http://blazsovdat.com/publications/incremental.pdf" rel="nofollow noreferrer">here</a>.) Also see <a href="https://mathoverflow.net/questions/133977/incremental-entropy-computation/134376#134376">this mathoverflow</a> answer.</p>

<p>For the sake of convenience I am including simple Python code, demonstrating the derived formulas:
</p>

<pre><code>from math import log
from random import randint

# maps x to -x*log2(x) for x&gt;0, and to 0 otherwise 
h = lambda p: -p*log(p, 2) if p &gt; 0 else 0

# update entropy if new example x comes in 
def update(H, S, x):
    new_S = S+x
    return 1.0*H*S/new_S+h(1.0*x/new_S)+h(1.0*S/new_S)

# entropy of union of two samples with entropies H1 and H2
def update(H1, S1, H2, S2):
    S = S1+S2
    return 1.0*H1*S1/S+h(1.0*S1/S)+1.0*H2*S2/S+h(1.0*S2/S)

# compute entropy(L) using only `update' function 
def test(L):
    S = 0.0 # sum of the sample elements
    H = 0.0 # sample entropy 
    for x in L:
        H = update(H, S, x)
        S = S+x
    return H

# compute entropy using the classic equation 
def entropy(L):
    n = 1.0*sum(L)
    return sum([h(x/n) for x in L])

# entry point 
if __name__ == "__main__":
    L = [randint(1,100) for k in range(100)]
    M = [randint(100,1000) for k in range(100)]

    L_ent = entropy(L)
    L_sum = sum(L)

    M_ent = entropy(M)
    M_sum = sum(M)

    T = L+M

    print "Full = ", entropy(T)
    print "Update = ", update(L_ent, L_sum, M_ent, M_sum)
</code></pre>

<hr>
Incremental entropy computation
<p>Let <code>std::vector&lt;int&gt; counts</code> be a vector of positive integers and let <code>N:=counts[0]+...+counts[counts.length()-1]</code> be the the sum of vector components. Setting <code>pi:=counts[i]/N</code>, I compute the entropy using the classic formula <code>H=p0*log2(p0)+...+pn*log2(pn)</code>.</p>

<p>The <code>counts</code> vector is changing --- counts are incremented --- and every 200 changes I recompute the entropy. After a quick google and stackoverflow search I couldn't find any method for incremental entropy computation. So the question: Is there an incremental method, <a href="http://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#Online_algorithm" rel="nofollow noreferrer">like the ones for variance</a>, for entropy computation?</p>

<p>EDIT: Motivation for this question was usage of such formulas for incremental information gain estimation in <a href="http://homes.cs.washington.edu/~pedrod/papers/kdd00.pdf" rel="nofollow noreferrer">VFDT</a>-like learners. </p>

<p><strong>Resolved:</strong> See <a href="https://mathoverflow.net/questions/133977/incremental-entropy-computation/134376#134376">this mathoverflow post</a>.</p>