Opening Entropy
Entropy
- Length
- 25 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 5: Before the lecture
Shannon entropy, defined in 1948, measures the randomness of a discrete random variable as the minimum average number of bits needed to store or generate its outcomes. O'Donnell starts from binary examples and prefix-free codes, which let variable-length encodings decode without punctuation. He proves that a variable with outcomes has entropy between and , using Jensen's inequality and the concavity of the logarithm. Entropy is then shown to be additive for independent random variables, and encoding many independent draws together drives the per-draw cost toward the entropy. Part of Lecture 24a of CMU's graduate CS Theory Toolkit, it assumes discrete probability and expected values.
Your comment is kept while you sign up.Sign in
O'Donnell builds Shannon entropy from prefix-free codes, then batches independent draws to approach the entropy bound.
Shannon entropy, defined in 1948, measures the randomness of a discrete random variable as the minimum average number of bits needed to store or generate its outcomes. O'Donnell starts from binary examples and prefix-free codes, which let variable-length encodings decode without punctuation. He proves that a variable with outcomes has entropy between and , using Jensen's inequality and the concavity of the logarithm. Entropy is then shown to be additive for independent random variables, and encoding many independent draws together drives the per-draw cost toward the entropy. Part of Lecture 24a of CMU's graduate CS Theory Toolkit, it assumes discrete probability and expected values.
Elements of Information Theory
Interactive Information Complexity
Shannon '48
This lecture
Lecture 76 of 89 of A Theorist's Toolkit.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.