Entropy, explained

Entropy is not the easiest thing to understand.

It is rumored to describe something about information and disorder, but it is not clear why. What do logarithms and sums have to do with the notion of information?

💡 Let me explain! 💡

$$H[x] = - \sum_{i=1}^{n} P(x_i) \log P(x_i)$$

I have randomly selected an integer between 0 and 31. Can you guess which one? You can ask as many questions as you want. What is the minimum number of questions you have to ask to be 100% sure?

You can start guessing the numbers one by one, sure. But there is a better way!

If you ask "is the number larger or equal than 16?", you immediately eliminate half the search space! Continuing with this tactic, you can find the number for sure in 5 questions. In other words, we need to take the base two logarithm of 32 to get the number of questions required.

This logic applies to all numbers! If I pick a number between 0 and $n-1$, you need $\log_2 n$ questions to find it for sure, by cutting the possibilities in half with each.

Because the questions are yes-or-no questions, we can encode each answer with a $\textstyle 0$ or $\textstyle 1$.

If we write down the answers in a row, we effectively encode the numbers in n bits!

𝟎: 00000
𝟏: 00001
𝟐: 00010
...
𝟑𝟏: 11111

This is simply the number in base 2!

No matter which number I pick, five questions are needed to find it. So, the average number of bits required is also five. However, we are using a critical assumption here: I pick each number with an equal probability. What if that is not the case? 🤔

Suppose that I am picking between 0, 1, and 2, but I am picking 0 at 50% of the time, while 1 and 2 only 25% of the time. We should put this into mathematical form now! Let's denote the number I pick with $\textstyle X$. This is what is called a random variable. The probability distribution is given by

$$\begin{aligned} P(X = 0) &= 1/2, \\ P(X = 1) &= 1/4, \\ P(X = 2) &= 1/4. \end{aligned}$$

How many bits do we need now? We can be more bit-efficient than before! Consider this.

1st question: did you pick 0? If the answer is yes, the 2nd question is not needed. If no, we proceed!

2nd question: did you pick 1? No matter what the answer is, we know the solution! Yes implies 1, no implies 2.

Thus, the average number of bits are

$$\begin{aligned} \text{average number of bits} &= - \frac{1}{2} \log_2 \bigg( \frac{1}{2} \bigg) - \frac{1}{4} \log_2 \bigg( \frac{1}{4} \bigg) - \frac{1}{4} \log_2 \bigg( \frac{1}{4} \bigg) \\ &= \frac{1}{2} \log_2 2 + \frac{1}{4} \log_2 4 + \frac{1}{4} \log_2 4 \\ &= \frac{1}{2} + 2 \frac{1}{4} + 2 \frac{1}{4} \\ &= 1.5. \end{aligned}$$

(This is just the expected value of the number of bits. If you didn't understand this step, check out my explanation about the expected value!)

Now we are almost there! Let's see the general case. Suppose that I pick between $x_1, x_2, \dots, x_n$ and I pick $x_k$ with probability $p_k$. Similarly, as before, the number of questions needed to find $\textstyle k$ is $\log_2 \frac{1}{p_k}$!

$$\begin{aligned} \text{number of bits needed to find } x_k &= \log_2 \bigg( \frac{1}{p_k} \bigg) \ &= - \log_2 p_k. \end{aligned}$$

The entropy of a probability distribution is simply the average bits of information needed to guess its elements successfully. You should feel proud now! We have tamed entropy.

$$H[x] = - \sum_{i=1}^{n} P(x_i) \log P(x_i)$$

A few additional comments!

1. You might wonder what happens when the logarithm of the probability is not an integer. Not all questions provide 100% new information. In some cases, the answer gives you information that is partially contained in other bits. Hence, the "amount of new information" is not always an integer.

2. Does the base of the logarithm matter? In general, we can easily swap the base of the logarithms:

$$\log_a x = \frac{\log_b x}{\log_b a}.$$

Thus, swapping bases in the entropy formula is just multiplication with a constant.

So, entropy is simpler than you thought! (And probably also simpler than what you were taught.)