# Relationship between compression, shannon entropy and kolmogorov complexity

I have read that the Shannon Entropy is used as a bound for the compressibility of a message, for example here 1 it says "In other words, the best possible lossless compression rate is the entropy rate.".

This makes a lot of sense if we look at a message m which is created by a random source, each bit m[i] is either 1 or 0 with probability p=0.5. Then we get a Shannon entropy of 1 bit per symbol, the message is not compressible.

Now let us look at a message m' where m[i] = i mod 2. For a long message we get the same probability distribution of symbols as in the previous example if we consider each bit as its own symbol. However, if we consider two adjacent bits as one symbol, then we have only 01 01 01 always repeating, so the Shannon entropy is 0. So my first question is: How to chose what constitutes a symbol when calculating Shannon entropy?

A related thing seems to be Kolmogoroff complexity: The Kolmogorov complexity of a string m is the number of bits which are needed for the shortest program which produces m when executed. How are the two related? For example if we build a fibonacci string s{x}, such that s{0} = 0, s{1} = 1, s{n}=s{n-2}s{s-1} it is clear that the Kolmogoroff complexity is very small (we just write a program that executes above instruction in a loop x times). Therefore we can send this program and the integer x as our "compressed data". However, as 1 claims that Shannon Entropy is a lower bound on compressed data size it should be equally small. But in this case how do we choose our symbols so that the Shannon Entropy gets close to zero?

I would really appreciate if someone could provide any intuition on this.

My thoughts on this is that maybe that sources such as 1 are a bit misleading, because Shannon just assumes we have the optimal probability distribution already, but actually it is not computable, just like Kolmogoroff complexity is not computable in general. Therefore if we use simple methods to compute a probability distribution, i.e., by assuming 1 symbol = 1 bit we get an approximation of the Shannon Entropy, not the exact value.

Regards, Timo

## 1 Answer

The actual choice of symbols does not affect Shannon entropy. In the example sequence 0 1 0 1 0 1 0 1 0 ... the fact that gives zero Shannon entropy is not to have certain symbols, but to have a very rigid structure. There are basically only two different states (corresponding to the parity of the index within the sequence). This stays the same if you increase the block size (considering 01 as a symbol, or taking 010 and 101 as symbols of length 3 etc.). What entropy measures is basically the exponential growth rate of those words (states) when the length of the blocks is increasing. If the number of such words does not grow with increasing length, this gives zero entropy.

For a random sequence you would expect to see all (most) symbol sequences of a fixed length. Over a binary alphabet, the number of those blocks would be $2^n$ where $n$ is the length. Now this has an exponential growth rate of $2$, which taking the usual logarithm (in base 2) yields the one-bit-per symbol entropy.

• Thanks for your answer! But I don't understand what you mean by "The actual choice of symbols does not affect Shannon entropy.". As I understand shannon entropy is defined as H(P) = - \Sum_{i} p_{i} * \log_{2}(p_{i}). If I use this definition I get a very different result if I choose "0" and "1" as symbols, compared with just "01". – timos Sep 13 '14 at 2:59
• After reading a bit more I think it is wrong that we should have small entropy in the "010101" example. See the second answer in stackoverflow.com/questions/592077/… : "Shannon's Theorem is defined in terms of random data and probabilities. Similarly, the entropy of a string is only defined for random strings -- the entropy is a property of the distribution, not of the strings themselves.". – timos Sep 13 '14 at 11:19
• But in your 01010101 example there is no randomness, i.e. the symbols are completely deterministic, hence if a source can only produce this kind of sequence its entropy is zero. – MHS Sep 13 '14 at 23:14
• The formula you give is valid for sequences whose entries are iid probability, i.e. symbols are independent identically distributed, which is a good assumption for a random sequence. You specify a probability for each symbol and then you flip a coin/throw a dice to fill each entry of your sequence independently from other symbols. In the 010101 sequence however there is no randomness, i.e. symbols are highly correlated and in fact choosing one (the first) determines all others. Hence the random variables are not independent and the formula does not give the correct value of Shannon entropy. – MHS Sep 13 '14 at 23:28
• For example consider the entropy of English language. Its alphabet has 26 letters, using letter frequency would give a value for the entropy using your formula above. However the real entropy value is in fact much lower (i.e. long text passages can be compressed better than what would be expected by the formula). The reason is again the non-independence built into most languages, for example given a certain letter like "q" there is a much higher probability that there is an "u" afterwards, also many combinations of letters are not part of English words at all, there are not too many consonants – MHS Sep 13 '14 at 23:40