Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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

Conditional entropy can be expressed in terms of entropy as H(Y|X) = H(X,Y) - H(X).

Given a sequence $\{x _{1}, x _{2},... x _{n}\}$, the bigrams are $\{(x _{i}, x _{i+1})\}$, and the trigrams are $\{(x _{i}, x _{i+1}, x _{i+2})\}$.

In general, $H(X|Y) \ne H(Y|X)$. However, in the case of bigrams, since $H(X_{i}) = H(X_{i+1})$, we have $H(X_{i+1}|X_{i}) = H(X_{i}|X_{i+1})$. (Or very nearly: in fact $H(X_{i})$ omits the last term in the sequence, and $H(X_{i+1})$ omits the first term.)

Question 1: The above argument shows that the conditional entropy of the bigrams is equal to the conditional entropy of their reverses, but is there an intuitive way to see this? Why should the conditional entropy going forwards be the same as the conditional entropy going backwards?

Question 2: When I calculate $H(X_{i+2}|X_{i},X_{i+1})$ and $H(X_{i}|X_{i+1},X_{i+2})$ in code, they come out the same. I find this surprising. Is there a bug in my code? If not, what is the explanation. (Again, if possible I would like an intuitive explanation as well as a mathematical one.)

Question 3: If my sequence is produced by some Markov process, would it be valid to eliminate values $x_{i}$ for which we have "insufficient evidence" (ie too few samples)? Would this change the answers to questions 1 and 2?

share|cite|improve this question

Question 1: As long as $H(X_i)=H(X_{i+1})$ both conditional entropies will match, you can use a Venn-like diagram to convince yourself. However I don't follow what you mean by $H(X_i)$ omits the last term in the sequence, and $H(X_{i+1})$ omits the first term. Could you clarify that?

Question 2: I can think of a counterexample: let $H(X_i)=H(X_{i+1})=H(X_{i+2})=1$, $X_i=X_{i+1}$ and $X_{i+2}$ be independent of $X_i$,$X_{i+1}$. Then it is clear that: \begin{equation} H(X_{i+2}|X_iX_{i+1})=H(X_{i+2})=1 \end{equation} but \begin{equation} H(X_{i}|X_{i+1}X_{i+2})=0 \end{equation}

share|cite|improve this answer

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.