Intuitive explanation of entropy

Question

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?

Answer 1

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.

Answer 2

We want to define a measure of the amount of information a discrete random variable produces. Our basic setup consists of an 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 $n$ events with respectively the following 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 four conditions.

Let $H$ be our "measure".

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

2. If $p_i = 1$, then $H$ is minimum with a value of $0$, no uncertainty.

3. If $p_1 = p_2= \dots = p_n$, i.e. $p_i=\frac{1}{n}$, then $H$ is maximum. In other words, when every outcome is equally likely, the uncertainty is greatest, and hence so is the entropy.

4. If a choice is broken down into two successive choices, the value of the original $H$ should be the weighted sum of the value of the two new ones.

   An example of this condition $4$ is that $$H\left(\frac1{2}, \frac1{3}, \frac{1}{6} \right) = H\left(\frac{1}{2}, \frac{1}{2} \right) + \frac{1}{2} H\left(1 \right) + \frac{1}{2} H\left(\frac{2}{3}, \frac{1}{3} \right)$$

Here we decided to either take the a) first element or b) one of the other two elements. Then in a) we had no further decision, but for b) we had to decide which of those two to take.

The only $H$ satisfying the conditions above is:

$$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 \iff p_i = 1$ and $p_j= 0, \forall j \neq i$
2. $\forall n \in N$, $H$ is maximum when $p_1=,\cdots,= p_n$

3. Suppose $x$ and $y$ are two events with $x \in R^n$, $y \in R^m$ and $p(i,j)$ is the probability that $x$ and $y$ jointly occur (i.e. occur at the same time).

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

   • $H(x, y) \leq 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) \geq 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 $\Rightarrow$ greater entropy.

Here is a post with some illustrative R code

Answer 3

Let me give you an intuitive (rather than mathematically rigorous) interpretation of entropy, denoted $H(X)$.

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

Answer 4

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.

Answer 5

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

1. Derive the expression for $H \left(\tfrac{1}{n}, \tfrac{1}{n}, \ldots, \tfrac{1}{n} \right)$ 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.

Answer 6

Consider transmitting long numbers, e.g. values between 0 and 999,999 (decimal).

Each value can take one of out of a million possible states, and yet we can transmit each number with only 6 digits.

Noting that:

$$\log_{10}(1,000,000) = 6$$

Note that I've set the log base to match the number of symbols (0 to 9), and that the result is the number of (decimal) digits needed to encode a number with one million possible states.

For binary we get:

$$\log_{2}(1,000,000) \approx 19.93 \text{ bits}$$

So, hopefully, you can see that log({number of possibilities}) inherently gives a measure of how much information (how many digits) we need to encode a variable with $N$ possible states.

It may also be useful to move the minus sign inside the log, recalling that:

$$-\log{x} = \log{\frac{1}{x}}$$

Thus:

$$H(X) = \sum{p(x)}\log{\frac{1}{p(x)}} $$

So, in the above discussion, it looks like we just equated these two terms:

$$\{\text{number of possibilities}\} = \frac{1}{p(x)}$$

Which sort of makes sense. For example, if $p(x) = 1$, then $x$ can be the only possible value; if $p(x) = 0.5$, then there may be lots of other values, but there can be only one other at most with that same share of the probability, i.e. $0.5$.

So, $\log \left(\frac{1}{p(x)} \right)$ is giving us an amount of information fitting for a value with probability $p(x)$. We then multiply that amount of information by the probability of that value actually occurring, effectively calculating a weighted sum over all of the possible values. Giving:

$$H(X) = \sum{p(x)}\log \left( \frac{1}{p(x)} \right) $$

Answer 7

I see entropy as a number that gives you an idea of how random an outcome will be based on the probability values of each of the possible outcomes in a situation.

Let's start with a simple case. Suppose only a single outcome is possible, then there is only one value of $i$ ($=1$) and $p_{1}=1$. From the formula, the entropy is then zero:

$$-p_{1} \log(p_{1}) = p_{1} \log \left(\frac{1}{p_{1}} \right) = 1 * 0 = 0$$

