7 ms·

Shannon Entropy Imposes Fundamental Limits on Communication

77 points by harscoat 4y ago

rkp8000 4y ago
For anyone interested in these ideas, I'd highly recommend reading Shannon's original 1948 paper (linked in the article). While technical and precise it is actually quite digestible for someone with a bit of a quantitative background.
- ivansavz 4y ago
  link to paper abstract: https://ieeexplore.ieee.org/abstract/document/6773024 https://ieeexplore.ieee.org/abstract/document/6773024 direct link to PDF: https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6773024 https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=677...
  - nighthawk454 4y ago
    direct direct link: https://sci-hub.hkvisa.net/10.1002/j.1538-7305.1948.tb01338.x https://sci-hub.hkvisa.net/10.1002/j.1538-7305.1948.tb01338....
- prophesi 4y ago
  I'd also highly recommend watching The Bit Player documentary. Not as info-dense as an article or paper, but it's a fun ride.
mpalmer 4y ago
Information theory is fascinating to anyone who likes the mathy underpinnings of seemingly non-mathy things, and it's everywhere. Cool stuff. Speaking of information and decompression, my brain initially interpreted the title as a breaking news headline about a female supervillain who's also a theory nerd. It was only the added context of the domain name that fixed the error.
acjohnson55 4y ago
The information theory class I took in grad school was one of the most mindbending classes I've ever taken. It made doing gnarly math problems fun. Claude Shannon was a titan. He's also known for publishing what some call the most important masters thesis of all time, https://en.wikipedia.org/wiki/A_Symbolic_Analysis_of_Relay_and_Switching_Circuits https://en.wikipedia.org/wiki/A_Symbolic_Analysis_of_Relay_a....
_wldu 4y ago
One example I like to use (when talking about entropy): A four digit numeric PIN (that we know) has 0 bits of entropy. There is no uncertainty about what the PIN actually is. A randomly selected one (that we do not know) has just over 13 bits. print(math.log(10)/math.log(2)*4) 13.28771237954945 The more entropy, the more uncertain we are. However, humans are not random. We use the year we were born, some keyboard sequence or some other predictable number as our PIN. We don't know exactly how much entropy these PINS have (there is some degree of uncertainty), but we do know they are significantly less than 13 bits.
- mnks 4y ago
  I wrote a blog post [1] with an interactive widget where you can provide an encoding for a random decimal digit and see how close you can get to the theoretical log₂(10) ≈ 3.32 bits. [1]: https://blog.kardas.org/post/entropy/ https://blog.kardas.org/post/entropy/ (Average Code Length section)
- vba616 4y ago
  Here's a riddle. If using my birthday reduces the entropy of my PIN, what does it do to its entropy if I happen to have the same birthday as one of the most famous people in the world? Does it matter if I am aware or not? Does it matter what they use for their PIN? For the sake of argument, I'm thinking month and day, not year.
  - diffeomorphism 4y ago
    That is not a riddle just a question how to handle information on the distribution of passwords in the population. So you get the same answer as if it were four alphabetic characters and your choice is "soup".
  - rcxdude 4y ago
    The important thing is that your PIN has zero entropy, regardless of its value. Entropy is a property of distributions, not individual values. You may be thinking of the probability (or information content) your PIN is assigned when looking at the overally distributions of PIN, in which case it probably does matter how popular your birthday is (and whether it also matches common patterns people use for PINs). This does feed into the calculation of entropy for the distribution but then it ceases to tell you anything about your PIN specifically. It also only makes sense when you are looking at it relative to the distribution, so it matters how you specify the PINs you are comparing it to. The 'information content' of a given outcome is the logarithm of the inverse of its probability (i.e. more unlikely events give you more information), and the entropy of a distribution is the expected value of this information content.
