from Hacker News

Shannon Entropy Imposes Fundamental Limits on Communication

by harscoat on 9/7/22, 8:07 PM with 49 comments

  • by vba616 on 9/8/22, 5:10 AM

    "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.

  • by zbobet2012 on 9/7/22, 11:55 PM

    > 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.

  • by ttctciyf on 9/7/22, 11:17 PM

    > 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

  • by acjohnson55 on 9/7/22, 10:18 PM

    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_a....

  • by rkp8000 on 9/7/22, 9:32 PM

    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.

  • by mpalmer on 9/7/22, 9:52 PM

    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.

  • by javajosh on 9/7/22, 11:52 PM

    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.

  • by _wldu on 9/7/22, 10:37 PM

    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.

  • by bob1029 on 9/7/22, 10:54 PM

    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.

  • by ffhhj on 9/8/22, 1:29 AM