Information and Entropy

The previous chapter, Channels, Signals and Likelihoods, measured a channel by how often it makes mistakes and by how a receiver should weigh what it sees. A binary symmetric channel that flips one bit in ten delivers nine bits in ten correctly, so it is tempting to say that it carries 0.9 bits of information per use. The first chapter, Why Codes Exist, quoted a different figure for the same channel, a capacity of 0.5310 bits per use, and promised to explain it later. The gap between 0.9 and 0.5310 is the subject of this chapter. Counting correct bits does not measure information, because the receiver does not know which nine bits are the correct ones.

Measuring information takes three steps. Surprise assigns a number to a single outcome from its probability alone. Entropy averages surprise over the outcomes of a source. Mutual information extends the idea to the input and output of a channel and measures how much the output reveals about the input, and it is what the 0.5310 counts. Every inequality on the way rests on one fact about the logarithm, which is proved here too.

The tools are the probability of the chapter Probability for Coding and the logarithm. Every number in the chapter is recomputed by ch04_information_and_entropy.py, in the python/ folder of the companion repository ecc-book-lab, which prints each value beside the one the text states and stops at the first disagreement. The charts are drawn by ch04_charts.py in the same folder.

01.Measuring Surprise

A fair coin is tossed out of sight and someone reports the result. Before the report there were two equally likely possibilities, and afterward there is one. A fair die has six equally likely faces, and a card drawn from a shuffled deck has 52 possibilities. The report on the card settles more than the report on the coin, and the question is how much more.

One way to count is with yes-or-no questions. The coin needs one question, "Heads?" An outcome among four equally likely ones needs two. The first question splits the four into two pairs and asks which pair, and the second asks which member of that pair. Eight outcomes need three questions and $2^k$ outcomes need $k$, because each answer halves the candidates. The number of halvings that brings $M$ candidates down to one is the base-2 logarithm, $\log_2 M$, the power to which 2 must be raised to give $M$. Each of the $M$ outcomes has probability $p = 1/M$, so the count can be written in terms of the probability alone, as $\log_2 M = \log_2(1/p)$.

The die shows that the count need not be a whole number. Six faces give $\log_2 6 = 2.585$, between two questions and three, and although no single roll takes 2.585 questions, a long run of rolls can be described with close to 2.585 questions per roll on average, as the next chapter shows.

Surprise does not need equally likely outcomes. For a coin that lands heads nine times in ten, heads has surprise $\log_2(1/0.9) = 0.152$ bits, almost nothing, because heads was expected. Tails has surprise $\log_2 10 = 3.322$ bits, more than a fair die's face, because tails was a rare event. The rare outcome is the informative one, which is the whole idea behind the definition. The table below collects the outcomes used in this chapter.

The base of the logarithm fixes the unit. Base 2 gives bits, the natural logarithm $\ln$ gives units called nats, and the two differ by a constant factor. Since $2^{\log_2 x} = x = e^{\ln x}$, taking $\ln$ of the left side gives $\log_2 x \cdot \ln 2 = \ln x$, so $\log_2 x = \ln x / \ln 2$. The factor $1/\ln 2$ equals $\log_2 e = 1.4427$, so one nat is 1.4427 bits. Proofs in this chapter switch to $\ln$ whenever calculus is involved, because the derivative of $\ln x$ is the simple $1/x$, and then convert back.

02.Why the Logarithm

The card example shows why the logarithm is the right function and not merely a convenient one. Drawing the ace of hearts can be reported in one message, or in two, first the rank and then the suit. The rank is an ace with probability $1/13$ and the suit is hearts with probability $1/4$, and since a shuffled deck holds every rank in every suit, the two are independent, so the probability of both is the product $1/13 \times 1/4 = 1/52$. Either report should carry the same total. In bits, $3.700 + 2 = 5.700$, which matches the ace of hearts in the table of everyday surprises exactly.

The match is no accident. Probabilities of independent events multiply, information should add, and the logarithm is precisely the function that turns products into sums, $\log_2(ab) = \log_2 a + \log_2 b$. Hartley proposed the logarithm of the number of possibilities as the measure of information in 1928 [1], and Shannon weighted it by probability twenty years later [2]. The theorem below shows that the logarithm is the only choice that respects a few modest requirements.

