Return to Revisions

7 of 10

link updated

edited Mar 25, 2015 at 13:57

5.9k
3
34
72

Shannon entropy is a quantity satisfying a set of relations.

In short, logarithm is to make it growing linearly with system size and "behaving like information".

The first means that entropy of tossing a coin $n$ times is $n$ times entropy of tossing a coin:

$$ - \sum_{i=1}^{2^n} \frac{1}{2^n} \log\left(\tfrac{1}{2^n}\right) = - \sum_{i=1}^{2^n} \frac{1}{2^n} n \log\left(\tfrac{1}{2}\right) = n \left( - \sum_{i=1}^{2} \frac{1}{2} \log\left(\tfrac{1}{2}\right) \right) = n. $$

Or just to see how it works when tossing two different coins (perhaps unfair - with heads with probability $p_1$ and tails $p_2$ for the first coin, and $q_1$ and $q_2$ for the second) $$ -\sum_{i=1}^2 \sum_{j=1}^2 p_i q_j \log(p_i q_j) = -\sum_{i=1}^2 \sum_{j=1}^2 p_i q_j \left( \log(p_i) + \log(q_j) \right) $$ $$ = -\sum_{i=1}^2 \sum_{j=1}^2 p_i q_j \log(p_i) -\sum_{i=1}^2 \sum_{j=1}^2 p_i q_j \log(q_j) = -\sum_{i=1}^2 p_i \log(p_i) - \sum_{j=1}^2 q_j \log(q_j) $$ so the properties of logarithm (logarithm of product is sum of logarithms) are crucial.

But also Rényi entropy has this property (it is entropy parametrized by a real number $\alpha$, which becomes Shannon entropy for $\alpha \to 1$).

However, here comes the second property - Shannon entropy is special, as it is related to information. To get some intuitive feeling, you can look at $$ H = \sum_i p_i \log \left(\tfrac{1}{p_i} \right) $$ as the average of $\log(1/p)$.

We can call $\log(1/p)$ information. Why? Because if all events happen with probability $p$, it means that there are $1/p$ events. To tell which event have happened, we need to use $\log(1/p)$ bits (each bit doubles the number of events we can tell apart).

You may feel anxious "OK, if all events have the same probability it makes sense to use $\log(1/p)$ as a measure of information. But if they are not, why averaging information makes any sense?" - and it is a natural concern.

But it turns out that it makes sense - Shannon's source coding theorem says that a string with uncorrelted letters with probabilities $\{p_i\}_i$ of length $n$ cannot be compressed (on average) to binary string shorter than $n H$. And in fact, we can use Huffman coding to compress the string and get very close to $n H$.