An Introduction to Information Theory, Part 2: Entropy

Now that I've got a bit of background and origins done, it's time to get to some of the fun stuff.

As I said yesterday, both of the big branches of information theory have a concept of entropy. And while the exact presentations differ, because they're built on somewhat different theoretical foundations, the basic meaning of entropy in both branches is pretty much the same. I'm going to stick with the terminology of the Kolmogorov-Chaitin branch, but the basic idea is the same in either.

In K-C theory, we talk about the information content of strings. A string is an ordered sequence of characters from a fixed alphabet. It doesn't really matter what alphabet you choose; the point of this kind of theory isn't to come up with a specific number describing the complexity of a string, but to be able to talk about what information means in a formal algorithmic sense.

The entropy of a string is the total quantity of information encoded in that string.

Here's where it gets fun.

Another way of saying exactly the same thing is that the entropy of a string is a measure of the randomness of the string.

Structured strings are structured precisely because they contain redundancy - and redundancy does not add information.

Which string has more information: "XXXXYYYYY" or "4X5Y"? They have the same amount. One is a lot smaller than the other. But they contain the same amount of information.

Here's a third way of saying exactly the same thing: the entropy of a string is the length of the smallest compressed string that can be decompressed into the original.

Here's a better example. Go back and look at the first two paragraphs of yesterday's post. It took 514 character.

Here's the same information, compressed (using gzip) and then made
readable using a unix utility called uuencode:

M'XL(")E8$$0``VIU;FL`19$Q=JPP#$7[6≤7KIN',`M+]≤HHLPH``)\8BMOPY
M[#Y/GCDG#MLY2EI8$9H5GLX=*R(_+ZP/,-5-1#\HRJNT`77@LL,MZD,"H7LSUKDW3@$#V2
MH(KTO$Z^$%CN1Z>3L*J^?6ZW?^Y2+10;\+SOO'OC"/;7T5QA%987SY02I3I$
MLKW"W,VZ-(J$E"[$;'2KYI^\-_L./3BW.+WF3XE8)≤@D8X^U59DQ7IA*F+X/
MM?I!RJ*%FE%])Z+EXE+LSN*,P$YNX5/P,OCVG;IK=5_K&CK6J7%'+5M,R&J]
M95*W6O5EI%G^K)8B/XV#L=:5_`=5ELP#Y#\UJ??>[[DI=J''*2D];K_F230"
$`@(`````
` 

That's only 465 characters; and if I didn't have to encode it to stop
it from crashing your web-browser, it would only have been 319
characters. Those characters are a lot more random than the original -
so they have a higher information density. The closer we get
to the shortest possible compressed length, the higher the information
density gets.


Actually, I'm lying slightly; there's an additional factor that needs to be considered in K-C theory.

Remember that K-C comes from the foundational mathematics of computer science, something called recursive function theory. We're talking about strings being processed algorithmically by a program. So really, we get to talk about programs that generate strings. So it's not just strings: you have a program and a data string. Really, you measure information content of a string as the total size of the smallest pairing of program and data that generates that string. But for most purposes, that doesn't make that much difference: the combination of the program and the data can be encoded into a string.

In the two examples above, the program to follow is implied by the contents of the string; if we wanted to really model it precisely, we'd need to include the programs:

• For the string "XXXXYYYYY", the program is roughly:
  

  
         while there are more characters in the data:
            read a character
            output the character that you read
         end
  



• For the string "4X5Y", the program is roughly:
  

  
        while there are more characters in the data:
           read a number n from the data
           read a character c from the data
           output c n times
        end
  

  
  

Now, specifics aside: the definitions I gave earlier are pretty much correct in both K-C and Shannon information theory: information content is proportional to randomness is proportional to minimum compressed length.

So - what happens if I take a string in very non-compressed format (like, say, an uncompressed digitized voice) and send it over a noisy phone line? Am I gaining information, or losing information?

The answer is gaining information. Introducing randomness into the string is adding information.

"AAAABBBB" is less information than "AAAABxBB".

The way this is used to refute bozos who claim things like "You can't create information" should be obvious.