Entropy: An Introduction

As the first digital computers were being invented in the 1940s and researchers like Alan Turing were formalizing their capabilities, the scientific and engineering communities needed a way to quantify previous intuitive notions of information and communication . In 1948 Claude Shannon, during a stint at Bell Labs (also the birthplace of the transistor and Unix operating systems, among other major achievements in computer science) provided the first comprehensive framework to do so in his landmark paper A Mathematical Theory of Communication . With the tools provided by this theory (now known as Information Theory ), we can answer important questions about the limits of modern computers like: How can we store information (say, a file on our hard drive) in the most efficient way? Or, how do we successfully communicate information (say, a text message) over a channel (e.g., our cell network) that may not be 100% reliable?

We’ve provided a couple examples of “information” in the abstract sense, but how can we define information in a formal, precise way? We’ll start with an example. Let’s say the city of Seattle has decided to introduce a new service, whereby every morning each resident gets a text message with the day’s weather forecast. If it’s wintertime, where the weather is overcast ~100% of the time, sending the text is redundant; a resident will always be correct if they have basic knowledge of the city’s weather patterns and assume that every day will be overcast. In other words, the forecast won’t provide any new information for city residents , since there’s no uncertainty in the outcome.

Now, suppose instead we’re in a different season with multiple possibilities for the day’s weather. In this case our service will actually be useful - residents no longer can just assume that the weather will be overcast every day and be correct 100% of the time. Just how useful is a given forecast? Suppose we’re in the summer, and the weather (optimistically) is sunny 75% of the time and overcast 25% of the time. In this case, a resident would be correct on most days if they naively assumed the day’s weather would be sunny, and a forecast of a sunny day thus doesn’t provide much new information as compared to the naive baseline. Correspondingly, due to their relative rarity, a forecast indicating a cloudy day would be much more informative, as the naive prediction would be incorrect in this case.

From the previous example we see that the information transmitted when communicating the outcome of an event is intimately related to frequency of that outcome. With this idea in mind, we introduce our first concept in information theory, self-information .

Let’s say we have some discrete random variable $X \sim p(x)$ p ( x ) taking on a set of potential values $x \in \mathcal{X}$ X with a corresponding probability mass function $p(x)$ p ( x ) . We then define

The self-information (sometimes known as "surprisal" ) of an outcome $x \in \mathcal{X}$ X is defined as $I(x) = \frac{1}{\log p(x)} = -\log p(x)$ I ( x ) = lo g p ( x ) 1 ​ = − lo g p ( x )

We usually take the $\log$ lo g in the above definition to be base 2, so self-information is measured in bits . At a first glance our definition of $I(x)$ I ( x ) may seem arbitrary, but we can see that it captures the ideas we had in our thought experiment earlier, along with some other nice properties. As $p(x) \to 1$ p ( x ) → 1 , we have that $I(x) \to 0$ I ( x ) → 0 . This aligns with our intuition that information about an event is only transferred from a source to a recipient if the recipient was not already aware of that event’s outcome. Similarly, as $p(x) \to 0$ p ( x ) → 0 , we have that $I(x) \to \infty$ I ( x ) → ∞ , reflecting that the communication of a rare outcome is more informative than a common one.

Finally, suppose we wish to communicate the outcomes of two independent events $X_1, X_2 \stackrel{\text{i.i.d.}}{\sim} p(x)$ X 1 ​ , X 2 ​ ∼ i.i.d. p ( x ) . Since the outcomes of $X_1$ X 1 ​ and $X_2$ X 2 ​ are independent of each other, we’d expect that a compound message containing both outcomes would convey an amount of information equal to the sum of sending two messages containing each outcome individually. The self-information satisfies this property too, since for some joint outcome $(x_1, x_2) \in \mathcal{X} \times \mathcal{X}$ ( x 1 ​ , x 2 ​ ) ∈ X we have

