A Beginner's Guide to Information Entropy

“The answers you get depend upon the questions you ask.” — Thomas Kuhn

Some problems are hard because of the immense resources they demand to be resolved. These problems, for a lack of a better phrase, can be thought of as economically hard. Given access to sufficient resources, such problems can be theoretically overcome. A great example is guessing passwords. Given access to sufficient compute power, brute-force methods can be used to crack these problems wide open.

Communication on the other hand can be categorized as being a fundamentally hard problem. Such problems are resource agnostic. Their solutions require something more. Thomas Kuhn referred to these as paradigm shifts: fundamentally different ways of approaching a problem that reveal insights previously unseen. Achieving these insights involves asking the right questions. And it was one such question that sparked the Information age.

Origins

Communication itself is nothing new. From gestures to languages, humans have developed increasingly complex methods of interacting with each other. But what makes communication different from other modes of interaction is the exchange of information. The ability to transfer information from one individual to another has served as the cornerstone of developing complex communities and societies.

George Boole, through his work on the algebra of sets, showed that notions of truth and falsehood could be mathematically encapsulated to form concrete reasoning, laying the foundation for propositional logic. This was followed by Kurt Gödel who successfully demonstrated that seemingly abstract qualitative thoughts could in fact be expressed within the bounds of formal systems.

As methods of expressing thought evolved, so did ways of communicating it. Morse code provided the first revolution of communication, allowing people to leverage electric signals to express information through codified signals. While effective, the method had a severe bottleneck when it came to the type of data it could transmit. In particular, the encoding and decoding processes were entirely manual, thus limiting the scope of information that could be sent through.

That’s when Claude Shannon came into the picture. After publishing what’s been called the greatest Master’s thesis of the 20th century at the age of 21, Shannon began thinking about the following question: how can a message selected at one point be reproduced exactly at another point? His quest towards answering this led to the birth of Information Theory and the world we live in today.

Developing the intuition

Shannon’s idea was simple. He had to find a way to quantify the notion of information. But how does one go about doing this? How does one assign a value to information? Consider the following two sentences:

$X$: Bell peppers are most commonly found in three colors: red, green, and yellow.

$Y$: My dog is hungry.

Let’s define the information present in an object $X$ as $I(X)$. One heuristic we could use to quantify the contained information could be size. The longer a sentence, the more information it’s likely to carry. If we define information as a monotonically increasing function of size, then since $\|X\| > \|Y\|$, it follows that $I(X) > I(Y)$.

But there’s a problem with the above method that’s actually shown in the example itself. Consider the following thought experiment. Pick a random person and ask them to read both of the above statements. Odds are they already know about the different colors of bell peppers. But what are the chances that they already know about you having a dog? Isn’t $Y$ a more meaningful statement to them since it’s improving their knowledge in some capacity?

This concept forms the basis of Shannon’s reformulation of the notion of information. Instead of viewing it as being a measure of size or some type of content specific heuristic, he defined information as the resolution of uncertainty. What’s fascinating is that while revolutionary, this insight is also one of the most natural ways of thinking about information: if it improves your knowledge, it’s probably worth more than something that doesn’t. This provides a smooth segue into quantifying information by looking at how much it improves certainty.

Understanding the math

We can rewrite the above relationship between an object $X$ and its information $I(X)$ as follows:

$$I(X) \propto X_c$$

where $X_c$ represents the factor by which $X$ reduces uncertainty. To quantify the information present in an object, we must somehow determine this $X_c$ quantity. A natural first step in this process is to define a unit of measurement for the thing we are trying to quantify. Shannon did the hard work and formalized the notion of a bit. At a high level, a bit can be thought of as the unit of information. Shannon used it to form a bridge between both sides of the above formula, linking information to certainty. He did this by defining a single bit as follows:

“The amount of information required to reduce uncertainty by a factor of 2.”

Don’t worry if this seems obscure right now. There’s an example coming up that details exactly how this definition fits into the intuition we developed above. The key idea to keep in mind is that based on that definition, we now have a new way of thinking about information almost like a physical quantity like mass or length.

