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.

I'm familiar with information and coding theory, and do know that the units of Shannon information content (-log_2(P(A))) are "bits". Where "bit" is a "binary digit", or a "storage device that has two stable states".

But, can someone rigorously prove that the units are actually "bits"? Or we should only accept it as a definition and then justify it with coding examples.

Thanks!

share|improve this question
add comment

2 Answers 2

up vote 1 down vote accepted

When there are two events, both of which are equally likely, when conveying the news that one of them has actually happened, you convey -log2(0.5)=1 bit of information.

There is no rigorous proof here: just a mapping from a probability space to a bit-space (if I may call so). Either you see a binary random variable with equally likely 0 or 1, or you consider two equally likely stable states, whose representation would entail 1 bit.

share|improve this answer
    
But how you interpret the self-information of the event whose probability is 0.1? $-\log 0.1=6.6$? How you explain the mapping of 0.1 to 6.6 bits? what I think that this mapping should be taken as a definition. And all the specific examples can only justify this definition. –  Michael Mar 28 '12 at 8:10
1  
See, if the probability of an event is say 0.001, then we can understand that it takes places once in 1000 times. So the worth of the information is same as choosing one among 1000 likely events. In both cases, the information is log2(1000) bits. –  Bravo Mar 28 '12 at 8:31
    
Thanks Bravo! I like your explanation very much. Do you think it can serve as a formal prove/explanation? Or we still have to accept "bits" as definition? –  Michael Mar 28 '12 at 9:11
1  
Welcome :) It is only a way of looking at it. You cannot have a "proof" for it. Er, how does one 'prove' the unit of power is Watt? :) PS: If you are satisfied enough, press the accepted tick mark :) –  Bravo Mar 28 '12 at 9:28
add comment

A quick answer could be that if your storage device has probability $1/2$ of being in either of the two possible states, then the formula $$\sum_i -p_i\log_2(p_i)$$ gives you $=1$, so that is the unit. Somehow it sounds like you are not satisfied with that argument given that you have surely seen it?? Note that this does require the two states to be equiprobable. Note also that some (older?) sources occasionally measure information in nats instead of bits. The difference being that the natural logarithm is used in place of base-2 logarithm.

share|improve this answer
    
Thanks Jyrki. Your explanation is good, I thought about it. But it doesn't explain the case when the events do not have equal probability. It also doesn't explain the case of the Self Information: $-p_i\log p_i$. Regarding other units, once you can understand one unit (let's say - bit) you can scale it to everything else. –  Michael Mar 28 '12 at 8:00
    
correcting a mistake: Self Information is: $-\log p_i$ and not $-p_i\log p_i$. –  Michael Mar 28 '12 at 8:16
    
I don't know if this helps. In a sense a bit is the information content of the answer to a yes/no question. But if the answers to a dual question has severely unbalanced probabilities, then it is to your advantage to pack, or should I say compress several instances of the same question into one. Say, you are asking questions about the genders of early 20th century mathematicians, and you know that 15 out of 16 of them were male, so $p(\text{Female})=1/16$, and $-\log_2 p=4$. When playing "20 questions", the first question could be: "Was any of the following 4 mathematicians female?" –  Jyrki Lahtonen Mar 28 '12 at 9:41
    
... In the long run asking that question first saves a lot of questions in comparison to asking about genders of individual mathematicians. The idea being that it is wasteful to ask question, if you are almost certain about the answer. –  Jyrki Lahtonen Mar 28 '12 at 9:44
    
Thanks Jyrki. Your example is good to demonstrate the relation betwee bits and probability of the events. But it just another example and not a proof. So, as I wrote in the above comments, it looks like we should accept the units of "bits" as definition and then justify it using various examples. –  Michael Mar 28 '12 at 9:55
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.