$\begin{aligned} I(x_1, x_2) &=-\log p(x_1, x_2)\\ &= -\log\big(p(x_1)p(x_2)\big)\\ &= -[\log p(x_1) + \log p(x_2)]\\ &= I(x_1) + I(x_2) \end{aligned}$ I ( x 1 ​ , x 2 ​ ) ​ = − lo g p ( x 1 ​ , x 2 ​ ) = − lo g ( p ( x 1 ​ ) p ( x 2 ​ ) ) = − [ lo g p ( x 1 ​ ) + lo g p ( x 2 ​ ) ] = I ( x 1 ​ ) + I ( x 2 ​ ) ​

which matches from what we’d expect of a measure of information.

Now, suppose out outcome isn’t known ahead of time, but we still want a sense of how much information we’ll be transmitting. One simple way to do this is to weight the self-information $I(x)$ I ( x ) of each outcome by the probability of that outcome $p(x)$ p ( x ) . This gives us our second major concept in information theory, entropy

The entropy $H(X)$ H ( X ) of a random variable $X$ X is defined as $H(X) = \sum_{x \in \mathcal{X}}p(x)I(x) = -\sum_{x \in \mathcal{X}}p(x)\log p(x)$ H ( X ) = x ∈ X ∑ ​ p ( x ) I ( x ) = − x ∈ X ∑ ​ p ( x ) lo g p ( x )

By convention we assign a value of $0$ 0 to $p(x)\log p(x)$ p ( x ) lo g p ( x ) when $x = 0$ 0 , even though technically $0\log 0$ 0 lo g 0 is undefined. We can justify this by continuity, as it can be shown $x \log x \to 0$ x lo g x → 0 as $x \to 0^{+}$ 0 + .This too aligns with our intuition - an outcome with no chance of occuring doesn’t have any effect on the variability of our event $X$ X .

Entropy is quite possibly the “fundamental unit” of information theory, and it’ll continue coming up in all kinds of interesting ways. We can think of $H(X)$ H ( X ) as quantifying how much we’ll be “surprised” by the outcome of $X$ X on average. An example will help illustrate this idea

