MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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}$

share|cite|improve this question
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 – blazs Jun 29 '13 at 9:30

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.