What Is Conditional Entropy? Solving the Noisy-Channel Puzzle

Foundations of Information Theory · Part 3

An intuitive explanation of conditional entropy with a worked example: how much uncertainty remains after observing a noisy signal, with Bayes’ rule derived by counting.

In Part 1 we met a puzzle. A bit x is sent through a channel that adds noise w \in \{0, 1\}, and the receiver sees y = x + w. When y = 1, the receiver cannot tell which bit was sent. So how much information gets through: one bit, zero bits, or somewhere in between?

We now have everything we need to answer it. Recall the idea we started with:

Information Transferred = Initial Uncertainty − Remaining Uncertainty

The bits are equally likely, so the initial uncertainty is the entropy of a fair bit, which Part 2 showed is exactly 1 bit. The whole question is: what is the remaining uncertainty?

How often does each value occur?

To calculate anything, we must also say how the noise behaves. Let both noise values be equally likely, and let the noise be independent of the bit. Then each of the four combinations of x and w has probability \tfrac12 \times \tfrac12 = \tfrac14:

x	w	y = x + w	Probability
0	0	0	\tfrac14
0	1	1	\tfrac14
1	0	1	\tfrac14
1	1	2	\tfrac14

The value y = 0 is produced in only one way, and so is y = 2. But y = 1 is produced in two ways, so

P(y=0) = \tfrac14, \qquad P(y=1) = \tfrac14 + \tfrac14 = \tfrac12, \qquad P(y=2) = \tfrac14 .

What the receiver believes after seeing y

This is the key step. When the receiver sees a particular value of y, what should it believe about x?

Imagine a thousand transmissions. Each of the four combinations happens about 250 times. Now suppose the receiver sees y = 1. It should keep only the cases where y was 1, about 500 of them, and ignore everything else. Of these 500 cases, about 250 had x = 0. So

P(x=0 \mid y=1) = \frac{250}{500} = \frac{1/4}{1/2} = \tfrac12 .

Seeing y = 1 leaves the receiver exactly where it started: fifty-fifty. Doing the same counting for the other two values, if the receiver sees y = 0, it is certain the bit was 0, and if it sees y = 2, it is certain the bit was 1.

Three bar charts. After y = 0, x = 0 has probability 1. After y = 1, both values have probability one half. After y = 2, x = 1 has probability 1. — Figure 1: What the receiver believes about the transmitted bit after each observation. Only y = 1 leaves any doubt.

In every case we did the same thing: we divided the probability of this x and this y happening together by the total probability of this y,

P(x \mid y) = \frac{P(x, y)}{P(y)} .

This is Bayes’ rule. We did not need to memorise it: it came directly from counting.

The remaining uncertainty for one observation

After seeing y, the receiver has a new probability distribution for x, and we already know how to measure the uncertainty of a distribution: its entropy. The only change is that the probabilities are now the updated ones:

H(X \mid Y = y) = \sum_x P(x \mid y) \log_2 \frac{1}{P(x \mid y)} .

For our channel this gives 0 bits after seeing y = 0, 1 bit after seeing y = 1, and 0 bits after seeing y = 2. This is exactly what intuition said: seeing 0 or 2 settles the question, while seeing 1 leaves all of the doubt.

Averaging: conditional entropy

The receiver does not get to choose which y it sees. So, just as entropy is an average over outcomes, we average the remaining uncertainty over all possible observations, weighting each by how often it occurs:

H(X \mid Y) = \sum_y P(y)\, H(X \mid Y = y)

For our channel,

H(X \mid Y) = \tfrac14 \cdot 0 + \tfrac12 \cdot 1 + \tfrac14 \cdot 0 = \tfrac12 \text{ bit}.

This average is called the conditional entropy: the uncertainty about x that remains, on average, after the receiver observes y. Written as a single sum, it has the same shape as entropy itself:

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

Both are an average of surprise. In entropy, the surprise is measured before the receiver observes anything; in conditional entropy, it is measured after observing y, and then averaged over everything that can happen.

The answer to the puzzle

We now have both terms of our equation:

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

The answer was (C): somewhere in between. And it makes sense. Half the time, when the receiver sees 0 or 2, it learns the bit exactly. The other half of the time, when it sees 1, it learns nothing. On average, the channel delivers half of the bit that was sent.

Previous: Why does the entropy formula have a logarithm?

Next: Mutual information explained: the information shared by sender and receiver

Back to the series: Foundations of Information Theory

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