bob1029 4y ago
Information theory is so cool. I feel like having a solid grasp of the fundamentals is critical for achieving mastery in software development. Closely related would be digital signal processing and frequency domain techniques, both also extremely useful in many branches of software. The actual information content of a thing has always surprised me, especially when factoring in slightly imperfect (but passable) representations such as JPEG or MP3. To lose some information seems entirely acceptable in many cases.
ttctciyf 4y ago
> Engineers can build probabilistic models for patterns of pixel colors from one frame to the next. The models make it possible to calculate the Shannon entropy [...] That value tells you the limit of “lossless” compression — the absolute most the movie can be compressed before you start to lose information about its contents. While this is generally true in practice, strictly speaking the shortest possible encoding of a sequence of bits could be smaller than this would suggest, since it's possible a pattern exists that has escaped notice. For example: the first 10 billion digits of pi pass statistical tests for randomness, but can be generated by a short program which calculates them until the desired length is reached, in effect "compressing" them to the length of the generator program. Because of considerations like this, Algorithmic Information Theory[1] equates the information content of a bit sequence with the length of the shortest program which will generate it - though this has the drawback of being generally uncomputable - an intriguingly different paradigm. 1: see https://en.wikipedia.org/wiki/Algorithmic_information_theory https://en.wikipedia.org/wiki/Algorithmic_information_theory
- Eddy_Viscosity2 4y ago
  Could a smaller program be written that could generate the code that generates the digits of pi? So the code that writes the code is the smallest information content? I wonder how many times this could recurse before there is a limit..
  - zbobet2012 4y ago
    That's the https://en.wikipedia.org/wiki/Kolmogorov_complexity https://en.wikipedia.org/wiki/Kolmogorov_complexity. It's uncomputable in general.
    - Eddy_Viscosity2 4y ago
      Nice, this is exactly what I meant. Actually kind of proud of myself for having a similar thought as Kolmogovov.
- corey_moncure 4y ago
javajosh 4y ago
I'm more interested in the problem of sending strings out into the world where more strings may "stick" to them, possibly producing more strings. You know, like life. Or software. Given a particular string, can do you determine its age? Can you determine which discrete strings came into contact with it along its journey and when? And so on. I'm not sure if this is interesting to anyone else, but it sure is interesting to me! Consider how these are the boundary conditions that justify software design decisions so primordial we don't even consider them decisions anymore.
zbobet2012 4y ago
> That you can zip a large movie file, for example, owes to the fact that pixel colors have a statistical pattern, the way English words do. Engineers can build probabilistic models for patterns of pixel colors from one frame to the next. This is, in fact, incorrect generally. Movie files are generally compressed via _lossy_ compression, which escapes the Shannon entropy limit. Entropy based encoding, as described in this article, is generally only the final stage in a video "codec" (algorithm to compress, and decompress video). The first stage relies of finding information in the visual field that humans are unlikely to notice the loss of and discarding it. The second stage does interframe (between frames) compression by simply searching for blocks of pixels that match. Entropy coding is generally the final stage. This, by the way, is why zipping a video file can make it... larger.
- domador 4y ago
  That lossy compression "escapes" the Shannon entropy limit doesn't seem like an accurate way of putting it. Lossy compression throws information away, so there is less information to compress. The entropy limit is still in place. I agree with the overall point, though, that movie files aren't "zipped" up, but are compressed using lossy compression (with few exceptions).
  - kidme5 4y ago
    Lossy compression is something Shannon specifically addressed with Rate Distortion Theory https://en.wikipedia.org/wiki/Rate%E2%80%93distortion_theory https://en.wikipedia.org/wiki/Rate%E2%80%93distortion_theory
- abetusk 4y ago
  This is a pretty unkind reading. The author almost surely was using zip as a synonym for compress. Some people use "hoover" as a proxy for vacuum, even though they're not literally using a Hoover vacuum to clean. Movies aren't "escaping" the Shannon entropy limit, they're falling well within the Shannon entropy limit for the appropriate domain of human vision. Whether it's throwing out high frequency noise at one stage or using moving blocks and keeping delta changes at another, there's an underlying assumption of the "codeword" space is versus the source space. Even by the time it gets to the codec it's already "compressed" by throwing out almost all the spectra not visible to us. These are implicit assumptions about the domain that you've dismissed.
