# What is the role of the logarithm in Shannon's entropy?

Shannon's entropy is the negative of the sum of the probabilities of each outcome multiplied by the logarithm of probabilities for each outcome. What purpose does the logarithm serve in this equation?

An intuitive or visual answer (as opposed to a deeply mathematical answer) will be given bonus points!

-
You (or other readers) may enjoy: A. Renyi (1961), On Measures of Entropy and Information, Proc. of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, vol. 1, 547-561. – cardinal Feb 19 '14 at 17:58
Based on your reaction, I suppose what you mean is why Shannon used logarithm in his formula, right? – Ooker Nov 16 '15 at 17:56
@Ooker: That is one way to phrase it. "Why" did he put it in? "What" is it's function or role"? "What" does it achieve? "How" is it helpful? To me, these are all in the same neighborhood... – histelheim Nov 16 '15 at 18:41

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

-
This answer has a lot of nice details - but from a layman's perspective it still skirts the issue - what is the role of the logarithm? Why can't we calculate entropy without the logarithm? – histelheim Feb 19 '14 at 19:40
@histelheim What you mean by "without the logarithm"? $\sum_i p_i$ is just one. If you want another measure of diversity without $\log$, look at diversity indices - e.g. so-called Inverse Simpson index $1/\sum_i p_i^2$ which tells effective number of choices (one over average probability), there is Gini–Simpson index $1-\sum_i p_i^2$ which is always between 0 and one. And if you don't care for subtle information-related properties of Shannon entropy, you can use any of them (though, they weight low and high probabilities differently). – Piotr Migdal Feb 19 '14 at 19:51
I am baffled by your last comment, Histelheim: what could "entropy without the logarithm" possibly refer to? That suggests you haven't yet clearly articulated your question, because it sounds like you have some unstated concept of "entropy" in mind. Please don't keep us guessing--edit your question so that your readers can provide the kinds of answers you are looking for. – whuber Feb 19 '14 at 21:23
@ Piotr Migdal - you write "logarithm is to make it growing linearly with system size and "behaving like information"." - this seems crucial for me to understand the role of the logarithm, however I'm not quite clear as to what it means. – histelheim Feb 21 '14 at 2:51
@ Piotr Migdal - further, your explanation following "We can call log(1/p) information. Why?" seems to make sense to me. Is it that the logarithm essentially moves us from a diversity index to an information index - measuring the number of bits we need to tell the events apart. – histelheim Feb 21 '14 at 2:57

This is the same as the other answers, but I think the best way to explain it is to see what Shannon says in his original paper.

The logarithmic measure is more convenient for various reasons:

1. It is practically more useful. Parameters of engineering importance such as time, bandwidth, number of relays, etc., tend to vary linearly with the logarithm of the number of possibilities. For example, adding one relay to a group doubles the number of possible states of the relays. It adds 1 to the base 2 logarithm of this number. Doubling the time roughly squares the number of possible messages, or doubles the logarithm, etc.
2. It is nearer to our intuitive feeling as to the proper measure. This is closely related to (1) since we intuitively measures entities by linear comparison with common standards. One feels, for example, that two punched cards should have twice the capacity of one for information storage, and two identical channels twice the capacity of one for transmitting information.
3. It is mathematically more suitable. Many of the limiting operations are simple in terms of the logarithm but would require clumsy restatement in terms of the number of possibilities

Note that the Shannon entropy coincides with the Gibbs entropy of statistical mechanics, and there is also an explanation for why the log occurs in Gibbs entropy. In statistical mechanics, entropy is supposed to be a measure the number of possible states $\Omega$ in which a system can be found. The reason why $\log \Omega$ is better than $\Omega$ is because $\Omega$ is usually a very fast-growing function of its arguments, and so cannot be usefully approximated by a Taylor expansion, whereas $\log \Omega$ can be. (I don't know whether this was the original motivation for taking the log, but it is explained this way in a lot of introductory physics books.)

-
This answer seems to be the most focused yet informative. – Trevor Alexander Feb 20 '14 at 1:41
This isn't why the log appears in the entropy calculation. This is why the information reported is reported as such. There is an alternative quantity: the "perplexity" that reports information without the log. In this part of his paper, Shannon is arguing in favor of bits/nats/hartleys, and against perplexity. – Neil G Feb 25 '14 at 15:16

Here's an off-the-cuff explanation. You could say 2 books of the same size have twice as much information as 1 book, right? (Considering a book to be a string of bits.) Well, if a certain outcome has probability P, then you could say its information content is about the number of bits you need to write out 1/P. (e.g. if P=1/256, that's 8 bits.) Entropy is just the average of that information bit length, over all the outcomes.

-

another way of looking at this is from an algorithmic point of view. Imagine that you're going to guess a number $x$, that the only information you have is that this number is in the interval $1 \leq x \leq N$. In this situation, the optimal algorithm for guessing the number is a simple Binary search algorithm, which finds $x$ in order $O(\log_2N)$. This formula intuitively says how many questions you need to ask to find out what's $x$. For example, if $N=8$, you need to ask maximum 3 questions to find the unkown $x$.