Proof. Substitute $p = 2^{-u}$, so that $u = \log_2(1/p)$ runs over the non-negative numbers, and define $g(u) = f(2^{-u})$. Because $2^{-u} \cdot 2^{-v} = 2^{-(u+v)}$, the additivity of $f$ becomes $g(u + v) = g(u) + g(v)$, and since $f$ decreases in $p$, $g$ increases in $u$. Setting $u = v = 0$ gives $g(0) = 2g(0)$, so $g(0) = 0$. Adding $u$ to itself $n$ times gives $g(nu) = n\,g(u)$ for every whole number $n$. With $c = g(1) = f(1/2)$, this says $g(n) = nc$. Applying the same rule to $n$ copies of $1/n$ gives $n\,g(1/n) = g(1) = c$, so $g(1/n) = c/n$, and then $g(m/n) = m\,g(1/n) = (m/n)\,c$. So $g(u) = cu$ for every non-negative fraction $u$. For any other $u$, pick fractions $r$ and $r'$ with $r < u < r'$. Since $g$ increases, $cr \le g(u) \le cr'$, and because $r$ and $r'$ can be chosen as close to $u$ as desired, $g(u) = cu$. Translating back, $f(p) = g(\log_2(1/p)) = c \log_2(1/p)$. $\blacksquare$

The constant $c$ is the only freedom left, and it is a choice of unit. Setting $c = 1$, so that a fair coin carries exactly one unit, defines the bit.

03.Entropy as Average Surprise

A source does not produce one outcome but a long stream of them, and the useful number is the surprise per outcome on average. The coin biased 9 to 1 produces heads nine times in ten, each with surprise 0.152 bits, and tails once in ten, with surprise 3.322 bits. Over many tosses the average is

$$0.9 \times 0.152 + 0.1 \times 3.322 = 0.1368 + 0.3322 = 0.4690$$

bits per toss. The rare tails carries most of the information, 0.3322 of the 0.4690 bits, although it happens only a tenth of the time. A fair coin averages 1 bit per toss, so the biased coin carries less than half the information of a fair one.

The convention for $p(x) = 0$ is not arbitrary. An impossible outcome never happens, so it should not change the average, and the term $p \log_2(1/p)$ does shrink to 0 as $p$ shrinks. The inequality $\ln t \le t - 1$, proved in the section Convexity and Jensen's Inequality without any use of entropy, gives the rate. Applied to $t = 1/\sqrt{p}$ it says $\ln(1/\sqrt{p}) \le 1/\sqrt{p} - 1 < 1/\sqrt{p}$, and doubling gives $\ln(1/p) < 2/\sqrt{p}$. Multiplying by $p$ and converting to bits,

$$p \log_2 \frac{1}{p} < \frac{2\sqrt{p}}{\ln 2},$$

and the right side falls to 0 with $p$. An outcome of probability 0.001 contributes only $0.001 \log_2 1000 = 0.00997$ bits.

A source that emits one of four letters with probabilities $1/2$, $1/4$, $1/8$ and $1/8$ has entropy $\tfrac12 \cdot 1 + \tfrac14 \cdot 2 + \tfrac18 \cdot 3 + \tfrac18 \cdot 3 = 1.75$ bits. A fair die has $H = \log_2 6 = 2.5850$ bits, since all six terms equal $\tfrac16 \log_2 6$. A loaded die that shows a six half the time and each other face a tenth of the time has

$$H = 0.5 \times 1 + 5 \times 0.1 \times 3.3219 = 2.1610$$

bits, less than the fair die. Loading the die makes its rolls more predictable, and entropy falls.

Entropy depends only on the probabilities, never on what the outcomes are called or what numbers they carry. It is also never negative, since every probability is at most 1, every surprise $\log_2(1/p(x))$ is therefore at least 0, and a sum of non-negative terms cannot be negative. The entropy is 0 exactly when every term is 0, which needs every $p(x)$ to be 0 or 1, so a source has zero entropy only when one outcome is certain. A source that always says the same thing tells nothing.

04.The Binary Entropy Function

The commonest random variable in coding has two values, a bit that is 1 with probability $p$ and 0 with probability $1 - p$. It is a flipped bit on a binary symmetric channel, a 1 in a sparse data stream, or a biased coin. Its entropy gets its own name and symbol.

The chapter Why Codes Exist wrote this function as $H(p)$. From here on the book writes $h(p)$, keeping the capital $H$ for the entropy of a random variable, so that $H(X) = h(p)$ when $X$ is a bit that is 1 with probability $p$. Four values show its shape. A bit that is 1 once in a hundred has $h(0.01) = 0.0808$ bits, which is $8.08$ times its probability, so a rare event is expensive per occurrence even when its total entropy is small. The coin biased 9 to 1 has $h(0.1) = 0.4690$, a bit that is 1 a quarter of the time has $h(0.25) = 0.8113$, and a fair bit has $h(0.5) = 1$. Swapping the roles of 0 and 1 swaps $p$ and $1 - p$ in the formula and leaves the sum unchanged, so $h(p) = h(1 - p)$ and the graph is symmetric about $p = 1/2$.