Let $X \sim Bern(p)$ B e r n ( p ) . In other words, we have $X = \begin{cases} 1 & \text{with probability $p$} \\ 0 & \text{with probability $1-p$} \end{cases}$ { 1 0 ​ with probability  p with probability 1 − p ​

Plugging in to our formula for entropy, we have

$H(X) = -p\log p - (1 - p)\log(1-p)$ H ( X ) = − p lo g p − ( 1 − p ) lo g ( 1 − p )

To build up our intuition we can visualize our entropy for different values of $p$ p in the following graph (where we let $H(p)$ H ( p ) denote $H(X)$ H ( X ) as a function of $p$ p )

Figure 1. Entropy of $X \sim Bern(p)$ B e r n ( p ) as a function of $p$ p (mouse over to see precise values). Note that $H(p)$ H ( p ) is maximized when $p = 1/2$ 1 / 2 (maximum variability in the outcome) and minimized when $p = 0$ 0 or $p = 1$ 1 (no variability in the outcome).

As we would expect, $H(X)$ H ( X ) is 0 when $X$ X is deterministic ( $p = 0$ 0 or $p = 1$ 1 ) as there’s no potential for surprise in such cases. On the other hand, it’s maximized when $p = 1/2$ 1 / 2 when the variability in outcomes is greatest. We’ll work through another more complicated example before moving on.

Let $X \sim Geom(p)$ G e o m ( p ) . In other words, the probability that we need $k$ k Bernoulli trials before reaching our first 1 is (letting $q = 1 - p$ ) $P(X = k) = q^{k-1}p$ P ( X = k ) = q k − 1 p

Plugging into our formula for entropy we have

$\begin{aligned} H(X) &= -\sum_{k=1}^{\infty}q^{k-1}p\cdot \log\big(q^{k-1}p\big) \\ &= -\bigg[\sum_{k=1}^{\infty}pq^{k-1}\log p + \sum_{k=1}^{\infty}pq^{k-1}\log q\bigg]\\ &= -\bigg[\sum_{k=0}^{\infty}pq^{k}\log p + \sum_{k=0}^{\infty}pq^{k}\log q\bigg] \end{aligned}$ ​ = − k = 1 ∑ ∞ ​ q k − 1 p ⋅ lo g ( q k − 1 p ) = − [ k = 1 ∑ ∞ ​ p q k − 1 lo g p + k = 1 ∑ ∞ ​ p q k − 1 lo g q ] = − [ k = 0 ∑ ∞ ​ p q k lo g p + k = 0 ∑ ∞ ​ p q k lo g q ] ​

From calculus, we know that $\sum_{n=0}^{\infty}r^{n} = \frac{1}{1-r}$ ∑ n = 0 ∞ ​ r n = and $\sum_{n=0}^{\infty}nr^{n} = \frac{r}{(1-r)^2}$ ∑ n = 0 ∞ ​ n r n = ( 1 − r ) 2 r ​ for any real number $r$ r with $|r| < 1$ ∣ r ∣ < 1 . This gives us

$\begin{aligned} H(X) &= -\bigg[\frac{p\log p}{1 - q} + \frac{pq\log q}{p^2}\bigg] \\ &= -\bigg[\frac{p\log p + q\log q}{p}\bigg]\\ &= -\bigg[\frac{p\log p + (1-p)\log (1-p)}{p}\bigg]\\ \end{aligned}$ ​ = − [ 1 − q p lo g p ​ + p 2 p q lo g q ​ ] = − [ p p lo g p + q lo g q ​ ] = − [ p p lo g p + ( 1 − p ) lo g ( 1 − p ) ​ ] ​

If we let $Y \sim Bern(p)$ B e r n ( p ) , this further simplifies to

$\begin{aligned} H(X) &= \frac{H(Y)}{p} \end{aligned}$ H ( X ) ​ = ​

and we visualize our entropy for for different values of $p$ p below:

Figure 2. Entropy of $X \sim Geom(p)$ G e o m ( p ) as a function of $p$ p . Note that $H(p) \to 0$ H ( p ) → 0 as $p \to 1$ 1 and $H(p) \to \infty$ H ( p ) → ∞ as $p \to 0$ 0 . This should agree with our intuition; with a high chance of success we'd expect our process to end quickly. On the other hand, with a lower chance of success we have a much fatter tail with a higher variability of outcomes.

As we might expect, $H(p) \to 0$ H ( p ) → 0 as $p \to 1$ 1 since there’s less variability in the number of trials we need until our first success. On the other hand $H(p) \to \infty$ H ( p ) → ∞ as $p \to 0$ 0 , which reflects the fact that it’s much harder to predict the number of trials required to reach a success as the probability of success is lowered.

One immediate consequence of the definition of entropy is the following:

$H(X) \geq 0$ H ( X ) ≥ 0

Proof:

Going back to our definition of entropy:

$H(X) = -\sum_{x \in \mathcal{X}}p(x)\log p(x)$ H ( X ) = − x ∈ X ∑ ​ p ( x ) lo g p ( x )

Since our $p(x)$ p ( x ) terms are probabilities, we must have $0 \leq p(x) \leq 1$ p ( x ) ≤ 1 . Since $\log x \leq 0$ lo g x ≤ 0 for $0 < x \leq 1$ , so we must have $\sum_{x \in \mathcal{X}}p(x)\log p(x) \leq 0$ ∑ x ∈ X ​ p ( x ) lo g p ( x ) ≤ 0 . Multiplying by the negative sign in the definition of $H(X)$ H ( X ) then completes the proof. $\square$ □

This fact will prove very useful as we proceed in the course, so it’s good to commit to memory now.

The reader may have noticed that our definition of entropy is nearly identical to that of the expected value of a random variable, differing only in the presence of the $\log$ lo g function. This begs the question - can we reconcile these two concepts? First, as a reminder we define expected value as

The expected value $E[X]$ E [ X ] of a discrete random variable $X \sim p(x)$ p ( x ) is $E[X] = \sum_{x \in \mathcal{X}} p(x)\cdot x$ E [ X ] = x ∈ X ∑ ​ p ( x ) ⋅ x

Now, suppose we apply some deterministic function $g$ g to our random variable $X$ X - this gives us a new random variable $g(X)$ g ( X ) . Since the randomness in $g(X)$ g ( X ) is entirely due to the randomness in $X$ X , intuitively we should be able to compute $Eg(X)$ E g ( X ) using $X$ X ’s distribution $p(x)$ p ( x ) without needing to compute $g(X)$ g ( X ) ’s distribution. It turns out that our intuition here is correct; this is a well-known result in probability theory that is used enough to have its own name

For a discrete random varible $X \sim p(x)$ p ( x ) and function $g\colon \mathbb{R} \to \mathbb{R}$ g : R → R $E[g(X)] = \sum_{x \in \mathcal{X}} p(x)\cdot g(x)$ E [ g ( X ) ] = x ∈ X ∑ ​ p ( x ) ⋅ g ( x )

Despite the intuitive nature of this theorem, proving it requires some work which we omit here and leave as an exercise for the reader.Setting $g(X) = -\log p(X)$ g ( X ) = − lo g p ( X ) and using LOTUS we then have

$H(X) = E[-\log p(X)] = E[I(X)]$ H ( X ) = E [ − lo g p ( X ) ] = E [ I ( X ) ]

which allows us to formally justify our notion of entropy as the average amount of information contained in the outcome of a random varible.

We’ll go over one final example before concluding these notes. Suppose we want to communicate the outcome of an event represented by a random variable $X$ X . Ideally (to save money, power, etc.) we’d like to do so with as short a message as possible on average. Naturallly, our encoding scheme should use fewer bits to represent high-probability events and more bits to encode low probability ones. It turns out (we’ll prove this later), any coding scheme for this problem requires at least $I(X)$ I ( X ) bits on average to send our message without corrupting its contents. In other words, $H(X) = E[I(X)]$ H ( X ) = E [ I ( X ) ] provides a lower bound on the average number of bits required to guarantee that our message will be transmitted successfully. While we won’t have the tools to prove this until later, a simple example will help illustrate this idea

Let $X = \begin{cases} a & \text{with probability 1/2} \\ b & \text{with probability 1/4} \\ c & \text{with probability 1/8} \\ d & \text{with probability 1/8} \end{cases}$ ⎩ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎧ ​ a b c d ​ with probability 1/2 with probability 1/4 with probability 1/8 with probability 1/8 ​

How could we devise a code to transmit the outcome of $X$ X in this case? One possible scheme is as follows: If $X = a$ a , we send a 1 and end transmission, otherwise we send a 0 and continue. Similarly, if $X = b$ b , we then send a 1 and stop, otherwise we send another 0. Finally, if $X = c$ c we send a 1 and stop, otherwise we send a 0 and stop. Under this scheme, we send a total of 1 bit half the time, 2 bits 1/4 of the time, and 3 bits 1/4 of the time, giving us a total of 1.75 bits on average.

Figure 3. Visual representation of our probability space. At each step of our encoding algorithm, we eliminate half of the space that still remains.

Each time we ask our “questions” in this scheme, we’re eliminating half of the remaining probability space. This is very similar to the way that binary search eliminates half the possible solution space at each step of the algorithm. Moreover, just as binary search is an optimal algorithm (i.e., takes the fewest number of steps possible to still guarantee a correct answer), we would expect our encoding scheme to be optimal for $X$ X .

We can verify this intuition by plugging into our formula for entropy

$H(X) = -\frac{1}{2}\log\frac{1}{2}-\frac{1}{4}\log\frac{1}{4}-\frac{1}{8}\log\frac{1}{8}-\frac{1}{8}\log\frac{1}{8} = 1.75 \text{ bits}$ H ( X ) = − lo g − lo g − lo g − lo g = 1 . 7 5  bits

Since our average number of bits needed to encode the outcome of $X$ X can’t be less than $H(X)$ H ( X ) , our proposed scheme is indeed optimal.

Footnotes: