Take the 2-minute tour ×
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.

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|improve this question
2  
0% accept rate discourage some from answering your posts. When a question has been answered to your satisfaction, it's considered good form to click the check mark below the voting arrows for that answer. The person whose answer you accept (you can only accept one) gets a small reputation boost, and you send a signal to others that you're no longer in need of an answer. BTW, it's not too late to go back to your old posts and accept your favorite answers. –  draks ... Sep 9 '12 at 17:35
add comment

1 Answer 1

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|improve this answer
add comment

Your Answer

 
discard

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.