Proof. Write $h(p) = -p \log_2 p - (1 - p) \log_2 (1 - p)$. The derivative of $\ln p$ is $1/p$, and $\log_2 p = \ln p / \ln 2$, so the derivative of $\log_2 p$ is $1/(p \ln 2)$. By the product rule, the derivative of $p \log_2 p$ is $\log_2 p + p \cdot \frac{1}{p \ln 2} = \log_2 p + \frac{1}{\ln 2}$. The same rule, with the chain rule for $1 - p$, gives the derivative of $(1 - p)\log_2(1 - p)$ as $-\log_2(1 - p) - \frac{1}{\ln 2}$. Subtracting both from 0,

$$h'(p) = -\log_2 p - \frac{1}{\ln 2} + \log_2(1 - p) + \frac{1}{\ln 2} = \log_2 \frac{1 - p}{p}.$$

The ratio $(1 - p)/p$ exceeds 1 when $p < 1/2$, so the slope is positive there, equals 1 at $p = 1/2$, where the slope is $\log_2 1 = 0$, and falls below 1 when $p > 1/2$, where the slope is negative. A function that rises and then falls has its maximum at the turning point, and $h(1/2) = \tfrac12 \cdot 1 + \tfrac12 \cdot 1 = 1$. $\blacksquare$

The slope formula explains why small error rates are costly. At $p = 0.01$ the slope is $\log_2 99 = 6.629$, at $p = 0.1$ it is $\log_2 9 = 3.170$, and at $p = 0.25$ it is $\log_2 3 = 1.585$. Near $p = 0$ the curve is almost vertical, so the first small probability of error adds entropy very quickly, while near $p = 1/2$ a little more noise barely matters, because the bit was already nearly unpredictable.

For $\text{BSC}(0.1)$ the capacity quoted in the chapter Why Codes Exist was $1 - h(0.1) = 0.531$ bits, what is left of each bit once the unpredictability of the channel's flips is paid for, as the section Mutual Information of the Binary Symmetric Channel derives.

05.Convexity and Jensen's Inequality

Every inequality in this chapter rests on one comparison, between the average of a function and the function of an average. A two-point example shows that the two differ. Let $X$ be 1 or 4 with equal probability. Its average is $E[X] = 2.5$, where $E[\cdot]$ denotes the expected value, the probability-weighted average from the chapter Probability for Coding. Taking the logarithm of the average gives $\log_2 E[X] = \log_2 2.5 = 1.3219$, while averaging the logarithms gives $E[\log_2 X] = \tfrac12 \log_2 1 + \tfrac12 \log_2 4 = \tfrac12 \cdot 0 + \tfrac12 \cdot 2 = 1$. The average of the logarithm is smaller. Squaring goes the other way. The average of the squares is $E[X^2] = \tfrac12 \cdot 1 + \tfrac12 \cdot 16 = 8.5$, larger than the square of the average, $(E[X])^2 = 6.25$.

The direction depends on which way the function bends. The graph of $x^2$ bends upward, so a straight line drawn between two of its points, a chord, lies above the curve, and the average of the function values, which sits on the chord, exceeds the function at the average point. The logarithm bends downward, its chords lie below it, and the inequality flips.

The left side is the function at a point between $a$ and $b$, and the right side is the height of the chord above that point, so the definition says exactly that every chord lies on or above the graph. The square is convex, because

$$\lambda a^2 + (1 - \lambda) b^2 - \bigl(\lambda a + (1 - \lambda) b\bigr)^2 = \lambda (1 - \lambda)(a - b)^2 \ge 0.$$

Expanding the square on the left gives $\lambda^2 a^2 + 2\lambda(1 - \lambda)ab + (1 - \lambda)^2 b^2$, and subtracting it from $\lambda a^2 + (1 - \lambda) b^2$ leaves $\lambda(1 - \lambda)a^2 - 2\lambda(1 - \lambda)ab + \lambda(1 - \lambda)b^2$, which is the product on the right. A product of two non-negative weights and a square cannot be negative.

The logarithm needs one inequality, the most useful single fact in information theory.

Proof. Let $g(x) = x - 1 - \ln x$. Its derivative is $g'(x) = 1 - 1/x$, which is negative for $0 < x < 1$, zero at $x = 1$ and positive for $x > 1$. So $g$ falls until $x = 1$ and rises afterward, and its smallest value is $g(1) = 1 - 1 - \ln 1 = 0$. Every other value is larger, so $g(x) > 0$ for $x \ne 1$, which is the claim. $\blacksquare$

