Information Entropy

[A shorter introduction without the mathematics: Concept of Information Entropy.]

1. Information and Uncertainty
Consider the case of one of the two boxes shown in Fig. 1 below, containing a ball in it. You are asked to find in which box the ball is by asking me questions. I will answer only with a ‘yes’ or a ‘no’.

Figure 1

Now, before you ask any question to me, you don’t know which box contains the ball. In other words, you are uncertain and have no information about the system to decide on the correct answer of which box contains the ball. Once you ask questions and receive answers – in this case, one is enough – you gain information and are no more uncertain in making your decision. This implies that the decision that has to be made by you between the two boxes will depend on some logic and is not random guess work.

We could conclude that in view of such a decision making process, Uncertainty decrease leads to Information increase. We shall see in subsequent sections that Information and Uncertainty can be treated as quantities with numerical values and used to describe the efficiency of decision making processes, whether such processes are similar to the ball in the box example in Fig. 1 or picking out a ‘set of symbols’ from a relatively large sequence of symbols, as done in communication engineering.

2. The Real Bit
To quantify and measure Uncertainty we need to introduce the concept of the ‘real’ bit. A bit is defined as the amount of Information necessary to decide between two equal choices. As we will see later, unlike in computer parlance, the concept of a bit here can be associated with real numbers.

In the Ball and Box example in Fig. 1 with two boxes, you have to ask at least one question to decide on the correct choice of box. In other words, you require one bit of information to decide between two choices. Similarly, in the example of four boxes and a ball shown in Figure 2 below, for the presence of the ball in any of the boxes being equally likely, you require at least two bits of information. That is, you can be sure of the correct answer of which box the ball is only after at least two questions.

Figure 2

In another way, we can say that the Uncertainty of which box contains the ball is two bits before any question is asked by you and reduces to zero once the answer is known. By taking into account all possible eventualities, the number of bits provides the optimal number of questions that leads to the answer.

Extending the example, for 8 equally likely events of boxes containing the ball, we should require at least 3 bits of Information to make a choice (decision). Correspondingly, the Uncertainty of the system is 3 bits before any question is asked and reduces to zero, once the answer is known. This process of reduction in Uncertainty is accompanied by a gain in Information, that is, from zero knowledge of which box has the ball to the case of complete knowledge of which box has the ball.

Putting this into a mathematical framework, we can write

$2^{b} = M \dots (1)$

or upon rearrangement

$b = lo g_{2} (M) \dots (2)$

where, b is the number of bits required to determine which of the M different boxes has the ball in it. The number 2 arises because each yes-or-no answer halves the number of boxes that remain possible. If, for instance, the ball is slightly magnetized and one of the boxes is made of iron, then the boxes are no longer equally likely, and Eq. (2) no longer applies.

We shall proceed now to generalize the concepts to include such situations. We pick a new example now which is useful in communication engineering and coding theory.

Consider a sequence comprising of M different symbols and N total number of symbols. These symbols can be alphabets of a particular language (say, English) such that the sequence of letters could form a meaningful word or not. These M different symbols are attributed with different probabilities of occurrence $P_{i}$ where i denotes which symbol is being referred to.

For example, the sequence baabbcac has N = 8 total number of symbols (counting each of the letters) and M = 3 total number of different symbols (a, b and c). Unlike the earlier boxes and a ball example, here the probability of occurrence for each symbol (a or b or c) in the sequence can be different.

Rearranging Eq. (2) as

$b = - lo g_{2} \frac{1}{M} \dots (3)$

we can see that for the particular case of M equally probable symbols (or boxes in the earlier example) 1/M is the probability of occurrence of each symbol (or the ball to reside in any one particular box). Substituting 1/M as P in Eq. (3), this implies

$b = - lo g_{2} (P) \dots (4)$

For instance, in the case of Figure 2, there are 4 equally likely boxes in which the ball could have resided and so M = 4 and so P = 1/4. This leads to b = 2 from Eq. (4), which we concluded earlier. Also, it is clear from the nature of Eq. (4) that the bit b could be a real number.

3. Surprisal and Uncertainty

Whether it is the occurrence of a sequence in a particular way or the residence of a ball in a set of boxes, we know that the sum of all the probabilities is always one. This means, we cannot cheat. In the sequence given in the example in section 2, symbols that are not part of the original set of considered symbols will not appear. Analogously, in Figure 2, the ball will not reside in a fifth box that is not in our list of (four) boxes.

