3 ms·

Someone else commented on this too, and I'm not sure exactly where to go with that. Discussing block length and compression is deeper into that particular issue

Someone else commented on this too, and I'm not sure exactly where to go with that. Discussing block length and compression is deeper into that particular issue than I was really hoping to go in this, but I don't know of an easier way of explaining it. Any ideas?

lmkg 16y ago
It may be "deeper," but for me information theory only really clicks in my head in the context of compression. Without compression, I see some voodoo hand-waving with logarithms and I don't even know what it means for an event to have X bits of entropy, or why I should care, or if I should believe the result. With compression, the entropy is suddenly a concrete measurable value with real-world import, and it's cool that you can prove hard lower bounds like that. So it may be deep, but at least to me it makes the whole thing make sense, rather than just adding complication. You may be able to dodge the issue by not mentioning compression explicitly. It's nonsensical that a single die roll takes 2.58 bits, but it's perfectly believable that 100 die rolls could fit in 258 bits. Then with a little work, you can show that 258 is the smallest expected value of any encoding. That uses the concept of compression as an intuitive model, without having to formally define it or call it by name.
- moultano 16y ago
  Ok, check it now. I added a little bit about that, though I'm sure I could still improve the wording. Now we have something whose unit is "bits" but whose value includes fractions of a bit. What can we do with this? After all, if we're only storing one roll, we still need 3 bits to store 6 possibilities. The trick is that we can use fewer bits if we are storing more rolls at once. There are 2 wasted possibilities in those 3 bits we used for the first roll, and if you're clever, you can use those to encode some information about the next roll. If we're clever enough, and storing enough, 2.58... is the lower bound on the number of bits required per roll that you'll converge to with an optimal compression scheme.
- tel 16y ago
  You'd probably enjoy formulations involving Kolkgomorov Complexity or Minimum Message Length, both of which cover similar topics while having more direct interpretations for complexity.
- jallmann 16y ago
  > It's nonsensical that a single die roll takes 2.58 bits, but it's perfectly believable that 100 die rolls could fit in 258 bits. It takes 3 bits to code for six values, but that is clearly a loose bound, since 2^3 = 8. But by taking the base-2 logarithm, you can get the exact number of bits required. That's how I rationalize it. The 258-bits-in-100-die-rolls is a nice trick though. This is why the logarithm is my favorite mathematical function -- it's not just an operation on a number, but it also describes various properties of the number itself. Depending on how you use the log, it can describe the number of digits the input has, or how much "information" can be contained in the input, and so forth.
kd0amg 16y ago
The textbook I first learned it from described entropy as the amount of uncertainty associated with the event[1]. I don't remember whether it tried to form an explicit link to "bits" in the sense of "amount of computer memory/storage." Perhaps you could trick people into not getting confused by using another name at first and then later showing the conversion from uncertainty measured in [other-unit-name] to the minimum average number of bits to encode the outcome is the identity function. [1] It helped that the book gave axioms for uncertainty and then derived the -sum(p*log(p)) formula.

lmkg 16y ago

It may be "deeper," but for me information theory only really clicks in my head in the context of compression. Without compression, I see some voodoo hand-waving with logarithms and I don't even know what it means for an event to have X bits of entropy, or why I should care, or if I should believe the result. With compression, the entropy is suddenly a concrete measurable value with real-world import, and it's cool that you can prove hard lower bounds like that. So it may be deep, but at least to me it makes the whole thing make sense, rather than just adding complication. You may be able to dodge the issue by not mentioning compression explicitly. It's nonsensical that a single die roll takes 2.58 bits, but it's perfectly believable that 100 die rolls could fit in 258 bits. Then with a little work, you can show that 258 is the smallest expected value of any encoding. That uses the concept of compression as an intuitive model, without having to formally define it or call it by name.

moultano 16y ago
Ok, check it now. I added a little bit about that, though I'm sure I could still improve the wording. Now we have something whose unit is "bits" but whose value includes fractions of a bit. What can we do with this? After all, if we're only storing one roll, we still need 3 bits to store 6 possibilities. The trick is that we can use fewer bits if we are storing more rolls at once. There are 2 wasted possibilities in those 3 bits we used for the first roll, and if you're clever, you can use those to encode some information about the next roll. If we're clever enough, and storing enough, 2.58... is the lower bound on the number of bits required per roll that you'll converge to with an optimal compression scheme.
tel 16y ago
You'd probably enjoy formulations involving Kolkgomorov Complexity or Minimum Message Length, both of which cover similar topics while having more direct interpretations for complexity.
jallmann 16y ago
> It's nonsensical that a single die roll takes 2.58 bits, but it's perfectly believable that 100 die rolls could fit in 258 bits. It takes 3 bits to code for six values, but that is clearly a loose bound, since 2^3 = 8. But by taking the base-2 logarithm, you can get the exact number of bits required. That's how I rationalize it. The 258-bits-in-100-die-rolls is a nice trick though. This is why the logarithm is my favorite mathematical function -- it's not just an operation on a number, but it also describes various properties of the number itself. Depending on how you use the log, it can describe the number of digits the input has, or how much "information" can be contained in the input, and so forth.

kd0amg 16y ago

The textbook I first learned it from described entropy as the amount of uncertainty associated with the event[1]. I don't remember whether it tried to form an explicit link to "bits" in the sense of "amount of computer memory/storage." Perhaps you could trick people into not getting confused by using another name at first and then later showing the conversion from uncertainty measured in [other-unit-name] to the minimum average number of bits to encode the outcome is the identity function. [1] It helped that the book gave axioms for uncertainty and then derived the -sum(p*log(p)) formula.