Two checks make the lemma concrete. At $x = 2$ it says $\ln 2 = 0.6931 \le 1$, and at $x = 0.5$ it says $\ln 0.5 = -0.6931 \le -0.5$. Geometrically, $y = x - 1$ is the tangent line to $y = \ln x$ at $x = 1$, and the lemma says the curve never rises above it.

The lemma proves that the logarithm is concave. Take $a, b > 0$ and $m = \lambda a + (1 - \lambda) b$. Applying the lemma to $x = a/m$ gives $\ln a - \ln m \le a/m - 1$, and applying it to $b/m$ gives $\ln b - \ln m \le b/m - 1$. Multiplying the first by $\lambda$, the second by $1 - \lambda$, and adding,

$$\lambda \ln a + (1 - \lambda) \ln b - \ln m \le \frac{\lambda a + (1 - \lambda) b}{m} - 1 = 0,$$

which is the concavity inequality for $\ln$, and dividing by $\ln 2$ gives it for $\log_2$. The definition speaks of two points, but averages in information theory run over whole alphabets, and the extension is Jensen's inequality [3].

Proof. The argument is by induction on the number of values $n$. With one value both sides equal $f(x_1)$, and with two values the inequality is the definition of convexity. Suppose it holds for $n - 1$ values. If $p_n = 1$ the other probabilities are 0 and both sides equal $f(x_n)$. Otherwise set $y = \sum_{i < n} \frac{p_i}{1 - p_n} x_i$, an average of the first $n - 1$ values whose weights $p_i/(1 - p_n)$ add to 1. Then $\sum_i p_i x_i = (1 - p_n)\,y + p_n x_n$, and the definition of convexity with $\lambda = 1 - p_n$ gives

$$f\Bigl(\sum_i p_i x_i\Bigr) \le (1 - p_n) f(y) + p_n f(x_n).$$

The induction hypothesis bounds $f(y)$ by $\sum_{i<n} \frac{p_i}{1 - p_n} f(x_i)$, and multiplying by $1 - p_n$ turns the right side into $\sum_i p_i f(x_i)$. For the logarithm, apply the lemma to $x_i/m$ with $m = E[X]$, weight by $p_i$ and add, exactly as in the two-point case, to get $E[\ln X] - \ln m \le E[X]/m - 1 = 0$. Equality needs $\ln(x_i/m) = x_i/m - 1$ for every value of positive probability, which by the lemma means $x_i = m$ for all of them. $\blacksquare$

06.Relative Entropy and Gibbs' Inequality

Suppose the biased coin is described by someone who believes it is fair. That observer assigns each outcome surprise $\log_2 2 = 1$ bit, and so averages 1 bit per toss, when the true entropy is 0.4690 bits. The average surprise measured with a wrong model, here $\sum_x p(x) \log_2(1/q(x))$ with the true probabilities $p$ and the believed ones $q$, is called the cross-entropy. The excess, $1 - 0.4690 = 0.5310$ bits, is the price of the wrong belief. Subtracting the entropy from the cross-entropy term by term gives a formula for that price.

Kullback and Leibler introduced this quantity in 1951 [4], and it is also called the Kullback–Leibler divergence. For the biased coin $P = (0.9, 0.1)$ against the fair model $Q = (0.5, 0.5)$, the two terms are $0.9 \log_2(0.9/0.5) = 0.9 \times 0.8480 = 0.7632$ and $0.1 \log_2(0.1/0.5) = -0.2322$, so $D(P \,\|\, Q) = 0.7632 - 0.2322 = 0.5310$ bits, the excess found above. One term is negative, which shows that the individual terms carry no sign guarantee. The total, as the next theorem proves, always does.

Swapping the roles gives a different number. With the fair coin as truth and the biased model as belief, $D(Q \,\|\, P) = 0.5 \log_2(0.5/0.9) + 0.5 \log_2(0.5/0.1) = -0.4240 + 1.1610 = 0.7370$ bits. Believing a fair coin is biased costs more than the reverse, because the biased model assigns tails a surprise of 3.322 bits and a fair coin produces tails half the time. Relative entropy is not symmetric, so it is not a distance in the geometric sense. If the model calls an outcome impossible that in fact occurs, the cost is infinite, which is the formula's way of saying that a description built on that model has no way to record the outcome at all.

Proof. If some outcome has $p(x) > 0$ and $q(x) = 0$, then $D$ is infinite and the claim holds. Otherwise sum over the outcomes with $p(x) > 0$, convert to natural logarithms, and apply the lemma $\ln t \le t - 1$ with $t = q(x)/p(x)$,

$$-D(P \,\|\, Q) = \frac{1}{\ln 2} \sum_{p(x) > 0} p(x) \ln \frac{q(x)}{p(x)} \le \frac{1}{\ln 2} \sum_{p(x) > 0} p(x) \Bigl(\frac{q(x)}{p(x)} - 1\Bigr) = \frac{1}{\ln 2}\Bigl(\sum_{p(x) > 0} q(x) - 1\Bigr).$$