This seemingly obvious observation has significance in that it is used to define a concept called the surprisal of any event or symbol. It is defined as

$u_{i} = - lo g_{2} (P_{i}) \dots (5)$

Note also that Eq. (5) is similar in form to Eq. (4). If the probability of occurrence P of an event or symbol in a sequence is low, its surprisal u will be high. The occurrence of that low probable event or the appearance of that symbol in that particular location of the sequence will ‘surprise’ us. If the probability of occurrence is zero, we are totally surprised by the occurrence of that symbol, which is not in the original set of considered symbols.

Let us tie this concept of surprisal with Uncertainty (H, measured as b, bits per symbol), from our earlier discussion in section 1. We observe that Uncertainty before we receive a symbol (or before we see the box with the ball) is the same, irrespective of what symbol we receive. This is because the symbol that we don’t have cannot change our Uncertainty. It cannot increase our surprisal either. Therefore, Uncertainty H can be defined as the average of surprisal for all the N existing symbols

$H = \frac{u _{1} + u _{2} + \dots + u _{N}}{N} \dots (6)$

Using the summation notation, and accounting for the multiple appearances of any symbol, we can rewrite Eq. (6) as

$H = \sum_{i = 1}^{M} \frac{N _{i}}{N} u_{i} \dots (7)$

where $N_{i}$ is the number of appearances of the i th symbol.

Since $F_{i}$ , the frequency of the i th symbol occurring, is found by dividing $N_{i}$ , the number of times the particular symbol occurs by N, the number of symbols, we can further rewrite Eq. (7) as

$H = \sum_{i = 1}^{M} F_{i} u_{i} \dots (8)$

Also, we can see that the probability of occurrence of a symbol in a sequence $P_{i}$ used in Eq. (5) can also be written as

$P_{i} = lim_{N \to \infty} F_{i} \dots (9)$

This suggests that for $N \to \infty$ , substituting Eq. (9) in Eq. (8) leads to,

$H = \sum_{i = 1}^{M} P_{i} u_{i} \dots (10)$

Substituting for $u_{i}$ from Eq. (5) in Eq. (10), we arrive at

$H = - \sum_{i = 1}^{M} P_{i} lo g_{2} P_{i} \dots (11)$

Equation 11 is Shannon’s formula for Uncertainty (H), measured in bits per symbol.

Observe that the form of Eq. (11) for Uncertainty has a striking similarity to S = k log W, the concept of Thermodynamic Entropy introduced by Ludwig Boltzmann. The story goes (explained in reference [1]) that Shannon, after having described his concept in mathematical form, asked his friend John von Neumann what to call it, and von Neumann asked him to call it entropy, as nobody is sure of what it is and he (Shannon) would always have the advantage in any debate over his theory. So Shannon named it Information Entropy, although he also used the term Uncertainty to denote the same idea in his paper (see reference [2] for a related discussion).

Calling this Uncertainty H as Information Entropy (measured in bits per symbol) has also led to confusions because of wrong comparisons with and interpretations as the Thermodynamic Entropy (measured in Joules per Kelvin).

The nature of this H function for two symbols is shown in the figure below. Notice that the curve is symmetrical, and rises to a maximum of one bit when the two symbols are equally likely (probability = 0.5). It falls towards zero whenever one of the symbols becomes dominant at the expense of the other symbol.

Figure 3

4. From Uncertainty to Information

We saw in section 1 that a decrease in Uncertainty should increase Information. Let us put this also in a mathematical framework. Let us consider the example of the sequence baabbcac

According to the explanations in section 2, in the above sequence we have N = 8; M = 3; N(a)=3; N(b)=3 and N(c)=2

This implies the frequency of occurrence of ‘a’ is F(a) = 0.375. Likewise, F(b) = 0.375 and F(c) = 0.25. Using Eq. (5) we can deduce the surprisal of occurrence for symbol ‘a’ as u(a) = 1.415. Likewise, u(b) = 1.415 and u(c) = 2.000. Substituting in Eq. (10) we arrive at H = 1.5613 bits/symbol for a source that produces a, b and c with these frequencies.

Had all M = 3 symbols been equally likely, the Uncertainty would be the largest possible for three symbols, $H_{ma x} = lo g_{2} 3 = 1.585$ bits/symbol, from Eq. (2). The difference

$H_{ma x} - H = 1.585 - 1.5613 = 0.024 bits/symbol \dots (12)$

