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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 its 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|cite|improve this question
1  
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 '14 at 5:18
1  
I just want to point out that there are simple pieces of software around on the Internet claiming to determine (and in fact they do correctly compute according to the formula of Shannon) the "entropy" of a user-given character sequence. However, entropy is a concept relevant to the source of randomness, not to a particular "given" sequence. Hence such calculations are problematical. See the thread crypto.stackexchange.com/questions/33231/entropy-calculation – Mok-Kong Shen Apr 10 at 9:12
up vote 18 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|cite|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
2  
What does it mean that H is continuous at every p(i)? – confused00 Nov 21 '15 at 14:39

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|cite|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
    
@QiaochuYuan I'm guessing it's impossible to 'prove' formally why entropy in theory of information is defined this way. Rather, we should start with an intuitive concept and try to define a mathematical formula satisfying the properties we want it to satisfy in the informal sense. So 'informal' answers are the most formal. What do you think? – user4205580 May 5 '15 at 19:07
    
How would you intuitively characterize temperature $T$ along these lines if we think of $1/T$ coming from $dS/dE = 1/T$ as giving us something like 'the change in our expected surprise as the random variable changes'? hyperphysics.phy-astr.gsu.edu/hbase/thermo/temper2.html – bolbteppa Sep 24 '15 at 18:39
    
First paragraph was useful... the rest got too abstract – CodyBugstein Oct 27 '15 at 17:59
    
What does this mean : "It's reasonable to ask that it be continuous in the probability"? – confused00 Nov 21 '15 at 14:40

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|cite|improve this answer
    
+1 Thank you for you answer! Appreciate the help! =) – jjepsuomi Jun 6 '13 at 8:19

You wanted an intuitive interpretation of entropy $H(X)$ entropy. Let me share with you one way that I understand entropy. Note that my explanation will be mostly intuitive rather than rigorously mathematical.

Let me start by giving you my interpretation first and then let me justify it.

Entropy can be viewed as the cost of encoding a specific distribution $X$.

Since I will describe it in terms of encoding messages, let me change the notation to make the description more intuitive. We want to transmit some message $(M=m)$ across some channel $C$. Intuitively, the cost of sending a messages across a channel is the length of the encoding of the message $m$. i.e. the longer the message, the more it will cost us to send the message since we have to send more (bits) of information. The frequency (and the probability) of getting each message is dictated by the language $\mathcal{L}$ which the message came from. For example, the language could be $\mathcal{L} = English$, were the word "the" is probably relatively common (i.e. high frequency and high probability) and thus, we should choose wisely how to encode this, since we will have to send it very often (or in the case of English, write it pretty pretty often!). So we want an efficient encoding for "the". By efficient, we want it to mean choosing a encoding that happens to choose less number of "stuff" (or information, bits etc) that we need to send through the channel. Since the messages we have to send are somewhat random, then its seems reasonable that we aim to send the least amount of bits that we can, at least on average. i.e intuitively, we want to minimize:

$$ E[ |M|] = \sum_m Pr[M=m]|m|$$

where $|m|$ denotes the length of the encoding of message m.

For example, we might want to encode it this way: for common (high probability) messages lets use fewer bits of information to encode them since we have to send them very frequently. So we can encode them based of the relative frequency dictated by the distribution for $\mathcal{L}$. With a little more thought you can come up with Huffman coding or some other scheme similar to it, if you make sure that the messages can be decoded unambiguously, the main idea in my opinion is to encode frequent words with short code lengths and infrequent ones with longer code lengths.

It turns out that Shannon proved that the notion of entropy provides a precise lower bound for the expected number of bits required to encode instances/messages sampled from $P(M)$. i.e. if we consider any proper codebook for values of $M \in \mathcal{L}$, then the expected code length, relative to the distribution $P(M)$, cannot be less than the entropy $H(M)$:

$$H(M) \leq E[|M|]$$

Since there exists a scheme that makes this inequality tight, then we can expect to encode the messages $M$ as efficiently as possible (on average).

Thus, returning to the interpretation I suggested. Since, the cost of encoding something can be thought of as the number of bits we need to send through a channel, and the optimum value (entropy) can be achieved, then entropy becomes the expected cost of encoding a distribution of messages.

(or if you want to view it from the inequalities perspective, its the best/minimum expected cost you can have to encode any known distribution $P(M)$.)

share|cite|improve this answer
1  
+1 Excellent! Thank you very much!! =) – jjepsuomi Aug 23 '14 at 10:51
1  
Well written! I am glad that it is clarified that entropy is property of the language and not the word that we are encoding. Also entropy is all about measure and not random variable. – user1700890 Sep 21 '15 at 15:02
    
@user1700890 what do you mean its about measure and not r.v.? If u have some better view on entropy to provide, please do! We all would like to learn :) – Charlie Parker Feb 12 at 1:26
1  
@CharlieParker well, values of r.v. do not matter for entropy, only distribution (measure) matters. – user1700890 Feb 12 at 20:02
    