The probabilities $q(x)$ over part of the alphabet add to at most 1, so the right side is at most 0, and $D(P \,\|\, Q) \ge 0$. Equality needs equality in the lemma for every term, so $q(x) = p(x)$ wherever $p(x) > 0$, and it needs those $q(x)$ to add to 1, which leaves nothing for the remaining outcomes. Then $Q = P$. $\blacksquare$

07.How Large Entropy Can Be

The fair die has the largest entropy of any six-sided die in this chapter, and the pattern holds in general. Intuition says that an evenly spread distribution is the least predictable, and Gibbs' inequality makes that precise.

Proof. Let $U$ be the uniform distribution, $u(x) = 1/M$. Then

$$D(P \,\|\, U) = \sum_x p(x) \log_2 \bigl(p(x) \cdot M\bigr) = \sum_x p(x) \log_2 M - \sum_x p(x) \log_2 \frac{1}{p(x)} = \log_2 M - H(X).$$

Gibbs' inequality makes the left side non-negative, and zero only when $P = U$. $\blacksquare$

A second proof uses Jensen's inequality instead. The entropy is the average of $\log_2(1/p(X))$, the logarithm is concave, and so $H(X) \le \log_2 E[1/p(X)] = \log_2 \sum_{p(x) > 0} p(x) \cdot \frac{1}{p(x)}$, which is the logarithm of the number of outcomes with positive probability, at most $\log_2 M$.

The first proof gives more than a bound. It says that the shortfall of a distribution's entropy below the maximum equals its relative entropy from the uniform distribution. For the loaded die, $\log_2 6 - 2.1610 = 2.5850 - 2.1610 = 0.4240$ bits, and computing $D(P \,\|\, U)$ directly from the definition gives the same 0.4240. Loading the die costs it 0.4240 bits of unpredictability per roll, and that is exactly how far its distribution sits from fairness.

08.Joint and Conditional Entropy

A channel has two ends, so information about a channel needs entropies of two variables at once. A running example carries the rest of the chapter. An input bit $X$ is 1 with probability $q = 0.25$ and 0 with probability $0.75$, and it is sent through $\text{BSC}(0.1)$, which flips it with probability 0.1. The received bit is $Y$. Multiplying the probability of each input by the probability of what the channel does to it gives the probability of each pair. For example, $X = 0$ and $Y = 0$ needs a 0 to be sent and not flipped, with probability $0.75 \times 0.9 = 0.675$. The other three pairs have probabilities $p(0, 1) = 0.075$, $p(1, 0) = 0.025$ and $p(1, 1) = 0.225$. Adding along each row recovers $P(X = 0) = 0.75$, and adding down the columns gives $P(Y = 0) = 0.7$ and $P(Y = 1) = 0.3$.

The pair $(X, Y)$ is itself a random variable with four outcomes, so it has an entropy like any other.

For the running example the four terms are $0.675 \log_2(1/0.675) = 0.3828$, $0.075 \log_2(1/0.075) = 0.2803$, $0.025 \log_2(1/0.025) = 0.1330$ and $0.225 \log_2(1/0.225) = 0.4842$, and

$$H(X, Y) = 0.3828 + 0.2803 + 0.1330 + 0.4842 = 1.2803 \text{ bits}.$$

The input alone has $H(X) = h(0.25) = 0.25 \log_2 4 + 0.75 \log_2(4/3) = 0.5 + 0.3113 = 0.8113$ bits. The pair holds more uncertainty than the input, because the channel's flip adds some of its own. How much it adds is a conditional entropy.

Once $X$ is known, $Y$ is still uncertain. If $X = 0$, then $Y$ is 1 with probability 0.1, so the remaining uncertainty is $H(Y \mid X = 0) = h(0.1) = 0.4690$ bits. If $X = 1$, then $Y$ is 0 with probability 0.1, and again $H(Y \mid X = 1) = 0.4690$. The vertical bar is read "given".

In the running example both values of $X$ leave 0.4690 bits, so $H(Y \mid X) = 0.75 \times 0.4690 + 0.25 \times 0.4690 = 0.4690$ bits. Notice that $0.8113 + 0.4690 = 1.2803$, the joint entropy. The match is a theorem.

