Mutual Information Explained: The Information Shared by Sender and Receiver

Foundations of Information Theory · Part 4

An intuitive explanation of mutual information: why the information transferred over a noisy channel is the same seen from the sender’s side and the receiver’s side.

In Part 3 we solved our puzzle. For the channel y = x + w with w \in \{0, 1\}, observing y reduces the uncertainty about x from 1 bit to \tfrac12 bit, so half a bit of information gets through per transmission:

H(X) - H(X \mid Y) = 1 - \tfrac12 = \tfrac12 \text{ bit}.

Now let us ask the question the other way round.

The reverse question

How much does knowing x reduce the uncertainty about y? At first sight this seems to be a completely different question. Let us answer it with exactly the same steps.

Before x is known, y takes the values 0, 1 and 2 with probabilities \tfrac14, \tfrac12 and \tfrac14, so its entropy is

H(Y) = \tfrac14 \log_2 4 + \tfrac12 \log_2 2 + \tfrac14 \log_2 4 = 1.5 \text{ bits}.

Once x is known, the only thing that can still change y is the noise. If x = 0, then y is 0 or 1, each with probability \tfrac12; if x = 1, then y is 1 or 2, again with probability \tfrac12 each. Either way, 1 bit of uncertainty remains, so H(Y \mid X) = 1 bit. The reduction is

H(Y) - H(Y \mid X) = 1.5 - 1 = \tfrac12 \text{ bit}.

The same answer, from the opposite direction. There is a nice way to see why. The received signal varies by 1.5 bits in total. One bit of that variation is just the noise. The remaining half bit is the part that carries information about x.

Why the two answers are always equal

One example cannot prove that this always happens. To see that it does, write H(X) as a sum over pairs (x, y) (adding P(x, y) over all y gives P(x)), and subtract the formula for conditional entropy from Part 3. Using Bayes’ rule, P(x \mid y) = P(x, y)/P(y), everything collapses into one symmetric expression:

H(X) - H(X \mid Y) = \sum_{x, y} P(x, y) \log_2 \frac{P(x, y)}{P(x)\, P(y)} .

In this expression x and y play exactly the same role: swap them and nothing changes. Starting from H(Y) - H(Y \mid X) leads to the same expression. So the two answers are equal for every channel, not just ours.

For our channel, only four pairs can occur:

(x, y)	P(x, y)	P(x)\,P(y)	Contribution
(0, 0)	\tfrac14	\tfrac18	\tfrac14 \log_2 2 = \tfrac14
(0, 1)	\tfrac14	\tfrac14	0
(1, 1)	\tfrac14	\tfrac14	0
(1, 2)	\tfrac14	\tfrac18	\tfrac14 \log_2 2 = \tfrac14

The total is again \tfrac12 bit. The table also shows where the information comes from: the pairs with y = 1 contribute nothing, because observing y = 1 tells the receiver nothing about x. All of the information comes from the observations y = 0 and y = 2.

Mutual information

Because the reduction in uncertainty is the same in both directions, it does not belong to x alone or to y alone: it is shared by the two. That is why it is called the mutual information:

I(X; Y) = H(X) - H(X \mid Y) = H(Y) - H(Y \mid X)

Mutual information is the precise form of the idea we started with in Part 1: the initial uncertainty minus the remaining uncertainty.

The symmetric formula also tells us when no information gets through. If x and y are independent, then P(x, y) = P(x)\,P(y) for every pair, every logarithm in the sum is \log_2 1 = 0, and I(X; Y) = 0. Information can only be transferred when what is received depends on what was sent.

As a check, consider the first channel from Part 1, where the noise was -1 or +1 and the received sets never overlapped. Every received value comes from exactly one bit, so H(X \mid Y) = 0 and I(X; Y) = 1 - 0 = 1 bit. From the other side, y takes four equally likely values, so H(Y) = 2 bits, and once x is known only the 1 bit of noise remains: 2 - 1 = 1 bit again. The formulas confirm what we saw on the number line at the very start.

Looking ahead: how much can a channel carry?

All along, we assumed that 0 and 1 are equally likely. That was a choice. If the transmitter sends a 1 with probability q, the same steps show that our second channel transfers

I(X; Y) = \tfrac12 H(q),

where H(q) is the entropy of the source.

Two curves against q. The dashed curve is the source entropy, peaking at 1 bit. The solid curve is half of it, peaking at half a bit at q = 0.5. — Figure 1: Information transferred through the overlapping channel as the transmitter changes how often it sends a 1. The channel delivers exactly half of the source’s entropy, and at most half a bit.

So the information that gets through depends not only on the channel, but on how the transmitter uses it. This raises a natural question: what is the most information a channel can carry, over all the ways the transmitter can choose its input? That number is the channel’s capacity, and it is where this series goes next.

Previous: What is conditional entropy? Solving the noisy-channel puzzle

Back to the series: Foundations of Information Theory

Read the full chapter, with worked problems: Chapter 1 (PDF)