@user1700890 oh I see what you mean. Yes sure. I guess I tried making an intuitive/conceptual explanation rather than a super rigorous one. If you want to add some supplementary remarks on my answer to point that out, I'd be happy to incorporate them. – Charlie Parker Feb 13 at 1:30

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|cite|improve this answer
    
+1 Thank you for your help! Appreciate it! =) – jjepsuomi Aug 23 '14 at 10:51

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|cite|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 \left( \frac{N!}{n_1 ! \cdots n_k ! } \right) \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|cite|improve this answer
1  
+1 Thank you for your help! :) – jjepsuomi Nov 12 '13 at 8:29

Here is a simple intuitive explanation of Shannon entropy.

The telegraph message "SOS" is encoded as "...---..." in Morse code. The thing to note is that the massage is made up of letters from the alphabet but what is transmitted down the communication line are only dots and dashes. The message is written in the alphabet but transmitted in dots and dashes. Morse code maps letters to dots and dashes.

Text messages, emails and instant messaging are all written in text (i.e. upper and lower case letters, space, tab, decimal digits, punctuation marks, etc) but transmitted as bits {0, 1}. For the mathematician the problem of communication is of finding the most efficient way of mapping text messages to streams of bits. By most efficient I mean the least number of bits. If I have a text message of 100 characters what is the smallest number of bits I need to transmit down the line?

From these examples we can see that message transmission involves 2 sets A and B. The message is a sequence of letters from set A but the communication line can only transmit characters from set B. Let $m_A$ be a message written in A and let $m_B$ be the same message written in B. Let E be an encoding function that maps messages from A to messages from B.

$$m_B = E(m_A)$$

We can measure the size of the message by counting the number of characters in the message. The length of $m_A$ is $L(m_A)$ and the length of $m_B$ is $L(m_B)$.

Clearly a short message will have a sort encoding and a long message will have a long encoding. If we double the length of the message we will double the length of the encoding. The length of the encoding will be proportional to the length of the message.

$$L(m_B) \varpropto L(m_A)$$

By introducing a constant of proportionality k we can turn this into an equation.

$$L(m_B) = kL(m_A)$$

The problem of finding the most efficient encoding reduces to find the minimum possible value of k. This minimum value is the entropy of the set A measured over the set B.

If

$$A = \{A_1, A_2, A_3, ..., A_n\}$$

and the probability of $A_i$ being in the message is $p_i$ and B is the set

$$B = \{B_1, B_2, B_3, ..., B_m\}$$

then the entropy is given by

$$Entropy = \sum_{i=1}^n p_i\log_m(\frac{1}{p_i})$$

Note that log is taken to the base m which is the size of the set B.

So far I have dealt with the most general case but now I will switch to the simple case when each of the n characters in A are equally likely so $p_i = \frac{1}{n} \forall i$.

$$Entropy = \sum_{i=1}^n \frac{1}{n} \log_m(n)$$

This simplifies to

$$Entropy = \log_m(n)$$

In this case the entropy only depends on the of the sizes of A and B.

To prove this is correct function for the entropy we consider an encoding $E: A^r \rightarrow B^s$ that encodes blocks of r letters in A as s characters in B.

$$L(m_A) = r, \space L(m_B) = s, \space m_B = E(m_A)$$

The range of E must be greater than or equal to the size of the domain or otherwise two different messages in the domain would have to map to the same encoding in the range. The size of the domain is $ n^r $ and the size of the range is $ m^s $. We chose s to satisfy the following inequalities.

$$m^{(s-1)} \lt n^r \le m^s$$

The right hand inequality ensures the range is greater than or equal to the domain. The left hand inequality ensures this is the smallest such s that has this property.

Taking the log to base m of both side of these inequalities gives us.

$$\log_m(m^{(s-1)}) \lt \log_m(n^r) \le \log_m(m^s)$$

$$(s-1)\log_m(m) \lt r\log_m(n) \le s\log_m(m)$$

$$\frac{(s-1)}{r} \lt \log_m(n) \le \frac{s}{r}$$

The constant of proportionality k we introduced earlier is the ratio $\frac{s}{r}$.

$$k = \frac{s}{r}$$

So the right hand inequality proves

$$ \log_m(n) \le k $$

This proves that $\log_m(n)$ is a lower bound for k but how close can an encoding come to the lower bound? We note that

$$\frac{(s-1)}{r} \lt \log_m(n) \le \frac{s}{r}$$

implies

$$\frac{s}{r}-\log_m(n) \lt \frac{s}{r}-\frac{(s-1)}{r}$$

$$\frac{s}{r}-\log_m(n) \lt \frac{1}{r}$$

$$k-\log_m(n) \lt \frac{1}{r}$$

We can make k as close as we like to $\log_m(n)$ by increasing the block size r.

This finishes our treatment of the special case of equal probabilities. Hopefully having proved that in this case the entropy is $ \log_m(n) $ the more general formula should not come as too much of a surprise.

I hope you find this simple explanation more intuitive than the usual approach. I searched the internet for an explanation of entropy but didn't like any of the results so I came up with my own. It took me 5 years but now I understand Shannon entropy.

share|cite|improve this answer
    
Thank you for your help! =) – jjepsuomi Apr 19 at 7:36

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.