ffhhj 4y ago
The Dartmoth Workshop: http://www-formal.stanford.edu/jmc/slides/dartmouth/dartmouth/node1.html http://www-formal.stanford.edu/jmc/slides/dartmouth/dartmout...
vba616 4y ago
"If someone tells you a fact you already know, they’ve essentially told you nothing at all." I think it's interesting to consider how this is/is not true in a real life context. If someone tells you a fact you already know, then it could be communicating several different things. 1. It might mean *they think* you don't know it. 2. It might mean they want to make sure *you know* they know you know it. 3. It might mean they believe you know it and want to communicate they agree. 4. It might mean they are hoping for you to (or not to) contradict/argue/refute it. If, however, you can't tell which of those (or some other alternative) is intended, then no information was communicated at all. Except...there is a message communicated that they have some interest or concern regarding the topic, which is different from remaining silent. Whenever someone says anything, true, false, nonsense, lie, they are communicating a true and possibly significant fact - that they chose to say that thing, in whatever circumstance. I am thinking of "Gödel, Escher, Bach", if you can't tell.
- phreeza 4y ago
  > "If someone tells you a fact you already know, they’ve essentially told you nothing at all." The reality of zero information transfer is more subtle than this quote makes it sound, and covers the point you raise. In reality, you must not just know the thing you are being told, but you also have to know in advance that it is the thing you are going to be told. So if I tell you "the sun is shining" when you already know it is, there is still information being transferred if I could also have said "yesterday it was raining". Only if "the sun is shining" is absolutely the only thing I could have said is it a zero information statement.
  - pyinstallwoes 4y ago
    There is information in the fact a signal was sent and received from the observer of the receiver.
    - phreeza 4y ago
      If the receiver didn't assign a prior probability of 1 to the sender sending the signal then yes.

77 points by harscoat 4y ago

For anyone interested in these ideas, I'd highly recommend reading Shannon's original 1948 paper (linked in the article). While technical and precise it is actually quite digestible for someone with a bit of a quantitative background.

ivansavz 4y ago
link to paper abstract: https://ieeexplore.ieee.org/abstract/document/6773024 https://ieeexplore.ieee.org/abstract/document/6773024 direct link to PDF: https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6773024 https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=677...
- nighthawk454 4y ago
  direct direct link: https://sci-hub.hkvisa.net/10.1002/j.1538-7305.1948.tb01338.x https://sci-hub.hkvisa.net/10.1002/j.1538-7305.1948.tb01338....
prophesi 4y ago
I'd also highly recommend watching The Bit Player documentary. Not as info-dense as an article or paper, but it's a fun ride.

mpalmer 4y ago

Information theory is fascinating to anyone who likes the mathy underpinnings of seemingly non-mathy things, and it's everywhere. Cool stuff. Speaking of information and decompression, my brain initially interpreted the title as a breaking news headline about a female supervillain who's also a theory nerd. It was only the added context of the domain name that fixed the error.

acjohnson55 4y ago

The information theory class I took in grad school was one of the most mindbending classes I've ever taken. It made doing gnarly math problems fun. Claude Shannon was a titan. He's also known for publishing what some call the most important masters thesis of all time, https://en.wikipedia.org/wiki/A_Symbolic_Analysis_of_Relay_and_Switching_Circuits https://en.wikipedia.org/wiki/A_Symbolic_Analysis_of_Relay_a....

_wldu 4y ago