From the probabilistic perspective, when you declare $x$ as being equally likely to be any values in range $1 \leq x \leq N$, it means $p(x) = 1/N$ for $1 \leq x \leq N$. Claude Shannon nicely showed that the information content of an outcome $x$ is defined as:

$$h(x) = \log_2 \frac{1}{p(x)}$$

The reason for the base 2 in the logarithm is that here we're measuring the information in bits. You can also assume natural logarithm which makes your information measure in nats. As an example, the information content of outcom $x=4$ is $h(4) = 3$. This value is precisely equal to the number of steps in the binary search algorithm (or number of IF statements in the algorithm). Therefore, the number of questions you need to find out $x$ is equal to $4$, is exactly the information content of the outcome $x=4$.

We can also analyze the performance of the binary search algorithm for any possible outcome. One way of doing that is to find out what's the expected number of questions to be asked for any values of $x$. Note that the number of required questions for guessing a value of $x$, as I discussed above, is $h(x)$. Therefore, the expected number of questions for any $x$ is by definition equal to:

$$\langle h(x) \rangle = \sum_{1 \leq x \leq N} p(x) h(x)$$

The expected number of questions $\langle h(x) \rangle$ is just same as the entropy of an ensemble $H(X)$, or entropy in short. Therefore, we can conclude that entropy $H(X)$ quantifies the expected (or average) number of the questions one need to ask in order to guess an outcome, which is the computational complexity of the binary search algorithm.

-
+ This is one of my favorite applications of information theory - algorithm analysis. If you have decision points with >2 outcomes, such as when you index an array, that's the principle behind hash coding and O(n) sorts. – Mike Dunlavey Feb 20 '14 at 1:07
This argument is fine for discrete entropy, but doesn't easily generalize to continuous entropy. – Neil G Feb 25 '14 at 15:25

The purpose of $\log(p_i)$ appearing in Shannon's Entropy is that $\log(p_i)$ is the only function satisfying the basic set of properties that the entropy function, $H(p_1, \ldots ,p_N)$, is held to embody.

Shannon provided a mathematical proof of this result that has been thoroughly picked over and widely accepted. The purpose and significance of the logarithm in the entropy equation is therefore self-contained within the assumptions & proof.

This doesn't make it easy to understand, but it is ultimately the reason why the logarithm appears.

I have found the following references useful in addition to those listed elsewhere:

1. Probability Theory: The Logic of Science by E.T. Jaynes. Jaynes is one of the few authors who derives many results from scratch; see Chapter 11.
2. Information Theory, Inference and Learning Algorithms by David MacKay. Contains an in-depth analysis of Shannon's source coding theorem; see Chapter 4.
-

## Summary:

Because it represents average total number of perfect questions that you need them to get answered in order to fully resolve all ambiguities in a data that you hadn't seen yet. A perfect question with $n$ possible answers is one that, when answered, the space of possibilities will be reduced by $n$ times.

## Example:

Suppose that I rolled a $6$-faced fair dice and you were to predict its outcome. The space of possibilities is $6$. You could ask me questions like this binary one "is the outcome $1$?" (answer is either yes or no, i.e. $n=2$) and my answer could be "nopies!". Then the space of possibilities by just $1$. So this question is not a good one to ask.

Alternatively, you could ask better questions, such as this superior binary question "is it greater than $3.5$?", and my answer would be "yeppies!" -- then boom, the space of possibilities is reduced down by half! I.e. there are just $6/2=3$ candidates left (out of the originally 6). Hell yeah dude.

Now suppose that you keep recursively asking more of these good questions until you reach the case when the space of possibilities has only $1$ possibility, by which -by definition- there is no ambiguity left (you know the answer).

Let's do this:

• $6$ possibilities. Q: Is outcome $> 3.5$? A: Yes.
• $6/2=3$ possibilities left. Q: is outcome $\ge 5$? A: Yes.
• $6/2/2=1.5$ possibilities left. Q: is outcome $= 6$? A: Yes.

You conclude that the outcome must be number $6$, and you only needed to ask $3$ binary questions. I.e. $ceil(\log_2(6)) = ceil(2.58) = 3$

Now, obviously, number of binary questions are always a natural number. So why doesn't Shannon's entropy use $ceil$ function? Because it actually spits out the average number of good questions that need to be asked.

If you repeat this experiment (by writing a Python code), you will notice that on average you will need to ask $2.58$ perfect binary questions.

Of course, if you ask binary questions, you set the base of the log to that. So here $\log_2(...)$ because our questions were binary. If you ask questions that expect $n$ many possible answers, you will set the base to $n$ instead of $2$, i.e. $\log_n(...)$.

## Simulation:

import random

total_questions = 0
TOTAL_ROUNDS = 10000