is the redundancy of the source: how far its symbol frequencies are from all being equal. (Shannon expressed it as a fraction, $1 - H / H_{ma x}$ .) The larger the redundancy, the more predictable the sequence. Here the frequencies are nearly equal, so the redundancy is small.

How much Information does the receiver gain? Following section 1, Information is the decrease in Uncertainty,

$R = H (b e f ore) - H (a f t er) \dots (13)$

If the channel is noiseless, once a symbol has arrived there is no Uncertainty left about it, so H(after) = 0 and R = H(before). A receiver who knows the source’s frequencies gains 1.5613 bits for each symbol. A receiver who knows only that a, b or c may come, each equally likely, gains 1.585 bits. This is the boxes and a ball case again: for eight boxes and a ball, before the ball is located there is an Uncertainty of 3 bits; after it has been located, it becomes 0 bits. Since Uncertainty has gone from 3 to 0, we gained 3 bits of Information. (If the channel is noisy, H(after) is not zero, and the information received is correspondingly less.)

The calculation of $H_{ma x}$ above assumes the sequence can contain only a, b and c (M = 3). If we allow any letter of the English alphabet to appear, then M = 26 and $H_{ma x} = lo g_{2} 26 = 4.700$ bits/symbol, while H = 1.5613 remains the same for the same source. The redundancy measured against the full alphabet is then

$H_{ma x} - H = 4.700 - 1.5613 = 3.139 bits/symbol \dots (14)$

A source that uses only three of the 26 letters is highly predictable. Conversely, a receiver that expects any of the 26 letters, each equally likely, has more Uncertainty before each symbol arrives (4.7 bits instead of 1.585), and so gains more Information when it arrives. When the pool is restricted to a, b and c, the sequence can be “guessed” more correctly, and less is learnt from receiving it.

5. Conclusions

Information Entropy or Shannon Entropy is a concept that is used primarily in communication engineering and coding theory. Since the 1990s it has also been used in bioinformatics and DNA sequence analysis, where protein binding sites are described using information theory and sequence logos [6]. It is also the quantity that today’s AI language models are trained to minimise, as the next section explains.

6. Addendum (2026): An AI named Claude

In 2026 I asked an AI assistant, Claude, why it was named so. Anthropic, its maker, has not formally explained the name, but it is widely taken as a nod to Claude Shannon. The nod is apt. A large language model is, at its core, a machine that assigns probabilities $P_{i}$ to the next symbol (a “token”: a word or part of a word), given the symbols before it. It is trained to make its average surprisal (Eq. 5, averaged as in Eq. 10, with the model’s probabilities scored against real human text) as small as possible. This quantity is called cross-entropy. A model that is seldom surprised by human writing has, in Shannon’s sense, learnt a good deal about it.

Shannon anticipated the game. In his 1948 paper [7] he built successively better approximations to English by picking letters, and then words, according to their measured frequencies. In 1951 [8] he had people guess the next letter of a text, and estimated that printed English carries only about one bit per letter. That is far below the $lo g_{2} 27 \approx 4.75$ bits it would carry if all letters and the space were equally likely. The gap is the redundancy of language (Eq. 12), and that redundancy is what makes prediction, and hence such models, possible.

So when the assistant answered my question, it was quite literally choosing each word to keep my surprisal low. Its namesake would have approved of the efficiency, if not the verbosity.

References

[1] Myron Tribus and Edward C. McIrvine, Energy and Information, Scientific American, vol. 225, no. 3, pp. 179–188, Sep. 1971

[2] For more clarification, see the excellent page by Dr. Thomas D. Schneider, Information Is Not Entropy, Information Is Not Uncertainty!

[3] Cosma Shalizi’s notebook on Information Theory collects and recommends many useful books and reliable web resources on this topic

[4] Some more from Cosma Shalizi on Ergodic Theory and Estimating Entropies and Information

[5] John Hawks, Information theory: a short introduction (2008): notes on Information Entropy and how to use it in anthropology

[6] T. D. Schneider and R. M. Stephens, Sequence logos: a new way to display consensus sequences, Nucleic Acids Research, vol. 18, pp. 6097–6100, 1990

[7] C. E. Shannon, A Mathematical Theory of Communication, Bell System Technical Journal, vol. 27, pp. 379–423 and 623–656, 1948

[8] C. E. Shannon, Prediction and Entropy of Printed English, Bell System Technical Journal, vol. 30, pp. 50–64, 1951

Arunn Narasimhan

Explorer

Information Entropy

Backlinks