Proof. The definition of conditional probability gives $p(x, y) = p(x)\, p(y \mid x)$. Taking $\log_2$ of the reciprocal turns the product into a sum, $\log_2 \frac{1}{p(x, y)} = \log_2 \frac{1}{p(x)} + \log_2 \frac{1}{p(y \mid x)}$. Multiply by $p(x, y)$ and add over all pairs. The left side becomes $H(X, Y)$. In the first term on the right, adding $p(x, y)$ over $y$ for a fixed $x$ gives $p(x)$, so that term becomes $\sum_x p(x) \log_2 \frac{1}{p(x)} = H(X)$. The second term is $H(Y \mid X)$ by definition. The second form follows from the same argument with the roles of $X$ and $Y$ swapped. $\blacksquare$

In words, the uncertainty about a pair is the uncertainty about the first member plus whatever remains about the second once the first is known. The second form of the rule computes the uncertainty about the input that remains once the output is seen, the quantity a decoder cares about. The output has $H(Y) = h(0.3)$, with terms $0.3 \log_2(10/3) = 0.5211$ and $0.7 \log_2(10/7) = 0.3602$, so $H(Y) = 0.8813$ bits. Then

$$H(X \mid Y) = H(X, Y) - H(Y) = 1.2803 - 0.8813 = 0.3990 \text{ bits}.$$

The definition gives the same number directly, which is a useful check. A received 0 came from a sent 1 with probability $P(X = 1 \mid Y = 0) = 0.025/0.7 = 0.0357$, and a received 1 came from a sent 1 with probability $0.225/0.3 = 0.75$. Evaluated at the exact fractions, the remaining uncertainties are $h(0.025/0.7) = 0.2223$ and $h(0.225/0.3) = h(0.75) = 0.8113$ bits, and averaging over the outputs gives $0.7 \times 0.2223 + 0.3 \times 0.8113 = 0.3990$ bits. A curious detail hides in the second term. After a received 1, the input is 1 with probability 0.75, the mirror image of the prior 0.25, so the uncertainty $h(0.75) = h(0.25)$ is exactly what it was before anything was received. The received 1 changed the belief completely and the amount of uncertainty not at all.

The chain rule extends to any number of variables by applying it repeatedly, $H(X, Y, Z) = H(X) + H(Y \mid X) + H(Z \mid X, Y)$. Take two independent fair bits $X$ and $Y$ and their exclusive or $Z = X \oplus Y$, which is 1 when exactly one of them is 1. Then $H(X) = 1$, $H(Y \mid X) = 1$ because $Y$ is independent of $X$, and $H(Z \mid X, Y) = 0$ because $Z$ is computed from them. So $H(X, Y, Z) = 2$ bits, although there are three bits in the triple. The third bit is redundant, and a parity bit is redundant in exactly this way.

09.Conditioning Reduces Entropy

In the running example, seeing the output cut the uncertainty about the input from $H(X) = 0.8113$ to $H(X \mid Y) = 0.3990$ bits. Learning something can never increase uncertainty on average.

Proof. Write both entropies as averages over the joint distribution. Since $\sum_y p(x, y) = p(x)$, $H(X) = \sum_{x, y} p(x, y) \log_2 \frac{1}{p(x)}$, and by definition $H(X \mid Y) = \sum_{x, y} p(x, y) \log_2 \frac{1}{p(x \mid y)}$. Subtracting, and using $p(x \mid y) = p(x, y)/p(y)$,

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

The right side is the relative entropy between the joint distribution $p(x, y)$ and the product distribution $p(x)\,p(y)$, the distribution the pair would have if the two variables were independent. Gibbs' inequality makes it non-negative, and zero only when $p(x, y) = p(x)\,p(y)$ for every pair, which is the definition of independence. $\blacksquare$

10.Mutual Information

The drop in uncertainty about the input caused by seeing the output is the information the output carries about the input, and it is the central quantity of the subject.

For the running example, $I(X; Y) = 0.8113 - 0.3990 = 0.4123$ bits. Each use of the channel carries 0.4123 bits about the input, out of the 0.8113 bits the input holds, a share of $0.4123/0.8113 = 0.508$. The definition looks lopsided, since it starts from the uncertainty about $X$, but the quantity is symmetric, which is why the name says mutual.

Proof. The chain rule gives $H(X \mid Y) = H(X, Y) - H(Y)$. Substituting into the definition gives $I(X; Y) = H(X) + H(Y) - H(X, Y)$, an expression that does not change when $X$ and $Y$ are swapped. Substituting the other form of the chain rule, $H(X, Y) = H(X) + H(Y \mid X)$, gives $H(Y) - H(Y \mid X)$. Non-negativity and the condition for zero are the theorem Conditioning Reduces Entropy. $\blacksquare$