One example I like to use (when talking about entropy): A four digit numeric PIN (that we know) has 0 bits of entropy. There is no uncertainty about what the PIN actually is. A randomly selected one (that we do not know) has just over 13 bits. print(math.log(10)/math.log(2)*4) 13.28771237954945 The more entropy, the more uncertain we are. However, humans are not random. We use the year we were born, some keyboard sequence or some other predictable number as our PIN. We don't know exactly how much entropy these PINS have (there is some degree of uncertainty), but we do know they are significantly less than 13 bits.

mnks 4y ago
I wrote a blog post [1] with an interactive widget where you can provide an encoding for a random decimal digit and see how close you can get to the theoretical log₂(10) ≈ 3.32 bits. [1]: https://blog.kardas.org/post/entropy/ https://blog.kardas.org/post/entropy/ (Average Code Length section)
vba616 4y ago
Here's a riddle. If using my birthday reduces the entropy of my PIN, what does it do to its entropy if I happen to have the same birthday as one of the most famous people in the world? Does it matter if I am aware or not? Does it matter what they use for their PIN? For the sake of argument, I'm thinking month and day, not year.
- diffeomorphism 4y ago
  That is not a riddle just a question how to handle information on the distribution of passwords in the population. So you get the same answer as if it were four alphabetic characters and your choice is "soup".
- rcxdude 4y ago
  The important thing is that your PIN has zero entropy, regardless of its value. Entropy is a property of distributions, not individual values. You may be thinking of the probability (or information content) your PIN is assigned when looking at the overally distributions of PIN, in which case it probably does matter how popular your birthday is (and whether it also matches common patterns people use for PINs). This does feed into the calculation of entropy for the distribution but then it ceases to tell you anything about your PIN specifically. It also only makes sense when you are looking at it relative to the distribution, so it matters how you specify the PINs you are comparing it to. The 'information content' of a given outcome is the logarithm of the inverse of its probability (i.e. more unlikely events give you more information), and the entropy of a distribution is the expected value of this information content.

bob1029 4y ago

Information theory is so cool. I feel like having a solid grasp of the fundamentals is critical for achieving mastery in software development. Closely related would be digital signal processing and frequency domain techniques, both also extremely useful in many branches of software. The actual information content of a thing has always surprised me, especially when factoring in slightly imperfect (but passable) representations such as JPEG or MP3. To lose some information seems entirely acceptable in many cases.

ttctciyf 4y ago

> Engineers can build probabilistic models for patterns of pixel colors from one frame to the next. The models make it possible to calculate the Shannon entropy [...] That value tells you the limit of “lossless” compression — the absolute most the movie can be compressed before you start to lose information about its contents. While this is generally true in practice, strictly speaking the shortest possible encoding of a sequence of bits could be smaller than this would suggest, since it's possible a pattern exists that has escaped notice. For example: the first 10 billion digits of pi pass statistical tests for randomness, but can be generated by a short program which calculates them until the desired length is reached, in effect "compressing" them to the length of the generator program. Because of considerations like this, Algorithmic Information Theory[1] equates the information content of a bit sequence with the length of the shortest program which will generate it - though this has the drawback of being generally uncomputable - an intriguingly different paradigm. 1: see https://en.wikipedia.org/wiki/Algorithmic_information_theory https://en.wikipedia.org/wiki/Algorithmic_information_theory

Eddy_Viscosity2 4y ago
Could a smaller program be written that could generate the code that generates the digits of pi? So the code that writes the code is the smallest information content? I wonder how many times this could recurse before there is a limit..
- zbobet2012 4y ago
  That's the https://en.wikipedia.org/wiki/Kolmogorov_complexity https://en.wikipedia.org/wiki/Kolmogorov_complexity. It's uncomputable in general.
  - Eddy_Viscosity2 4y ago
    Nice, this is exactly what I meant. Actually kind of proud of myself for having a similar thought as Kolmogovov.
corey_moncure 4y ago

javajosh 4y ago

I'm more interested in the problem of sending strings out into the world where more strings may "stick" to them, possibly producing more strings. You know, like life. Or software. Given a particular string, can do you determine its age? Can you determine which discrete strings came into contact with it along its journey and when? And so on. I'm not sure if this is interesting to anyone else, but it sure is interesting to me! Consider how these are the boundary conditions that justify software design decisions so primordial we don't even consider them decisions anymore.