Note: At first it may seem like if 1 bit improves certainty by a factor of 2, then 5 bits would improve certainty by a factor of $5 \times 2 = 10$. But note that the definition says factor of 2. This does not imply multiplicative scaling but rather exponential. Each additional bit improves the certainty provided by the previous one by another factor of 2. Thus 5 bits would improve certainty by a factor of $2^5 = 32$.

Now that we have a standard unit of measurement, we can proceed to determining the $X_c$ quantity. I’ll list the formula we’re trying to unpack below so you don’t have to scroll up.

$$I(X) \propto X_c$$

We can do so effectively using some basic principles from probability theory. Let’s understand this with an example.

Let’s consider the canonical probability experiment: a coin toss. Let $X$ be a random variable (r.v.) representing the two possible outcomes of the toss. We assume that the coin is unbiased, and so $X$ can be heads or tails with equal probability.

While the coin is in the air, the observer’s uncertainty about the outcome of the toss can be expressed in terms of the probability of each of the two outcomes. Since the coin is fair, we know that:

$$\begin{aligned} P(X = h) &= 0.5 \\ P(X = t) &= 0.5 \end{aligned}$$

This means that before the coin lands, the observer is only 50% certain about what the outcome will look like. Once the coin lands, that certainty instantly turns into 100% because they now have the exact knowledge of what the outcome is. The information the observer obtains from knowing that the coin landed on either heads or tails effectively improves their certainty by a factor of 2.

Plugging into the certainty formula, we get the following:

$$I(X = h) \propto 2$$

At this point you might wonder why I chose to write $I(X = h)$ instead of $I(X)$. The idea here is that information is measured specific to a given outcome. In our example, $X$ is an r.v. that can take on multiple values based on the multiple outcomes of the experiment (the coin toss). The above expression can be read as follows: the information obtained from observing the outcome of the coin toss as being heads is directly proportional to the factor by which that information improves the observer’s certainty. In this case, that factor is 2.

Note that the certainty factor $X_c$ was entirely dependent on the known probabilities of the outcomes. In this particular case, because both outcomes of heads or tails have equal probabilities, the certainty factor associated with each of those outcomes is also the same. However, this will not hold true for situations where different outcomes have different probabilities. We will see a more detailed example of this shortly.

Coming back to this expression:

$$I(X = h) \propto 2$$

We see that the left hand side (L.H.S) has information while the right hand side (R.H.S) contains certainty. We need a way of linking the two to remove the proportionality sign and replace it with a more helpful equality sign. Luckily, Shannon provided this bridge with his definition of a bit. We can reverse the process of exponentiation discussed earlier (since that was converting from bits to certainty), and replace it with taking the logarithm of the certainty with base 2.

$$I(X = h) = \log_2 2 = 1$$

And there we have it. The information contained within an outcome of a coin toss is 1 bit.

Key idea: We defined information as the resolution of uncertainty. The lower the probability of some outcome occurring, the more uncertainty we have about that outcome, and thus the more information we need to reduce that uncertainty.

On the other hand, events that occur with a high probability are more obvious, and thus don’t have as much uncertainty associated with them, thus requiring lesser information to communicate. This points to the idea that information is inversely proportional to the probability of an event.

Entropy

The above example provided us with a mechanism for determining the information present in a particular outcome of an r.v. One such variable can have several different outcomes, each containing a different amount of information. We can then ask the following question: on average, how much information does an r.v. contain?

The first method that comes to mind is simply taking the information present within each of the outcomes of a r.v. and adding them all up. This seems reasonable but keep in mind that the resulting quantity wouldn’t be very meaningful since it discounts two key facts:

1. We want the average information and not the total information. The latter quantity is of no use to us since it is impossible for an r.v. to assume the value of every single one of its outcomes at the same time.
2. Different outcomes have different probabilities. Adding them all up without accounting for that ignores the varying likelihoods of actually obtaining different information states.

The fix is to use a weighted sum, using the probabilities of obtaining those events as the weights.

Let $X$ be an r.v. representing the information present in a series of different outcomes. Let $P(X_x)$ be the probability of the r.v. $X$ taking on a particular outcome $x$. Let $H(X)$ represent the weighted sum. Using the coin toss example gives us:

$$\begin{aligned} P(X_{\text{heads}}) &= 0.5 & I(X_{\text{heads}}) &= 1 \\ P(X_{\text{tails}}) &= 0.5 & I(X_{\text{tails}}) &= 1 \end{aligned}$$

The weighted sum would then be as follows:

$$\begin{aligned} H(X) &= P(X_{\text{heads}}) \cdot I(X_{\text{heads}}) + P(X_{\text{tails}}) \cdot I(X_{\text{tails}}) \\ &\Rightarrow 0.5 \cdot 1 + 0.5 \cdot 1 = 1 \end{aligned}$$

This quantity $H(X)$ is referred to as the entropy of a r.v. $X$. It is simply a measure of the average amount of information present in a series of outcomes.

More complex example

The coin toss example is a great starting point, but it’s rather simplistic in that the outcomes we’re talking about have an equal probability of occurring. The next step in the process of understanding entropy is to generalize to various situations where outcomes may occur with varying probabilities.

Consider two individuals, Alice and Bob. Alice lives in a city where it rains 5 out of 7 days in a week, and it’s sunny the other 2 days. Bob on the other hand lives on the other side of the country in a town where the weather is rainy for 3 out of 7 days, cloudy for another 2 out of 7 days, and sunny 2 out of 7 days.

Let $A$ be the random variable representing the weather in Alice’s city, and let $B$ represent the same for Bob’s city. We can express their probability tables below:

R.V.	P(Rainy)	P(Cloudy)	P(Sunny)
A	5/7 ≈ 0.71	—	2/7 ≈ 0.29
B	3/7 ≈ 0.44	2/7 ≈ 0.28	2/7 ≈ 0.28

Let $A_I$ be a random variable representing the information in each of the outcomes in Alice’s city. Let $B_I$ represent the same for Bob’s city:

R.V.	I(Rainy)	I(Cloudy)	I(Sunny)
AI	0.49	—	1.79
BI	1.18	1.84	1.84

We can now take the expected value of each of the random variables, thus obtaining the entropy for each of them.

$$\begin{aligned} H(A_I) &= 0.71 \cdot 0.49 + 0.29 \cdot 1.79 = 0.867 \\ H(B_I) &= 0.44 \cdot 1.18 + 0.28 \cdot 1.84 + 0.28 \cdot 1.84 = 1.549 \end{aligned}$$

The above can be interpreted as follows. To communicate information regarding the weather in Bob’s city takes on average 1.549 bits of information. To do the same in Alice’s city requires on average 0.867 bits of information. This makes intuitive sense following our link between information and how surprising an event is. Alice’s city’s weather distribution is heavily skewed towards rain, so the weather is quite predictable. On the other hand, Bob’s city sees a lot more variation in its weather patterns, thus making each outcome more surprising to encounter.

Based on these examples and the initial intuition, we can now construct a simple formal definition of the entropy equation. We know that entropy is a measure of the expected value of information present across several events $X_i$.

$$H(X) = \sum_i P(X_i) \cdot I(X_i)$$

But we also know that $I(X_i)$ can be expressed in terms of $P(X_i)$ via the logarithmic connect that we derived earlier. Thus the final entropy equation becomes:

$$H(X) = -\sum_i P(X_i) \cdot \log_2 P(X_i)$$

Why?

Shannon’s formulation of entropy propelled his theory of information to new heights. He was able to show that the entropy of a particular event is actually the minimum number of bits you need to communicate information about that event. This statement allowed for the birth of modern compression techniques. The idea was simple: the entropy of an event was providing a limit to how far one could compress information about that event without worrying about suffering losses in the data transmission process.

If you’re interested in how the idea of information redundancy ties into concepts like compression, keep a lookout for my upcoming series of posts diving into the intuition behind how compression works, and explorations of a few techniques (containing examples in code).

Something extra

The statistical interpretation of entropy was heavily influenced by its counterpart in thermodynamics. I’ve found that understanding the parallels these concepts hold in nature is quite useful in being able to appreciate the underlying beauty of a seemingly abstract idea. I’m writing a mini-blog post about it which should be up here soon, so check back in if interested!