The running example confirms all three forms. The second gives $0.8813 - 0.4690 = 0.4123$ bits and the third gives $0.8113 + 0.8813 - 1.2803 = 0.4123$ bits. The second form is the one used for channels, because $H(Y \mid X)$ is the noise the channel adds, known from the channel alone, while $H(X \mid Y)$ needs a decoder's view of the problem. The proof also produced a formula that works straight from the joint table.

If $X$ and $Y$ are independent, every ratio inside the logarithm is 1 and $I(X; Y) = 0$. A channel whose output is independent of its input carries nothing, however often it is used. If $Y = X$, a perfect channel, then $H(X \mid X) = 0$ and $I(X; X) = H(X)$, which for the running input is 0.8113 bits. Everything the input holds gets through, and no channel can deliver more than that. The table below collects the running example.

11.The Information Diagram

The relations among these six numbers fit in one picture. Draw the entropy of $X$ as a disc and the entropy of $Y$ as a second, overlapping disc, with areas proportional to bits. The overlap is the mutual information, the part of each variable's uncertainty that the other explains. The part of the $X$ disc outside the overlap is $H(X \mid Y)$, what remains about $X$ once $Y$ is known, and the part of the $Y$ disc outside it is $H(Y \mid X)$. The whole shaded area is $H(X, Y)$.

Every identity proved so far reads off the diagram. The two crescents and the overlap make up the whole, $0.3990 + 0.4123 + 0.4690 = 1.2803$. The left crescent and the overlap make up the $X$ disc, $0.3990 + 0.4123 = 0.8113$, and the overlap and the right crescent make up the $Y$ disc, $0.4123 + 0.4690 = 0.8813$. For two variables every region is a quantity already proved non-negative, so the picture is honest.

For three variables it is not, and the failure is instructive. Draw three discs for $X$, $Y$ and the exclusive or $Z = X \oplus Y$ of two independent fair bits. The conditional mutual information $I(X; Y \mid Z) = H(X \mid Z) - H(X \mid Y, Z)$ measures how much $Y$ tells about $X$ once $Z$ is known. Knowing $Z$ alone says nothing about $X$, since for either value of $X$ the bit $Z$ is equally likely to be 0 or 1, so $H(X \mid Z) = 1$. Knowing both $Y$ and $Z$ determines $X = Y \oplus Z$, so $H(X \mid Y, Z) = 0$ and $I(X; Y \mid Z) = 1$ bit. Yet $X$ and $Y$ are independent, so $I(X; Y) = 0$. The central region of the three-disc picture would have to be $I(X; Y) - I(X; Y \mid Z) = 0 - 1 = -1$ bit, a negative area. Two independent bits become completely dependent once their parity is known, and no arrangement of discs can draw that. The diagram is a reliable guide for two variables and only a mnemonic for more.

12.Mutual Information of the Binary Symmetric Channel

The reasoning of the running example works for any input probability $q$ and flip probability $p$, and it ends with the 0.5310 of the opening paragraph. The output is 1 when a 1 is sent and kept or a 0 is sent and flipped, so

$$r = P(Y = 1) = q(1 - p) + (1 - q)p.$$

Whatever is sent, the channel flips it with probability $p$, so $H(Y \mid X = x) = h(p)$ for both inputs and $H(Y \mid X) = h(p)$. The second form of the mutual information then gives

The noise term $h(p)$ does not depend on the input, so the input distribution matters only through $h(r)$. The largest value $h$ can take is 1, at $r = 1/2$. To see which input achieves it, subtract $1/2$ from $r$,

$$r - \tfrac12 = q - 2qp + p - \tfrac12 = q(1 - 2p) - \tfrac12(1 - 2p) = (1 - 2p)\bigl(q - \tfrac12\bigr).$$

For any channel with $p \ne 1/2$, the output is uniform exactly when the input is.

Proof. The output is a single bit, so $h(r) = H(Y) \le \log_2 2 = 1$ by the theorem The Uniform Distribution Maximizes Entropy, and $I(X; Y) = h(r) - h(p) \le 1 - h(p)$. At $q = 1/2$ the identity above gives $r = 1/2$, so $h(r) = 1$ and the bound is reached. $\blacksquare$

For $\text{BSC}(0.1)$ the uniform input gives $1 - 0.4690 = 0.5310$ bits per use, the capacity quoted in the chapter Why Codes Exist. Nine bits in ten arrive correctly, but the receiver cannot tell which, and resolving that doubt costs $h(0.1) = 0.4690$ bits of every received bit. What remains, 0.5310 bits, is the information about the input that a received bit actually carries.

The table shows how quickly a skewed input wastes the channel. The input with $q = 0.25$ of the running example uses only 0.4123 of the available 0.5310 bits, and the rare alarm, at $q = 0.05$, only 0.1152. The noise costs the same 0.4690 bits in every row, and what changes is how much uncertainty the input brings to be revealed.

