This certain Khan Academy videos introduces the intuition about information entropy: https://www.youtube.com/watch?v=2s3aJfRr9gE&t=102s . It relates information entropy to the expected number of questions needed to be asked to determine the given letter produced by a certain machine according to certain way of asking some binary-outcome questions in sequence. However, the video did not mention how it came up with the scheme to ask question. For four-letter case with even probability, it simply assumes asking if the letter belongs to two of the possible two-letter subsets, and for the non-even probability case, it gave another 'cleverer' way of asking questions without explaining why it is the optimal way of asking question for that specific scenario and hence the expected number of question asked is numerically equal to the information entropy that machine has. I previously thought the principle according to which it comes up with the scheme of asking question is the same as how decision tree does splitting, i.e. maximum information gain, however after some calculation I realized that is probably not the case. Hope someone can help explain what is the principle behind by going through the non-even probability case. Many thanks.

  • $\begingroup$ I suggest looking at a proof rather than a video. $\endgroup$ Jul 12, 2022 at 21:20
  • $\begingroup$ @yuvalFilmus may I ask where can you find the proof? I am talking about the proof of the principle of devising the scheme rather than information entropy $\endgroup$
    – Sam
    Jul 13, 2022 at 1:18
  • $\begingroup$ You can find it in any textbook, for example Cover and Thomas' Elements of information theory. $\endgroup$ Jul 13, 2022 at 10:46
  • 1
    $\begingroup$ See the proof of Theorem 8.3 (the source coding theorem) here for a construction of the code. $\endgroup$ Jul 13, 2022 at 10:52
  • $\begingroup$ @YuvalFilmus Theorem 8.3 does not specify the protocol for constructing the code. Do you actually mean Huffman Coding? Also I realize given the alphabet size fixed to 2, the optimal way of constructing the code is actually equivalent to a optimal decision tree constructed based on maximum information gain? $\endgroup$
    – Sam
    Jul 18, 2022 at 9:37


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.