zbobet2012 4y ago

> That you can zip a large movie file, for example, owes to the fact that pixel colors have a statistical pattern, the way English words do. Engineers can build probabilistic models for patterns of pixel colors from one frame to the next. This is, in fact, incorrect generally. Movie files are generally compressed via _lossy_ compression, which escapes the Shannon entropy limit. Entropy based encoding, as described in this article, is generally only the final stage in a video "codec" (algorithm to compress, and decompress video). The first stage relies of finding information in the visual field that humans are unlikely to notice the loss of and discarding it. The second stage does interframe (between frames) compression by simply searching for blocks of pixels that match. Entropy coding is generally the final stage. This, by the way, is why zipping a video file can make it... larger.

domador 4y ago
That lossy compression "escapes" the Shannon entropy limit doesn't seem like an accurate way of putting it. Lossy compression throws information away, so there is less information to compress. The entropy limit is still in place. I agree with the overall point, though, that movie files aren't "zipped" up, but are compressed using lossy compression (with few exceptions).
- kidme5 4y ago
  Lossy compression is something Shannon specifically addressed with Rate Distortion Theory https://en.wikipedia.org/wiki/Rate%E2%80%93distortion_theory https://en.wikipedia.org/wiki/Rate%E2%80%93distortion_theory
abetusk 4y ago
This is a pretty unkind reading. The author almost surely was using zip as a synonym for compress. Some people use "hoover" as a proxy for vacuum, even though they're not literally using a Hoover vacuum to clean. Movies aren't "escaping" the Shannon entropy limit, they're falling well within the Shannon entropy limit for the appropriate domain of human vision. Whether it's throwing out high frequency noise at one stage or using moving blocks and keeping delta changes at another, there's an underlying assumption of the "codeword" space is versus the source space. Even by the time it gets to the codec it's already "compressed" by throwing out almost all the spectra not visible to us. These are implicit assumptions about the domain that you've dismissed.

ffhhj 4y ago

The Dartmoth Workshop: http://www-formal.stanford.edu/jmc/slides/dartmouth/dartmouth/node1.html http://www-formal.stanford.edu/jmc/slides/dartmouth/dartmout...

vba616 4y ago

"If someone tells you a fact you already know, they’ve essentially told you nothing at all." I think it's interesting to consider how this is/is not true in a real life context. If someone tells you a fact you already know, then it could be communicating several different things. 1. It might mean *they think* you don't know it. 2. It might mean they want to make sure *you know* they know you know it. 3. It might mean they believe you know it and want to communicate they agree. 4. It might mean they are hoping for you to (or not to) contradict/argue/refute it. If, however, you can't tell which of those (or some other alternative) is intended, then no information was communicated at all. Except...there is a message communicated that they have some interest or concern regarding the topic, which is different from remaining silent. Whenever someone says anything, true, false, nonsense, lie, they are communicating a true and possibly significant fact - that they chose to say that thing, in whatever circumstance. I am thinking of "Gödel, Escher, Bach", if you can't tell.

phreeza 4y ago
> "If someone tells you a fact you already know, they’ve essentially told you nothing at all." The reality of zero information transfer is more subtle than this quote makes it sound, and covers the point you raise. In reality, you must not just know the thing you are being told, but you also have to know in advance that it is the thing you are going to be told. So if I tell you "the sun is shining" when you already know it is, there is still information being transferred if I could also have said "yesterday it was raining". Only if "the sun is shining" is absolutely the only thing I could have said is it a zero information statement.
- pyinstallwoes 4y ago
  There is information in the fact a signal was sent and received from the observer of the receiver.
  - phreeza 4y ago
    If the receiver didn't assign a prior probability of 1 to the sender sending the signal then yes.