Information, Entropy, Relative Entropy, and Mutual Information

History

In the early 20th century, laying copper wires and building radio infrastructure was very expensive, and physical bandwidth (range of frequencies a wire could reliably carry) was a strictly finite resource. Telecom companies needed to maximize their return on investment, so engineers had to figure out how much “payload” (actually useful bits) these lines were truly carrying, instead of just measuring electrical pulses.

People were designing different physical systems to transmit information (like a simple on-off based Morse code system, or a decoder for 10 different voltage levels), and they needed way to compare these systems to find out which one had the maximum throughput while minimizing physical costs.

The physical wire worked exactly the same whether it was transmitting speech or a string of random numbers, so we couldn’t use human semantics (like abbreviations) to design a system. The natural next idea was to base it on the likelihood of the symbols used.

Hartley (1928) said: if a source emits $n$ symbols from an alphabet of size $D$, there are $D^n$ possible messages. But since cost and time scale linearly with message length, we would like our information measure to do so too, so the amount of information transferred is better represented as $n \log D$ (taking the log of $D^n$).

This measure assumed every symbol is equally likely, but real sources like English are not, there are many more e’s than z’s (or in the Hartley example, 00 is probably more likely than 73), and you could design schemes to take advantage of these asymmetries in the $D^n$ possibilities using the statistical structure.

Shannon (1948) exploited this by making information a function of the probability of symbols instead of alphabet size.

Information (surprise)

Setup: Let $X$ be a discrete random variable mapping a physical action (like pressing a telegraph key) to a specific symbol $x$ in an alphabet (26 letters of English + space + punctuation). Its likelihood is given by the probability mass function $p(x)$.

Motivation: Because physical wires ignore human semantics, every symbol’s “information” depends on how predictable it is, expected symbols (like E at $p(E) = 12\%$) carry less information than rare symbols (like Z at $p(Z) = 0.01\%$). To quantify this, we define $h$ as the measure of the “surprise”, or information, contained in a single event such as seeing the letter E.

The three conditions we need on $h$

1. Additivity on independent events: $h(pq) = h(p) + h(q)$ for all $p, q \in (0,1]$. Learning two unrelated facts should yield the sum of their information. Without this there is no well-defined information rate per symbol, and a message of doubled length would not have doubled cost.
2. Monotonically decreasing in $p$: for $p \le q \Rightarrow h(p) \ge h(q)$. Being told a symbol you already knew in your shared prior must cost nothing, so $h(1) = 0$ (this also comes out of additivity, since $h(1 \cdot 1) = h(1) + h(1) \Rightarrow h(1) = 0$), and rarer outcomes are more informative.
3. Normalization: $h(1/2) = 1$. This is just to decide on a unit for information: observing an event with 50% probability (a fair coin flip) provides exactly 1 bit.

Where this goes next: We now have a measure for the information contained in a single keystroke. But while building a radio tower we care about the overall long-term behaviour of a message source, not a single keystroke, so we need a single number to represent the average information rate of the entire system. That is the average information over all keystrokes, using the expectation $\mathbb{E}$ from statistics:

$\mathbb{E}[h(X)] = \sum p(x)\, h(x)$

Substituting the $h(x)$ term we derived gives the expected surprise from the message source, fundamental enough to be given its own name: Entropy.

Entropy

Setup: Let $X$ be a discrete random variable mapping the event of a human pressing a telegraph machine key to one symbol $x$ in our alphabet $\mathcal{X}$, with pmf $p(x)$. This $X$ is the same one as for self-information, since the message source is just a machine that rolls the random variable $X$ over and over again ($X_1, X_2, X_3, \dots, X_n$).

Motivation: We want the expected surprise from any generic keystroke, so entropy ranges over the entire alphabet. This means that unlike self-information $h(p)$, which takes a single probability (a number between 0 and 1) and outputs the surprise of one specific symbol, entropy $H$ is a functional: it takes the entire probability distribution of the random variable and maps it to a single number representing the average surprise.

Properties