This is cool! When the outcome will be the same every single time, the "randomness" is zero, and so the entropy does indeed correspond to a measure of randomness.

Now, before moving to more complicated cases, let's look at a plot of the factors involved in the entropy formula. Let me rewrite the formula first as follows:

$$ - \sum_{i} p_{i} \log(p_{i}) = \sum_{i} p_{i} \log \left(\frac{1}{p_{i}} \right)$$

Looking at this plot you see that there is nothing really special about $\log \left( \frac{1}{p} \right)$, really any function of $p$ such that $f(1) = 0$ would have done the trick.

Now, you might wonder, what if I have two possible outcomes, one that is nearly certain and one that is very unlikely; for example $p_{1} = 0.999$ and $p_{2} = 0.001$. This case is tricky!

For the first outcome, we see that $p_{1} \log\left(\frac{1}{p_{1}} \right)$ is a number very close to zero. That first outcome is not too different from the single-outcome situation we looked at before.

For the second outcome, $p_{2} = 0.001$, let's think about the limit of the product $p\log(\frac{1}{p})$ as $p \rightarrow 0$. Intuitively, we know that if we add an extremely unlikely event, such as the one with $p_{2} = 0.001$, the "randomness" situation should not really be that different from our original single-outcome process.

Let's look at a graph to see what the definition of entropy does for us in this case:

Beautiful! This means that an extremely unlikely event contributes nearly zero to the entropy of the system. Extremely likely and extremely unlikely are similar in terms of their "randomness": they have pretty much none of it!

Why the logarithm?

At this point you might be wondering, what is so special about the logarithm? It does seem kind of an arbitrary choice. There certainly must be other functions of $p$ that have the same convergence properties as $p$ goes to $0$ and $p$ goes to $1$.

So, I'll give you a situation to think about. Suppose you have a system where there are two equally likely choices $1$ and $2$, with probabilities $p_{1} = p_{2} = \frac{1}{2}$. That situation will have some entropy, let's call it $S_{2}$. Consider also a second system with an entropy $S_{3}$ where there are three equally likely choices $A$, $B$ and $C$, with probabilities $p_{A} = p_{B} = p_{C} = \frac{1}{3}$.

It would be nice if the entropy were a function such that if I considered the union of the two independent systems, the resulting entropy of the global system would be additive, that is

$$ S_{g} = S_{2} + S_{3} $$

In simpler words, it would be nice for our measure of "randomness" to be additive.

Let's be explicit here and write down the full expression for $S_{g}$, assuming that the events from one system are completely independent from events in the other system.

\begin{align} S_{g} = p_{1} p_{A} \log \left (\frac{1}{p_{1}p_{A}} \right) + p_{1}p_{B} \log \left(\frac{1}{p_{1}p_{B}} \right) + p_{1}p_{C} \log \left( \frac{1}{p_{1}p_{C}} \right) + \\ p_{2}p_{A} \log \left( \frac{1}{p_{2}p_{A}} \right) + p_{2}p_{B} \log \left( \frac{1}{p_{2}p_{B}} \right) + p_{2}p_{C} \log \left( \frac{1}{p_{2}p_{C}} \right) \end{align}

The property of the logarithm that makes it a good choice for defining entropy is then more clear:

$$ \log \left( \frac{1}{p_{1}p_{A}} \right) = \log \left( \frac{1}{p_1} \right) + \log \left( \frac{1}{p_A} \right)$$

Given this property, we can simplify $S_{g}$ as

$$ S_{g} = p_{1}\log\left( \frac{1}{p_{1}} \right) (p_{A} + p_{B} + p_{C}) + p_{1} S_{3} + p_{2} \log \left( \frac{1}{p_{2}} \right) (p_{A} + p_{B} + p_{C}) + p_{2} S_{3} $$

$$ S_{g} = S_{2} (p_{A} + p_{B} + p_{C}) + S_{3} (p_{1} + p_{2}) $$

Since probabilities add up to $1$, this gives us the desired property:

$$ S_{g} = S_{2} + S_{3} $$

This culminates our motivation for why the formula for entropy is what it is!

Key takeaway

I will summarize by saying that the key point is that "randomness" is hard thing to quantify. We can choose a measure for "randomness" (such as Shannon's entropy formula), and that choice is only informed by the properties that we want the measure to have.

When you look at

$$ S = - \sum_{i} p_{i} \log(p_{i}) $$

for the first time in your life you might think: where on earth did they pull this out from? But it turns out that it was a definition only informed by the properties that it holds.

An informal enumeration of these properties is given below:

1. An extremely likely event should not contribute much to the randomness measure.

2. An extremely unlikely event should not contribute much to the randomness measure.

3. Randomness should be additive.

Answer 8

The physical meaning of information entropy is:

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

Answer 9

Entropy is often too abstract to me! 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!

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.

Answer 10

If you understand expected value $\mathbb{E}$ of a random variable $X$, then the concept of entropy should be easier to understand. With no mathematical rigor, I'll express the entropy $H$ (of a discrete random variable $X$) in the following way:

$$ H(X) = \mathbb{E}[\text{surprise from outcome encoded in 2-bits}] = \mathbb{E}[\log(\text{surprise from outcome})]. $$

For an event $A$ with probability $p$, the surprise is inversely proportional to the probability of the event, $\frac{1}{p}$.

Answer 11

Although this question has been asked a long time ago and has received very relevant answers, I would like to add my personnal touch on the subject. Actually, since some time, I am wondering (like jjepsuomi) why the Shannon entropy is so ubiquitous and fascinating. Here is a summary of my current insight :

Information as reduction of uncertainty

An intuitive idea for understanding the information given by the unveiling of a random variable is to see this unveiling as a reduction of the space of what was possible before the variable was unveiled.

Suppose that you have a mysterious point $U$ that can be anywhere in a volume $V$ with uniform probability. A random variable X can be seen as a partition of $V$ into $N$ different smaller volumes $p_iV$. Due to uniformity, $U$ has the probability $p_i$ to be in the volume $V_i$.

Unveiling X will let us know in which domain $U$ stands. So, the possible area for $U$ will be reduced. The value of the new volume will be $p_iV$. We can define the reduction $r$ by $p_i$ itself. It can be seen as a function of $X$ and so, also as a random variable (that is why I prefer to call it r instead of $p_i$ that would be confusing). When $X$ has been unveiled, the intuitive notion of received information can safely be linked to the reduction $r$ (the smaller $r$, the more information I have received). Anyway, introducing a measure of information (like $\log(p_i)$) although tempting, is not useful right now. It will give some magic to the concept that will leads us too easily to the Shannon entropy that we want to discover without magic...

Shannon entropy as a metric to summarize reduction of uncertainty associated with a random variable

Now, suppose that $X$ has not yet been unveiled. We might find it useful to summarize the ability $X$ has to reduce $V$, through a single number.

Of course, a good candidate is the Shannon entropy, the opposite of the expected log of the reduction $r$ : $H=-\sum_ip_i\log(p_i)$.

A concurrent for Shannon Entropy ?

But, another metric is maybe more natural : the expected reduction itself : $\sum_ip_i^2$. I have spent some time looking at this metric and trying to figure out why it has not been as popular as the Shannon Entropy.

First, it is more elegant to introduce its logarithm : $G=-\log(\sum_ip_i^2)$ that have many intersting properties, similar to Shannon entropy's. (actually, only property 4 from the list given by @An.Ditlev is not valid).

In particular :

• We have $G(X,Y)=G(X)+G(Y)$ when $X$ and $Y$ are independent.

• We can devise a symetrical "mutual information" $I_G(X;Y)=G(X)+G(Y)-G(X,Y) \ge 0$

$H$ and $G$ are not measuring the same thing and we can find two random variables $X$ and $Y$ such that $H(X) \gt H(Y)$ while $G(X) \lt G(Y)$

Shannon Entropy is fitted for i.i.d sequences of random variables

Now, why Shanon Entropy has had a much better career that my $G$ metric ? Well, I guess it can be understood with the Asymptotic Expectation Property : In the case of a sequence of i.i.d random variables, we can prove (by the weak law of large numbers) that $\log(P(X_1,X_2,...,X_n)) \approx 2^{-nH}$. To put it simply, we are almost certain that the $\log()$ will be $2^{-nH}$ (that is a decreasing function of the Shannon Entropy). The higher the Shannon entropy, almost certainly the smaller the reduction!.

Strange examples

The success of the Shannon Entropy is due to the fact that we can decently forget the "almost" word in the last sentence.

That leads to a strange result. Let's go back to my previous example of two random variable $X$ and $Y$, $X$ having a higher $H$ and $Y$ a higher $G$. If we can chose between repeating a sequence $X_i$ or a sequence $Y_i$ :

If we chose $X$, we can be almost certain that the reduction $r$ will be better for $X$, but the average reduction will be beter with $Y$... That's because a set of sequences with a very small cumulated weight is sufficient to have a deep impact on the average in $G$.

It is analoguous to the problem of a gambler that can repeat an experiment where he has 50% chance to lose all his money and 50% chance to triple his bet. If he repeats the experiment a lot of times, he is almost certain to lose all its money, but on average, he will be very very rich... due to the very unlikely event that he will always win.

Things get stranger if we do not consider i.i.d variables but just a sequence of independent variables. Then, AEP don't stand and the Shanon Entropy can, in some cases, be quite a strange metric.

For instance, we can devise a sequence of independent random variables having each a Shannon Entropy of 1 bit while the probability $Pr(r \ge 0.5) \ge 0.5$. That is, the received Shanon Entropy increases to $\infty$, but the probability that we learn almost nothing remains quite important. (with random variables having the probability of the state 1 increasing rapidly to 1 with i but the remaining probability uniformly shared between a very rapidly number of states).

This is a work in progress... In particular, I would like to see the implication for the coding. Is there a coding that is best fitted for $G$? Is it true that, on average the $G$-coding will be shorter on average, while larger almost certainly ?

Conclusion

As a conclusion, I will say that the Shannon Entropy is just a metric that gives useful information about the ability a random variable has to reduce uncertainty. It does not describe it perfectly. (it is not a sufficient statistic of the probability distribution). While, there are some traps, in many case (i.i.d sequence) it is the most useful metric.

Answer 12

In my view, the most intuitive way to look at entropy, which I also think is also the most correct one is simply as follows:

1. If kilo grams is the measure of mass, seconds is the measure of time, meters is the measure of distance, then what is the measure of information? Say, how much information is inside a closed letter? In other words, if you open the letter and read it, how much information will you obtain?
2. Shannon's entropy basically tries to answer that question. The answer is very simple and extremely intuitive: how about we measure the quantity of information based on the number of questions that must be asked in order to fully discover all unknowns that were hidden in that thing. So in the case of the letter, the amount of information in the letter is the quantity of questions that we need to get answered in order to fully know the content of the letter.

But obviously there is a problem with (2), which is: how can the number of questions be meaningful? Someone may ask a single broad question like "what is inside the letter?" and fully obtain the letter. Or someone may ask really stupid questions like "what is the 1st letter?" then "what is the 2nd letter?", …, ending up with thousands of silly questions for a tiny letter!

Shannon's entropy solves this problem by standardising the questions, such that their numbers are stable and meaningful, and it does so by defining the qualities the questions must have. Turns out this is very easy!

Here is how the questions are standardised so that their quantity is stable:

The average number of perfect n-nary questions that, if answered, we would end up fully resolving all unknowns about the subject.

An $n$-nary question is "perfect" if it splits the search space evenly into $n$ many equal sub-spaces. So if a question is binary ($n=2$), then every time you ask a perfect binary question, it must split the search space in half.

Wait, that looks like a balanced tree! Balanced $n$-nary trees split the search space in $n$-many equal parts every time we move down by a single node.

In balanced $n$-nary trees, we have a tree root on top, and branches, until we finally reach terminal leaf nodes. Also, in a balanced $n$-nary tree, the total number of nodes that you need to cross until you finally reach the terminal leaf nodes is $\log_n \texttt{m}$, where $m$ is total number items stored in the balanced $n$-nary tree that you are trying to lookup — this is where the $\log$ part in entropy comes from!

Now, let's have a closer look at entropy:

$$ H(\mathcal{X}) = -\sum_{x\in\mathcal{X}} p_x \log_n(p_x) $$

Now let's unwrap it piece by piece. 1st let's get rid of that negative:

$$ H(\mathcal{X}) = \sum_{x\in\mathcal{X}} p_x \log_n(\frac{1}{p_x}) $$

That's it for the negative! It was added there only because $\log_n(\frac{1}{p_x})$ doesn't look neat enough. Basically $\log_n(\frac{1}{p_x}) = -\log_n(p_x)$.

HOMEWORK 1: The $\sum_{x\in\mathcal{X}} p_x \ldots$ is just a weighted sum. I leave you figure out why we need it on your own.

But what about $\log_n(\frac{1}{p_x})$? First let's remind ourselves what is $p_x$:

$$ p_x = \frac{\text{number of times $x$ happened}}{\text{number of times everything happened}} $$

And what does $\frac{1}{p_x}$ mean?

$$\begin{split} \frac{1}{p_x} &= \frac{1}{\frac{\text{number of times $x$ happened}}{\text{number of times everything happened}}}\\ &= \frac{\text{number of times everything happened}}{\text{number of times $x$ happened}}\\ \end{split}$$

Wow! You see! It's getting very similar to that $m$ in the balanced $n$-nary tree example (i.e. $\log_n m$ part above).

HOMEWORK 2: Now, I leave it to you to figure out how $\frac{\text{number of times everything happened}}{\text{number of times $x$ happened}}$ corresponds to $m$ in my balanced $n$-nary tree example earlier.

Now, only if you solve HOMEWORK 1 and HOMEWORK 2, you'd fully understand Shannon's entropy! It's actually very simple and intuitive.

Answer 13

There is an easy to understand video that illustrates, in layman terms, how to arrive at the formula for entropy:

https://www.khanacademy.org/computing/computer-science/informationtheory/moderninfotheory/v/information-entropy

The context of the video is information theory.

Answer 14

As a physicist, I can confess that not many people grasp 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, for certain situations, are more consistent than the standard definition.

Answer 15

Let me try to answer to part of your question where you ask how it's related to the "physical world" taking the same direction as MichaelNgelo's answer.

Let's say you have $N$ objects, out of them there are $n_1$ many $A$s and $n_2$ many $B$s.

How many ways can you order them? For example for $N = 4$, with one $A$ and three $B$s we have: $$ABBB$$ $$BABB$$ $$BBAB$$ $$BBBA$$

This is a combinatorics problem and we can find the formula: $$\frac{N!}{n_1!n_2!}$$

Note that there are more cases with $N=4$ and a arbitrarly number of $A$s and $B$s ($16$ cases) or with $N=4$ and with two $A$s and two $B$s ($6$ cases).

Given the proportions of $A$s and $B$s, it reduces the number of possibilities and we just need a way to differentiate between them.

This is where the logarithm comes in to tell the least amount of bits to differentiate between these $M$ cases. Explicitly we need $\log_2(M)$ bits.

Now divide by $N$ to find the number of bits needed per symbol in the sequence. So if put all together, the formula becomes:

$$\frac{\log_2(\frac{N!}{n_1!n_2!})}{N}$$

and for convenience instead of talking about $n_1$ and $n_2$ in absolute number, we talk about the fraction of $N$, respectively $f_1$ and $f_2$. Finally tending $N$ to infinity gives the shannon entropy.

Example with $f_1 = 0.25$ and $f_2 = 0.75$:

Someone experienced can probably derive the Shannon entropy formula from the formula above with $N$ tending to infinity.

So a possible interpretation of the Shannon formula would be: The number of bits needed per symbol given the proportions of each symbol in advance in an infinite sequence.