The uniform curve is symmetric, $1 - h(1 - p) = 1 - h(p)$, so a channel that flips nine bits in ten is exactly as good as one that flips one in ten, because a receiver that knows the channel simply inverts every bit. The worst channel is $\text{BSC}(0.5)$, where $r = 1/2$ whatever is sent and $I = 1 - 1 = 0$. A channel that flips half its bits produces output independent of its input, and no code can help.

Other channels give other answers. On the binary erasure channel $\text{BEC}(\varepsilon)$ of the previous chapter, an output that is not erased reveals the input completely, and an erasure, which happens with probability $\varepsilon$ whatever is sent, leaves the input exactly as uncertain as before. So $H(X \mid Y) = \varepsilon H(X)$ and $I(X; Y) = (1 - \varepsilon)\,h(q)$, which for $\text{BEC}(0.1)$ with a uniform input is 0.9 bits. On the Z-channel $\text{Z}(p)$, which never disturbs a 0 and turns a 1 into a 0 with probability $p$, the output is 1 with probability $q(1 - p)$, a sent 0 leaves no uncertainty about the output and a sent 1 leaves $h(p)$, so $H(Y \mid X) = q\,h(p)$ and

With $p = 0.1$ and a uniform input this is $h(0.45) - 0.5\,h(0.1) = 0.9928 - 0.2345 = 0.7583$ bits. At the same noise level the erasure channel carries 0.9 bits, the Z-channel 0.7583 and the symmetric channel 0.5310. A flip that announces itself as an erasure is the cheapest damage, a flip that can strike only one symbol is next, and a flip that can strike either symbol unannounced is the most expensive.

The largest mutual information a channel can deliver, maximized over every input distribution, is its capacity. This chapter has computed it for the binary symmetric channel without naming it, and the chapter Capacity and Shannon's Theorem defines it in general and proves the theorem that gives it meaning, that every rate below capacity can be reached with as few decoding errors as desired.

13.Looking Ahead

This chapter measured information. The next chapter, Source Coding and Prefix Codes, spends it. The four-letter source with probabilities $1/2$, $1/4$, $1/8$ and $1/8$ had entropy 1.75 bits, and a simple strategy matches that number exactly. Ask first whether the letter is the first one, and stop if it is. Otherwise ask whether it is the second, and if not, one more question separates the last two. The first letter takes one question, the second two and the last two three each, for an average of 1.75 questions. Writing each answer as a bit turns the questions into a code, 0, 10, 110 and 111, whose average length equals the entropy.

The next chapter asks when this works in general. It defines codes that can be decoded without separators, the prefix codes in which no codeword begins another, and proves the Kraft and McMillan inequalities that limit how short their codewords can be. It builds the Shannon–Fano code, which gives each letter a codeword about as long as its surprise, and Huffman's algorithm, with a proof that no prefix code does better. It ends with Shannon's source coding theorem, which says that no code can average fewer bits per letter than the entropy and that codes come within one bit of it. MacKay [5] and Cover and Thomas [6] develop the material of this chapter and the next in depth, and Lin and Costello [7] connect it to the codes of the later Parts.

14.Worked Examples

15.Exercises

References

1. [1]Hartley, R. V. L. (1928). “Transmission of Information.” Bell System Technical Journal, 7(3), pp. 535–563. doi:10.1002/j.1538-7305.1928.tb01236.x
2. [2]Shannon, Claude E. (1948). “A Mathematical Theory of Communication.” Bell System Technical Journal, 27(3), pp. 379–423. The paper concludes in the October issue, volume 27, number 4, pages 623 to 656. doi:10.1002/j.1538-7305.1948.tb01338.x
3. [3]Jensen, J. L. W. V. (1906). “Sur les fonctions convexes et les inégalités entre les valeurs moyennes.” Acta Mathematica, 30, pp. 175–193. doi:10.1007/BF02418571
4. [4]Kullback, S. and Leibler, R. A. (1951). “On Information and Sufficiency.” The Annals of Mathematical Statistics, 22(1), pp. 79–86. doi:10.1214/aoms/1177729694
5. [5]MacKay, David J. C. (2003). “Information Theory, Inference, and Learning Algorithms.” Cambridge University Press. The author's site offers the whole book free to read on screen. https://www.inference.org.uk/itila/book.html
6. [6]Cover, Thomas M. and Thomas, Joy A. (2006). “Elements of Information Theory.” 2nd edition. Wiley-Interscience. doi:10.1002/047174882X
7. [7]Lin, Shu and Costello, Jr., Daniel J. (2004). “Error Control Coding: Fundamentals and Applications.” 2nd edition. Pearson Prentice Hall.