1. Non-negativity : $H(X) \ge 0$. You can never have negative entropy. Because every probability $p(x)$ is a fraction between 0 and 1, the fraction $\frac{1}{p(x)}$ is always 1 or greater. Equality holds only if the outcome is deterministic, the telegraph machine is broken and only prints E ($p(E) = 1.0$, and all other letters $p = 0$).
2. Maximum entropy bound : $H(X) \le \log_2 \lvert \mathcal{X} \rvert$. Entropy hits its absolute mathematical ceiling when every single symbol in the alphabet $\mathcal{X}$ is equally likely (a uniform distribution). If you have a 32-key telegraph machine and the operator presses keys completely at random, you have maximum uncertainty of $H_{\text{max}} = \log_2(32) = 5 \text{ bits}$. Any structure in a language would make it lower.

From one source to a channel: the pair $(X, Y)$

We now have a mathematical model for a single message source $X$. But a real communication system is not just one isolated source. It is connected to a copper wire with electrical interference, which terminates at a receiver. Because of this noise, the receiver experiences a new physical event (e.g. hearing a distorted click on the sounder).

flowchart LR
  O[Operator presses key] --> X["X: sent symbol, x in alphabet"]
  X -->|noisy copper wire| Y["Y: received symbol, y in alphabet"]
  Y --> T[Receiver's tape]

We define a new discrete random variable $Y$, which maps this received physical event to a symbol $y$ in the receiver’s alphabet $\mathcal{Y}$ (usually, but not always, the same 26-letter alphabet as the sender’s).

To evaluate the communication system as a whole, factoring in the source behaviour, the wire noise, and the receiver observation all at once, we can treat the sender’s input and the receiver’s output as a single combined physical event. This makes a single vector-valued random variable $(X, Y)$, mapping the dual physical event (the sender pressing a key and the receiver observing a click) to a pair of symbols $(x, y)$ in the combined alphabet $\mathcal{X} \times \mathcal{Y}$.

The statistical blueprint of this entire system is the joint probability mass function $p(x,y)$: the likelihood that the sender transmits $x$ AND the receiver simultaneously gets $y$, capturing both the sender’s vocabulary habits and the wire’s physical noise profile.

Joint entropy $H(X, Y)$

Motivation: Joint entropy measures the expected surprise of the entire end-to-end system.

Since we are treating the pair as a single, slightly more complex telegraph machine, we reuse the exact same expected-value framework we used for $H(X)$. The surprise of a specific pair $(x,y)$ occurring is simply $h(p(x,y)) = -\log_2 p(x,y)$. To find the average over both the sent and received alphabets, in code we would have to use a double summation to iterate through the grid:

def joint_entropy(p): # p[x][y] = P(X=x, Y=y)
    total = 0.0
    for i in range(len(p)):
        for j in range(len(p[i])):
            prob = p[i][j]
            if prob > 0: # the 0 log 0 = 0 convention
                total -= prob * log2(prob)
    return total

Where this goes next: Now suppose we want to isolate the effect of the noisy wire itself. One way is to freeze the sender’s variable, so that we know which symbol $X$ was transmitted, the uncertainty left over in the system is then about which symbol $Y$ pops out at the receiver’s end, based on wire noise only. In a perfect, noiseless wire, knowing $X$ means you perfectly know $Y$, so the leftover uncertainty is exactly 0 bits, but in a real wire there may be flips due to static.

Conditional entropy $H(Y \mid X)$

Like the other entropies, this is a functional too, but it operates on a different set of probabilities.

For any specific symbol such as the letter E, the entropy of the receiver’s outcomes, using the standard entropy formula, is:

$H(Y \mid X = x) = - \sum_{y \in \mathcal{Y}} p(y \mid x) \log_2 p(y \mid x)$

But since we cannot just look at E, we need to average this leftover uncertainty across every symbol the sender could possibly transmit, weighting each one by how often the sender actually transmits it, $p(x)$:

Chain rule of entropy (two variables)

Since joint entropy is for the sender and the wire system as a whole, and the individual components both have entropies we have discussed, there is a natural relation:

Symmetry of the chain rule

Because joint entropy $H(X,Y)$ looks at the whole system from the outside, it doesn’t matter which side you start on:

$H(X, Y) = H(Y) + H(X \mid Y)$

Consider the case where the sender $X$ uses a very complex, erratic language (high entropy, say 10 bits per symbol), but the receiver $Y$ is a broken machine that only prints two symbols, A or B (low entropy, max 1 bit per symbol). We would need:

$10 \text{ bits} + H(Y \mid X) = 1 \text{ bit} + H(X \mid Y)$

This makes sense from either direction:

With a third variable

The chain rule holds even if we add a third variable $Z$ to the system (which could be a secondary sensor monitoring the wire):

$H(X, Y \mid Z) = H(X \mid Z) + H(Y \mid X, Z)$

Relative entropy (Kullback–Leibler distance)

Motivation: Now that we have a model capable of representing the telegraph system, we design a compression code for it to minimize cost to the telecom companies. One logical way to do this is to assign the shortest codes to the most common letters, based on a blueprint pmf $q(x)$ for the alphabet. However, in reality your sender may be transmitting messages in a different language, or talking about a specific topic, meaning their true probability blueprint is $p(x)$. Because your compression code is optimized for $q$ but reality follows $p$, your system is inefficient and transmits wasted bits. We need a term that measures these wasted bits arising from different assumptions about the underlying language.

Relative entropy, also called the Kullback–Leibler distance and denoted $D(p \,\Vert\, q)$, measures this exact inefficiency.

Why something like $H(p) - H(q)$ would not work

Imagine two operators:

• Operator P types A 99% of the time, and B 1% of the time.
• Operator Q types A 1% of the time, and B 99% of the time.

Because both operators have the exact same ratio of predictability (just flipped), their total average uncertainty is identical: $H(p) = H(q) \approx 0.08$ bits, so any difference-of-entropies measure reports zero penalty.

But say Operator Q’s codebook assigns a tiny 1-bit code to B and a massive 7-bit code to A. If you force Operator P (who almost only types A) to use Operator Q’s codebook, Operator P will be forced to send a massive 7-bit code 99% of the time, causing a high number of wasted bits.

Building the right measure

To find the real penalty, we must look at the cost of a single keystroke, and then average it out.

The extra wasted bits for typing that specific symbol $x$ is actual cost minus ideal cost:

$[-\log_2 q(x)] - [-\log_2 p(x)]$

Using logarithm rules, this simplifies to:

$\log_2 p(x) - \log_2 q(x) = \log_2 \frac{p(x)}{q(x)}$

This fraction is the exact number of extra bits you waste every single time you type the letter $x$, but you only type the letter $x$ according to the true reality of the system, $p(x)$. Therefore, to find the average total penalty of using the wrong codebook, we weight that per-keystroke penalty by the true probability $p(x)$ and sum over the whole alphabet:

Mutual information

Motivation (the severed-wire view): In our communication system with sender $X$ and receiver $Y$, suppose we cut the wire and look at the system. Because the wire is cut, $X$ and $Y$ have absolutely nothing to do with each other, they are independent, and the probability blueprint of this severed system is simply the product of their individual probabilities, $p(x)p(y)$.

One way to measure the ability of the physical connection to communicate the information of $X$ to $Y$ is to measure how far away the connected system is from being a severed system. “Far away” implies distance, so we can use the relative entropy tool $D(p \,\Vert\, q)$ to measure the distance between the true, connected reality $p(x,y)$ and the false, severed assumption $p(x)p(y)$.

Motivation (the engineer’s view): If the wire is cut, the engineer has to compress, transmit, and store $X$ and $Y$ as two completely independent streams of data: sending $X$ takes $H(X)$ bits and sending $Y$ takes $H(Y)$ bits. But if the wire is connected, $Y$ is largely just a noisy echo of $X$, instead of sending $Y$ from scratch, they can just send the differences (the noise), and storing them together as a joint system only takes $H(X,Y)$ bits. The “penalty” of assuming independence is the wasted bandwidth or hard drive space from failing to exploit their physical correlation.

This exact distance from independence is called mutual information, $I(X;Y)$.

Substituting the connected reality $p(x,y)$ for $p$, and the severed assumption $p(x)p(y)$ for $q$, in relative entropy:

Equivalent forms

$I(X;Y)$ is perfectly symmetrical, so $X$ says exactly as much about $Y$ as $Y$ says about $X$:

$I(X; Y) = I(Y; X)$

Chain rule for entropy ($n$ variables)

Motivation: Imagine calculating the total uncertainty of an entire telegraph message of length $n$. You don’t just add up the independent uncertainty of each letter, because letters depend on each other (grammar, spelling, the letter Q may be unlikely but after Q appears, the letter U is very likely). The total uncertainty of a book is the uncertainty of the 1st letter, plus the remaining uncertainty of the 2nd letter given you know the 1st, plus the uncertainty of the 3rd given you know the first two, and so on.

Conditional mutual information

Motivation: Suppose a sender wants to transmit a secret message $X \in \{0, 1\}$ to a receiver. To protect the transmission across an untrusted wire, the sender generates a purely random one-time pad key $Z \in \{0, 1\}$ and broadcasts the ciphertext $Y = X \oplus Z$.

flowchart TD
  X[Secret Plaintext X] --> Y[Ciphertext Y = X ⊕ Z]
  Z[Shared Key Z] --> Y

Without the key, looking at the ciphertext $Y$ tells you absolutely nothing about the message $X$ ($I(X; Y) = 0$).

We want to know: Given that we observe the key $Z$, how much information does the ciphertext $Y$ now reveal about the plaintext $X$?

Following the standard definition of mutual information (baseline uncertainty minus remaining uncertainty), we evaluate how observing $Y$ collapses our remaining doubt about $X$ once $Z$ is fixed:

In the one-time pad:

• $H(X \mid Z) = 1\text{ bit}$ (knowing the key alone leaves $X$ completely unknown).
• $H(X \mid Y, Z) = 0\text{ bits}$ (knowing key and ciphertext lets you reconstruct $X = Y \oplus Z$ perfectly).
• Thus, $I(X; Y \mid Z) = 1 - 0 = 1\text{ bit}$.

Chain rule for mutual information

Motivation: Instead of one sender, imagine a sequence of $n$ different sensors ($X_1 \dots X_n$) transmitting data to a single central receiver hub $Y$. We want to calculate the total amount of useful information the entire sensor array successfully shared with the hub.

Chain rule for relative entropy

Motivation: Recall our compression engineer from earlier. They built a codebook for the entire sender–receiver system $(X,Y)$ based on a false blueprint $q(x,y)$, when reality was actually $p(x,y)$. The total penalty paid in wasted bits is $D(p(x,y) \,\Vert\, q(x,y))$. We can split this penalty into two distinct physical failures:

• The penalty from misunderstanding the sender’s language ($X$).
• The penalty from misunderstanding the noise profile of the wire ($Y \mid X$).

To measure the latter, we define conditional relative entropy, $D\big(p(y \mid x) \,\Vert\, q(y \mid x)\big)$: the average distance between the true physical noise profile and the assumed noise profile, weighted by how often the sender actually transmits each symbol.

Summary

Identities:

• $H(X,Y) = H(X) + H(Y \mid X) = H(Y) + H(X \mid Y)$
• $H(X,Y \mid Z) = H(X \mid Z) + H(Y \mid X, Z)$
• $I(X;Y) = H(X) - H(X \mid Y) = H(Y) - H(Y \mid X) = H(X) + H(Y) - H(X,Y)$
• $I(X;X) = H(X)$
• $0 \le H(X) \le \log_2 \lvert \mathcal{X} \rvert$
• $H(Y \mid X) \neq H(X \mid Y)$ and $D(p \,\Vert\, q) \neq D(q \,\Vert\, p)$ neither is symmetric.