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 have bumped many times into entropy, but it has never been clear for me why we use this formula:

If $X$ is random variable then it's entropy is:

$$H(X) = -\displaystyle\sum_{x} p(x)\log p(x).$$

Why are we using this formula? Where did this formula come from? I'm looking for the intuition. Is it because this function just happens to have some good analytical and practical properties? Is it just because it works? Where did Shannon get this from? Did he sit under a tree and entropy fell to his head like the apple did for Newton? =) How do you interpret this quantity in the real physical world?

Thanks for any explanations. =)

share|improve this question
    
That was well known in Statistical Mechanics. Max Planck derived it for a phonon gas. Take some visit to Jaynes stuff. –  Felix Marin Apr 25 at 5:18

6 Answers 6

up vote 7 down vote accepted

Entropy

We want to define a measure of the amount of information a discrete random variable produces. Our basic setup consists of a information source and a recipient. We can think of our recipient as being in some state. When the information source sends a message, the arrival of the message causes the recipient to go to a different state. This change is exactly what we want to measure.

Suppose we have a set of events with probabilities.

$p_1,p_2,...,p_n$

We want a measure of how much choice we are to make, how uncertain are we? Intuitively it should satisfy the following three conditions.

Let $H$ be our measure.

  1. $H$ is continous at every $p_i$

  2. If $p_1= p_2= ... = p_n$ I.E $p_i=1/n$ then $H$ is maximum (when every outcome is equally like the uncertainty is greatest and hence so is the entropy)

  3. If a choice is broken down into two successive choice the value of the original $H$ should be the weighted sum of the value of the two new ones. An example of condition 3 is that $H(1/2,1/3,1/6) = H(1/2,1/2) +1/2H(2/3,1/3)$

The only H satisfying the conditions above are. $H = −K\sum^n_{i=1}p_i log(pi)$

To see that this definition gives what we intuitively would expect from a 'measure' of information, we state the following properties of $H$.

  1. $H = 0$ ⇔ $p_i= 1$ and $p_j= 0∀j \neq i$
  2. $∀n ∈ N$ $H$ is maximum when $p_1=,...,= p_n$
  3. Suppose $x$ and $y$ are 2 events with $x ∈ R^n$, $y ∈ R^m$ and $p(i,j)$ the probability of joint occurrences.

    • $H(x,y) = −\sum_{i,j}p(i,j)log(p(i,j))$

    • $H(x,y) ≤ H(x) + H(y)$ with equality only if the occurrences are independent.

    • $H_x(y) = −\sum_{i,j}p_i(j)log(p_i(j))= H(x,y) − H(x).$ The entropy of y when x is known.

    • $H(y) ≥ H_x(y)$, The entropy of y is never increased by knowing x.

  4. Any change towards equalization of the probabilities increases $H$. Greater uncertainty ⇒ greater entropy.

share|improve this answer
    
Thank you for your answer! =) –  jjepsuomi Mar 15 '13 at 10:59
    
IIRC this result is due to Faddeev. –  Qiaochu Yuan Apr 28 '13 at 7:01

Here's one mildly informal answer. How surprising is an event? Informally, the lower probability you would've assigned to an event, the more surprising it is, so surprise seems to be some kind of decreasing function of probability. It's reasonable to ask that it be continuous in the probability. And if event $A$ has a certain amount of surprise, and event $B$ has a certain amount of surprise, and you observe them together, and they're independent, it's reasonable that the amount of surprise adds.

From here it follows that the surprise you feel at event $A$ happening must be a positive constant multiple of $- \log \mathbb{P}(A)$ (exercise; this is related to the Cauchy functional equation). Taking surprise to just be $- \log \mathbb{P}(A)$, it follows that the entropy of a random variable is its expected surprise, or in other words it measures how surprised you expect to be on average after sampling it.

Closely related is Shannon's source coding theorem, if you think of $- \log \mathbb{P}(A)$ as a measure of how many bits you need to tell someone that $A$ happened.

share|improve this answer
    
+1 Thank you for you answer! Your answer was very intuitive and I liked it :) Sorry I can only accept one answer :/ –  jjepsuomi Jun 6 '13 at 8:20

The three postulates in An.Ditlev's answer are the ones used in Shannon's original 1948 paper (pdf). If you skip over to Appendix II in that paper, you can find the remainder of the derivation.

  1. Derive the expression for $H(\tfrac{1}{n}, \tfrac{1}{n}, \ldots, \tfrac{1}{n})$ as $-K \log n$.

  2. If all the $p_i$'s are rational, we can find an $m$ such that $m p_i \in \mathbb{N}, \forall i$. Now, use postulate 3 to derive the entropy formula

  3. Using the continuity postulate (first postulate), you can directly extend the formula to the case where the $p_i$'s are not necessarily rational.

share|improve this answer
    
+1 Thank you for you answer! Appreciate the help! =) –  jjepsuomi Jun 6 '13 at 8:19

as physicist, I can confess: nobody knows what entropy is!!!!(regardless of the different attempts to nail it with mathematical definitions). There are also other definitions of entropy flying around in the physics community which are more consistent that the standard definition for certain situations.

share|improve this answer
    
+1 Thank you for you answer! Appreciate the help! =) –  jjepsuomi Jun 6 '13 at 8:18

I always try to understand these concepts related to energy and entropy. The following perspective from statistical physics (instead of informational entropy) is what I got so far.

Let $N = n_1 + ... + n_k$ and $p_i = \frac{n_i}{N} $. $$\log ( \frac{N!}{n_1 ! ... n_k ! } ) \approx - N \sum_i p_i \log p_i $$ by Stirling's formula.

I wonder if this was the first time ever in human history that such an expression $$\sum_i p_i \log p_i $$ appeared! Entropy is often too abstract to me. The approximation above is a link between counting combinations and entropy, and it seems to provide the most concrete grasp~ This is the genius of Boltzmann, Maxwell and Gibbs which leads to the development of statistical mechanics.

share|improve this answer
    
+1 Thank you for your help! :) –  jjepsuomi Nov 12 '13 at 8:29

The physical meaning of information entropy is: the absolute minimum number of storage "bits" needed to capture the information.

This can be less than implied by the number of different values a variable can take on. For example, a variable may take on $4$ different values, but if it takes on one of these values more often than the others, then one would need less than $\log(4)=2$ bits to store the information, if we choose an efficient way of storing the information.

We get entropy in terms of "bits" when the base of the log in the entropy equation is $2$. For some other technology, e.g., some esoteric memory based on tri-state devices, we would use log of base $3$ in the entropy equation. And so on..

For a verbose explanation of the intuition behind Shannon's entropy equation, you could check out this document: "Understanding Shannon's Entropy metric for Information"

share|improve this answer

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.