# Incremental computation of a conditional entropy

Is it possible to compute a conditional entropy (see the two following formulas) in an incremental manner ? That is, the sets C and K are not fix: each time we have a new element c, set K may increase or not; and I want to update the current conditional entropy value each time we have a new element c.

Basically, I want to know if it is possible to have an incremental expression for this conditional entropy, like it is the case for example for the mean which can be computed by: $\bar X_n = n^{-1}[X_n + (n-1)\bar X_{n-1}]$

• Conditional entropy formula 1: $$H(C|K) = - \sum_{k=1}^{|K|} \sum_{c=1}^{|C|} \frac{a_{ck}}{N} log \frac{a_{ck}}{\sum_{c=1}^{|C|} a_{ck}}$$ $$H(C) = - \sum_{c=1}^{|C|} \frac{\sum_{k=1}^{|K|} a_{ck}}{N} log \frac{\sum_{k=1}^{|K|} a_{ck}}{N}$$

• Conditional entropy formula 2: $$H(K|C) = - \sum_{c=1}^{|C|} \sum_{k=1}^{|K|} \frac{a_{ck}}{N} log \frac{a_{ck}}{\sum_{k=1}^{|K|} a_{ck}}$$ $$H(K) = - \sum_{k=1}^{|K|} \frac{\sum_{c=1}^{|C|} a_{ck}}{N} log \frac{\sum_{c=1}^{|C|} a_{ck}}{N}$$

Note: $a_{ck}$ may refer to something like a distance between elements c and k, or the number of elements of type c that are in k, or something like that ... and $N$ is $\sum_{k=1}^{|K|} \sum_{c=1}^{|C|} a_{ck}$

• Your question will be easier to read if you include the equations via LaTeX code in the question itself, instead of via external links. (The site can process and display such code directly.) – Vaughn Climenhaga Feb 24 '12 at 20:25
• @VaughnClimenhaga I've just edited my post to add the Latex code. – shna Feb 24 '12 at 22:03
• what is $N$? Is it $|K| |C|$? – Suvrit Feb 24 '12 at 23:14
• I have edited my post to be more clear. – shna Feb 28 '12 at 19:21
• Dear shna, your question seems to be closely related to this one:mathoverflow.net/a/134376/34944. – user12344567 Jun 29 '13 at 9:30