for i in range(0,TOTAL_ROUNDS):
outcome = random.randrange(1,7)
total_questions += 1
if outcome > 3.5:
total_questions += 1
if outcome >= 5:
total_questions += 1
if outcome == 5:
pass
else:
# must be 6! no need to ask
pass
else:
# must be 4! no need to ask
pass
else:
total_questions += 1
if outcome >= 2:
total_questions += 1
if outcome == 2:
pass
else:
# must be 3! no need to ask
pass
else:
# must be 1! no need to ask
pass

print 'total questions: ' + str(total_questions)
print 'average questions per outcome: ' + str(total_questions/float(TOTAL_ROUNDS))


Results:

total questions: 26634
average questions per outcome: 2.6634


Holy molly dude $2.6634 \ne \log_2(6) \ne 2.58$.

What's wrong? It's almost close, but not really close as I hoped. Is it Python's PRNG trying to say a slow joke? Or is it Shannon being wrong? Or is it -God forbid- my understanding is wrong? Either way HELP. S.O.S. already dude.

-
You're onto a good explanation. The resolution of your difficulty is to combine separate problems. I'll illustrate. Don't predict one die at a time: predict, say, five at a time. There are $6^5=7776$ possibilities. By asking $\lceil\log_2(6^5)\rceil=13$ questions you can pin down any possible combination. Consequently (because the dice are independent) there are an average of $13/5=2.6$ bits of information per die. Better, roll $190537$ dice: it takes $492531$ questions to discover all their values, or $492531/190537\approx 2.584962500722$ questions per die to predict them all. Etc. – whuber Apr 5 at 20:59
@whuber isn't this what I am doing in my code? I toss 10000 dies, and sum total number of questions I ask for all dies. I then do sum/10000 I get 2.66. – caveman Apr 6 at 20:41
No, you're not doing that in your code at all! You need to ask a set of questions designed to simultaneously obtain the state of all the dice at once. That is not the same thing as the average number of questions needed to find the state of one die at a time. – whuber Apr 6 at 20:42

Suppose we have a discrete information source that produces symbols from some finite alphabet $\Omega = \{\omega_1, \dotsc, \omega_n\}$ with probabilities $p_1, \dotsc, p_n$. Shannon defines the entropy as the measure $H(p_1, \dotsc, p_n)$ such that

• $H$ is continuous in its parameters,
• $H$ is monotone increasing in $n$ when $p_1 = \dots = p_n = \frac1n$ (since uncertainty is increasing), and
• $H$ is independent of how a choice is split into successive choices. For example, consider three events when rolling a black die and a white die: (1) the white die is odd, (2) the white die is even and the black die is less than three, and (3) otherwise. Either the dice are rolled together, or else the white die is rolled first, and maybe the black die if necessary. This requirement states that \begin{align} H\left(\frac12, \frac16, \frac13\right) &= H\left(\frac12, \frac12\right) + \frac12 H\left(\frac13, \frac23\right). \end{align}

Shannon proves that the only $H$ satisfying the three requirements has the form \begin{align} H(p_1, \dotsc, p_n) &= -\sum_{i=1}^np_i\log_kp_i \end{align} where $k>1$ corresponds to an arbitrary information measurement unit. When $k=2$, this unit is the bit.

-

Entropy is defined as the logarithm of the geometric mean of the multinomial coefficient that expresses the number of states a system can be in:

$$\log \sqrt[N]{N \choose n_1,\ldots,n_k}$$

The logarithms appear in the formula after using Stirling's approximation of the factorial (see this explanation)

-
I believe the OP knows the logarithm is part of the definition. They ask why is it there? – whuber Aug 4 '15 at 17:12

Based on your nonacceptance of any already answers, I think what you are looking for is the reason why Shannon used logarithm in his formula at the first place. In other words, the philosophy of it.

Disclaimer: I'm just into this field for a week, coming here because of having the question just like you. If you have more knowledge on this, please let me know.

I have this question after reading one of the most important paper of Ulanowicz, Increasing Entropy: Heat death or perpetual harmonies?. This is the paragraph explains why the formula has -log(p) instead of (1-p):

Before further unpacking the formal definition of entropy, one would be justified in asking why not simply choose (1 – p) instead of [–log(p)] as the most appropriate measure of nonexistence? The answer is that the resultant product with p (that is [p–p^2]) is perfectly symmetrical around the value p = 0.5. Calculations pursuant to such a symmetric combination would be capable of describing only a reversible universe. Boltzmann and Gibbs, however, were seeking to quantify an irreversible universe. By choosing the univariate convex logarithmic function, Boltzmann thereby imparted a bias to nonbeing over being. One notices, for example, that max[–xlog{x}] = {1/e} ≈ 0.37, so that the measure of indeterminacy is skewed towards lower values of pi.

Looks like that Shannon chose logarithm for no reason. He just "smelt" that he should use logarithm. Why did Newton choose multiply operation in his formula F=m*a?