Surprise, bits and entropy
Claude Shannon measured information as surprise. An outcome of probability p carries log₂(1/p) bits, and the average surprise, entropy, is a hard limit on how far any message can be compressed.
40 min
After this lesson you can
- Compute the surprise of an outcome and explain why it has to be a logarithm
- Compute the entropy of a distribution and say when it is largest and smallest
- Explain entropy as the number of yes/no questions an optimal strategy needs, on average (the source coding theorem, informally)
- Build a Huffman code and compare its average length with the entropy
In this lesson
- The engineer’s question
- Why a logarithm?
- From possibilities to probabilities: surprise
- Entropy: the average surprise
- Twenty questions
- The limit: Shannon’s source coding theorem
- The code
- In the papers
This lesson is part of Descent Pro
Descent Pro unlocks every lesson on the route, from base camp to the summit. Every plan starts with a free trial.