Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Shannon formally defined the amount of information in a message as a function of the probability of the occurrence of each possible message[1]. Given a universe of messages $\mathbf{M} = \{ m_1,m_2,..,m_n \}$ and a probability $\mathbf{p(m_i)}$ for the occurrence of each message, the information content of a message in $\mathbf{M}$ is given by:

$$\sum\limits_{i=1}^{n} -p(m_{i})\log_{2}(p(m_{i})) $$

How is this formula derived? Why did Shannon add $\log_2$?

[1]C.E. Shannon. A mathematical theory of communication. Bell Systems Technical Journal, 27:379–423, 623–656, 1948.

share|improve this question
11  
Since you mention the paper, I'd have assumed that you read it. But then you ask that question... Here, help yourself. –  Raskolnikov Mar 6 '11 at 20:18
1  
The $\log_2$ is just a convention, since in computer science people tend to work with bits, and you want the amount of information in one bit (with $p(m=0) = p(m=1) = 1/2$) to be equal to 1. Physicists tend use the natural logarithm, for example. –  Gerben Mar 6 '11 at 22:06
    
bits, nats, whatever –  yoyo Mar 6 '11 at 22:28
add comment

2 Answers 2

up vote 7 down vote accepted

Shannon proves in his paper that in order to code $n$ messages you need roughly $nH(M)$ bits. You can take that as the definition of entropy, and then derive Shannon's formula.

There are also axiomatic derivations of $H(M)$ - you start with some expected properties of the entropy function, and you end up with exactly that formula. I think that's also in Shannon's paper.

The logarithm comes in basically since to represent $T$ different messages you need at least $\log_2 T$ bits.

share|improve this answer
add comment

Toss a coin $n$ times. The probability of the outcome you get is $p=(1/2)^n$. The number of bits of information is $n$, which is $-\log_2 p$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.