Contents / Information Theory / Entropy, Joint and Conditional Entropy

Chapter 1

Entropy, Joint and Conditional Entropy

What information means, how entropy measures it, and how entropy behaves when several random variables are considered together.

Introduction

What information means, how entropy measures it, and how entropy behaves when several random variables are considered together.

1.1Surprisal: What Information Should Mean

Before measuring information we must decide what we are measuring. Information theory takes the position that information is reduction of uncertainty: an outcome you were already certain of tells you nothing, and the more unexpected an outcome is, the more you learn from observing it. That single sentence, taken seriously, forces the logarithm on us.

Definition 1.1 (Surprisal (self-information)). Let $X$ be a discrete random variable with probability mass function $p$ . The surprisal of the outcome $x$ is

I(x) = \log_2 \frac{1}{p(x)} = -\log_2 p(x) \quad\text{bits},

defined for every $x$ with $p(x) > 0$ .

Intuition. Surprisal answers "how astonished should I be?", measured in yes/no questions. If an event has probability $1/2^k$ , then narrowing the world down to that event is exactly the work of $k$ successive halvings — $k$ coin flips' worth of news. A certain event ( $p=1$ ) costs $0$ bits, and an event of probability $10^{-6}$ costs about $20$ bits.

Why the logarithm specifically? Because we want surprisal to be additive over independent observations: hearing two unrelated pieces of news should inform you by the sum of their separate amounts. Combined with monotonicity and a little regularity, additivity pins the function down completely.

Theorem 1.2 (The logarithm is forced). Suppose $f : (0,1] \to [0,\infty)$ satisfies

$f$ is monotone non-increasing (rarer events are no less informative),
$f(pq) = f(p) + f(q)$ for all $p,q \in (0,1]$ (independent events add), and
$f$ is not identically zero.

Then there is a constant $c>0$ with $f(p) = -c\log_2 p$ for all $p \in (0,1]$ . Normalising by $f(1/2)=1$ gives $c=1$ , i.e. $f(p) = -\log_2 p$ .

Proof. Put $g(t) = f(2^{-t})$ for $t \ge 0$ . Condition (2) becomes $g(s+t) = g(s)+g(t)$ , Cauchy's functional equation, and condition (1) makes $g$ monotone non-decreasing. Additivity gives $g(n) = n\,g(1)$ for every positive integer $n$ , and $m\,g(n/m) = g(n)$ forces $g(r) = r\,g(1)$ for every positive rational $r$ . If $t$ is irrational, take rationals $r < t < s$ ; monotonicity gives $r\,g(1) \le g(t) \le s\,g(1)$ , and letting $r \uparrow t$ and $s \downarrow t$ yields $g(t) = t\,g(1)$ . Hence $f(2^{-t}) = t\,g(1)$ , that is, $f(p) = -g(1)\log_2 p$ . Condition (3) forces $g(1)\neq 0$ and monotonicity forces $g(1)>0$ ; set $c = g(1)$ .∎

Note how little was assumed. We did not ask for continuity — monotonicity alone rules out the pathological additive functions — and we did not ask for any particular scale. The base of the logarithm is a choice of unit, not a piece of mathematics.

Notation. Base $2$ gives bits (also called shannons); base $e$ gives nats; base $10$ gives bans (or hartleys). Conversion is one multiplication, since $\log_b p = \log_a p/\log_a b$ :

1 \text{ nat} = \log_2 e \approx 1.4427 \text{ bits}, \qquad 1 \text{ ban} = \log_2 10 \approx 3.3219 \text{ bits}.

Every identity and inequality in this chapter is base-independent, because changing base multiplies every term by the same positive constant.

Example 1.3 (Surprisal of a lottery ticket). A lottery has $1{,}000{,}000$ equally likely tickets. How many bits of information is the announcement "ticket #472913 won", and how many is "a ticket with an even number won"?

Solution. The winning ticket has probability $p = 10^{-6}$ , so

I = -\log_2 10^{-6} = 6\log_2 10 \approx 19.93 \text{ bits}.

The second announcement has probability $\tfrac12$ and so carries $1$ bit. The two are consistent with additivity: telling you the parity ( $1$ bit) and then the identity among the $500{,}000$ tickets of that parity ( $\log_2 500{,}000 \approx 18.93$ bits) totals $19.93$ bits, exactly the surprisal of naming the ticket outright. □□

Pitfall. Surprisal is a property of the outcome; entropy is a property of the distribution. Asking "what is the information in this sentence?" is ambiguous until you say which ensemble the sentence was drawn from. A string of $100$ random digits has high surprisal under the uniform model and essentially none under a model that puts all its mass on that string.

Exercises for §1.1 →

1.2From Surprisal to Entropy: The Two Analytic Tools

Surprisal attaches a number to each outcome. To attach one number to the source, average:

H(X) = \mathbb{E}\bigl[I(X)\bigr] = \sum_x p(x)\bigl(-\log_2 p(x)\bigr).

That is entropy, formalised in the next section. Before studying it we install the two analytic tools that every proof in this chapter uses. Both are statements about the concavity of $\log$ , and it is worth seeing them once, cleanly, so that later arguments can be one line long.

Theorem 1.4 (Jensen's inequality). Let $\varphi$ be a concave function on an interval $J$ and let $X$ be a random variable taking finitely many values in $J$ . Then

\mathbb{E}\bigl[\varphi(X)\bigr] \le \varphi\bigl(\mathbb{E}[X]\bigr).

If $\varphi$ is strictly concave, equality holds if and only if $X$ is constant with probability $1$ . For convex $\varphi$ the inequality reverses.

Proof. Induct on the size $n$ of the support. For $n=1$ both sides agree. Suppose the claim holds for supports of size $n-1$ , and let $X$ take values $x_1,\dots,x_n$ with positive probabilities $p_1,\dots,p_n$ . Write $q_i = p_i/(1-p_n)$ for $i<n$ , so $\sum_{i<n} q_i = 1$ , and set $\mu = \sum_{i<n} q_i x_i$ . Concavity applied to the two-point combination $(1-p_n)\mu + p_n x_n$ gives

\varphi\Bigl(\sum_{i=1}^n p_i x_i\Bigr) = \varphi\bigl((1-p_n)\mu + p_n x_n\bigr) \ge (1-p_n)\varphi(\mu) + p_n \varphi(x_n),

and the induction hypothesis gives $\varphi(\mu) \ge \sum_{i<n} q_i\varphi(x_i)$ . Substituting,

\varphi\Bigl(\sum_i p_i x_i\Bigr) \ge (1-p_n)\sum_{i<n}q_i\varphi(x_i) + p_n\varphi(x_n) = \sum_i p_i\varphi(x_i).

For the equality case, strict concavity makes the two-point step strict unless $\mu = x_n$ , and the inductive step strict unless $x_1=\dots=x_{n-1}$ ; together these force all $x_i$ equal.∎

Intuition. A chord of a concave curve lies below the curve. Averaging the inputs and then bending ( $\varphi(\mathbb{E}X)$ ) always lands at or above bending and then averaging ( $\mathbb{E}\varphi(X)$ ). Since $\log$ is concave, "the log of an average is at least the average of the logs" — and that one sentence proves the information inequality, the bound $H \le \log|\mathcal{X}|$ , and the data processing inequality.

Figure 1.5. The chord of

\log_2

from

(1,0)

(4,2)

lies below the curve. At

x=2.5

— the average of the two endpoints — the curve reads

1.322

and the chord reads

1.000

; the

0.322

-bit gap is

\log_2\mathbb{E}[X]-\mathbb{E}[\log_2 X]

for

X

equal to

1

4

with probability

\tfrac12

each.

The second tool is a workhorse form of the same fact, tailored to ratios of non-negative numbers. It is what makes convexity arguments about relative entropy short.

Theorem 1.6 (Log-sum inequality). Let $a_1,\dots,a_n$ and $b_1,\dots,b_n$ be non-negative numbers, and write $a = \sum_i a_i$ , $b = \sum_i b_i$ . Then

\sum_{i=1}^n a_i \log_2\frac{a_i}{b_i} \ \ge\ a\log_2\frac{a}{b},

with the conventions $0\log\tfrac{0}{b} = 0$ and $a\log\tfrac{a}{0} = \infty$ for $a>0$ . Equality holds if and only if the ratio $a_i/b_i$ is the same for every $i$ .

Proof. Assume all $a_i,b_i>0$ ; terms with $a_i=0$ contribute nothing to either side, and a zero $b_i$ with $a_i>0$ makes the left side infinite. The function $t \mapsto t\log_2 t$ is strictly convex on $(0,\infty)$ , since its second derivative is $1/(t\ln 2) > 0$ . Apply Jensen's inequality in its convex form to the random variable taking value $t_i = a_i/b_i$ with probability $\beta_i = b_i/b$ :

\sum_i \beta_i\,t_i\log_2 t_i \ \ge\ \Bigl(\sum_i \beta_i t_i\Bigr)\log_2\Bigl(\sum_i \beta_i t_i\Bigr).

Now $\sum_i \beta_i t_i = \sum_i a_i/b = a/b$ , and $\beta_i t_i \log_2 t_i = (a_i/b)\log_2(a_i/b_i)$ . Multiplying through by $b$ gives exactly the claim. Strict convexity makes equality equivalent to the $t_i$ being constant.∎

Example 1.7 (Two pieces of logarithmic arithmetic). Convert $H = 1.75$ bits to nats, then evaluate $\sum_i a_i\log_2(a_i/b_i)$ for $a = (0.6,0.4)$ and $b = (0.3,0.7)$ and check it against the log-sum bound.

Solution. Bits to nats divides by $\log_2 e$ : $1.75/1.4427 \approx 1.213$ nats.

For the sum, $\log_2 2 = 1$ and $\log_2(0.4/0.7) = \log_2 0.5714 \approx -0.8074$ , so

0.6(1) + 0.4(-0.8074) \approx 0.600 - 0.323 = 0.277.

Here $a = b = 1$ , so the log-sum bound reads $\ge 1\cdot\log_2 1 = 0$ , and indeed $0.277 > 0$ . The inequality is strict because $a_1/b_1 = 2 \neq 0.571 = a_2/b_2$ . This instance is precisely the statement $D(a\|b) \ge 0$ , proved in general in the relative entropy sections. □□

Exercises for §1.2 →

1.3What the Measures Are For, and What They Are Not

The quantities of this chapter are not free-floating definitions; each is the exact answer to an operational question. Stating those answers now explains why the definitions look the way they do, even though the full proofs belong to later chapters on source and channel coding.

Theorem 1.8 (Kraft inequality). A prefix-free binary code with codeword lengths $\ell_1,\dots,\ell_m$ exists if and only if

\sum_{i=1}^m 2^{-\ell_i} \le 1.

Proof. ( $\Rightarrow$ ) Draw the infinite binary tree and let $\ell_{\max} = \max_i \ell_i$ . A codeword of length $\ell_i$ occupies a node at depth $\ell_i$ , and the prefix-free condition says no codeword node is an ancestor of another, so the sets of depth- $\ell_{\max}$ descendants of the codeword nodes are disjoint. The codeword of length $\ell_i$ has $2^{\ell_{\max}-\ell_i}$ such descendants and there are $2^{\ell_{\max}}$ nodes at that depth altogether, so $\sum_i 2^{\ell_{\max}-\ell_i} \le 2^{\ell_{\max}}$ , which is the claim.

( $\Leftarrow$ ) Sort the lengths $\ell_1 \le \dots \le \ell_m$ and assign to the $i$ -th codeword the first $\ell_i$ binary digits of $\sum_{j<i} 2^{-\ell_j}$ . The hypothesis keeps every partial sum below $1$ , and for $j<i$ the two partial sums differ by at least $2^{-\ell_j}$ , so the $j$ -th codeword is not a prefix of the $i$ -th.∎

Kraft is the bridge between distributions and codes: given lengths satisfying the inequality, $q(x) = 2^{-\ell(x)}$ is a sub-probability distribution, and conversely any distribution $q$ suggests the lengths $\ell(x) = \lceil \log_2 1/q(x)\rceil$ . Every statement about code lengths in this chapter is a statement about distributions in disguise.

Theorem 1.9 (Source coding theorem, one-shot form). Let $X$ have entropy $H(X)$ and let $L^{*}$ be the minimum expected length of a prefix-free binary code for $X$ . Then

H(X) \le L^{*} < H(X) + 1.

Proof. For the lower bound, let $\ell$ be any prefix-free code, put $c = \sum_x 2^{-\ell(x)} \le 1$ and $q(x) = 2^{-\ell(x)}/c$ . Then

\mathbb{E}[\ell(X)] - H(X) = \sum_x p(x)\log_2\frac{p(x)}{2^{-\ell(x)}} = D(p\|q) - \log_2 c,

which is non-negative because $D(p\|q)\ge 0$ by Gibbs' inequality and $\log_2 c \le 0$ .

For the upper bound take $\ell(x) = \lceil\log_2 1/p(x)\rceil$ . These lengths satisfy Kraft, since $2^{-\lceil\log_2 1/p(x)\rceil} \le p(x)$ and the $p(x)$ sum to $1$ , and $\ell(x) < \log_2 1/p(x) + 1$ , so the expected length is below $H(X)+1$ .∎

The trailing $+1$ is the rounding loss from insisting on whole-bit codewords; coding blocks of $n$ symbols at a time divides it by $n$ , which is why entropy is the true limit asymptotically. The channel side of the theory has a matching statement, which we quote without proof.

Theorem 1.10 (Noisy channel coding theorem (quoted)). For a discrete memoryless channel with transition law $p(y|x)$ , define the capacity

C = \max_{p(x)} I(X;Y).

Then for every rate $R<C$ there are codes of rate $R$ whose probability of decoding error tends to $0$ as the block length grows, and for every $R>C$ the error probability is bounded away from $0$ .

Note. The converse half of this theorem is within reach of this chapter: it follows from the data processing inequality and Fano's inequality, both stated and proved below. The achievability half — that good codes exist — rests on a random coding argument and the joint asymptotic equipartition property, and is out of scope here.

Intuition. Two numbers govern the whole enterprise. Entropy $H$ is how much you must say; capacity $C$ , a maximised mutual information, is how much can be heard. Shannon's separation principle says that as long as $H < C$ you may compress down to $H$ and then protect the result up to $C$ , losing nothing by doing the two jobs separately.

Example 1.11 (Sizing a source). A source emits symbols A, B, C with probabilities $0.5, 0.25, 0.25$ . Estimate the size of a compressed file of $1000$ symbols and exhibit a code that achieves it.

Solution. The entropy is

H = 0.5\log_2 2 + 0.25\log_2 4 + 0.25\log_2 4 = 0.5 + 0.5 + 0.5 = 1.5 \text{ bits/symbol},

so $1000$ symbols need about $1500$ bits, or $188$ bytes. The code $\text{A}\mapsto 0$ , $\text{B}\mapsto 10$ , $\text{C}\mapsto 11$ is prefix-free with expected length $0.5(1)+0.25(2)+0.25(2) = 1.5$ bits, meeting the bound exactly. Equality is possible here precisely because every probability is a power of $\tfrac12$ , so the ideal lengths $\log_2 1/p(x)$ are already integers and nothing is lost to rounding. □□

Pitfall. Information measures say nothing about meaning, value, or truth. A megabyte of cryptographic noise has more entropy than a megabyte of Shakespeare, and a perfectly reliable channel carrying lies has full capacity. Shannon's framework deliberately quantifies only the statistical difficulty of reproducing a symbol stream.

Exercises for §1.3 →

1.4Definition of Entropy

Entropy is the central quantity of information theory: the average surprisal of a source, the number of bits per symbol that an ideal compressor needs, and — by the characterisation below — the only function of a distribution that behaves the way a measure of uncertainty ought to. This section and the two that follow define it, establish its structural properties, and develop the habits needed to compute it.

Definition 1.12 (Shannon entropy). Let $X$ be a discrete random variable with values in a countable alphabet $\mathcal{X}$ and probability mass function $p$ . The entropy of $X$ is

H(X) = -\sum_{x \in \mathcal{X}} p(x)\log_2 p(x) = \mathbb{E}\Bigl[\log_2\frac{1}{p(X)}\Bigr] \quad\text{bits}.

When $\mathcal{X}$ is infinite the series may diverge, in which case we write $H(X) = \infty$ .

Notation. By convention $0\log 0 = 0$ , which is the limit of $t\log t$ as $t \downarrow 0$ . Outcomes of probability zero therefore contribute nothing, and the entropy of $X$ depends only on the list of positive probabilities — not on the alphabet from which they were drawn, not on their order, and not on the values the variable takes.

That last point deserves emphasis: $H(X)$ is a function of $p$ , not of $X$ . The notation $H(X)$ is traditional and convenient but slightly misleading; a fair coin labelled $\{0,1\}$ and a fair coin labelled $\{-10^6, \pi\}$ have the same entropy, $1$ bit. This is exactly what distinguishes entropy from variance, which is sensitive to the numerical values and is not defined at all for an unordered alphabet.

Intuition. Entropy is average surprise, and equivalently the expected number of yes/no questions an optimal questioner needs to identify the outcome. For a source over four equally likely symbols, two questions always suffice and never fewer: $H = 2$ . For the source with probabilities $\tfrac12, \tfrac14, \tfrac18, \tfrac18$ , the optimal strategy asks "is it the first symbol?" first and averages $1.75$ questions.

Example 1.13 (Entropy of a biased coin). Compute the entropy of a coin with $P(\text{heads}) = 0.9$ .

Solution.

H = -0.9\log_2 0.9 - 0.1\log_2 0.1 = 0.9(0.15200) + 0.1(3.32193) \approx 0.137 + 0.332 = 0.469 \text{ bits}.

Sanity check: the answer lies strictly between $0$ (a two-headed coin) and $1$ (a fair coin), as it must for a biased but not deterministic coin. Operationally, a long sequence of these flips can be compressed to about $469$ bits per thousand flips. □□

The characterisation below explains why this particular formula, rather than some other decreasing function of predictability, is the measure of uncertainty. Its content is that entropy is forced by a grouping axiom: it should not matter whether you reveal an outcome all at once or in stages.

Theorem 1.14 (Shannon's characterisation of entropy (proof sketched)). Let $H_n(p_1,\dots,p_n)$ be defined for every probability vector and suppose

$h_2(p, 1-p)$ is continuous in $p$ ,
$H_n(1/n,\dots,1/n)$ is increasing in $n$ , and
(grouping) for $p_1 = q_1 + q_2$ ,

H_n(q_1, q_2, p_2, \dots, p_{n-1}) = H_{n-1}(p_1, p_2,\dots,p_{n-1}) + p_1\,H_2\Bigl(\frac{q_1}{p_1}, \frac{q_2}{p_1}\Bigr).

Then $H_n(p_1,\dots,p_n) = -c\sum_i p_i\log_2 p_i$ for some constant $c > 0$ .

Proof. Sketch. Write $A(n) = H_n(1/n,\dots,1/n)$ . Repeatedly applying the grouping axiom to split a uniform distribution on $mn$ points into $m$ groups of $n$ gives $A(mn) = A(m) + A(n)$ , so $A$ is an additive, increasing function on the integers; the argument used for the surprisal characterisation gives $A(n) = c\log_2 n$ . Grouping then extends this from uniform distributions to rational probability vectors, by realising a vector with denominators $n$ as a grouping of the uniform distribution on $n$ points, and continuity (1) passes to arbitrary real vectors. The full bookkeeping is standard but long, and we do not reproduce it; the essential step is the one displayed above.∎

Remark. Several inequivalent axiom sets give the same conclusion, and none of them is the reason entropy matters. The decisive argument is operational: Theorem Source coding theorem, one-shot form says entropy is the minimum achievable description length, and no other functional has that property. Axioms explain the formula; coding theorems justify it.

Exercises for §1.4 →

1.5Properties of Entropy

Everything in this section is proved from the definition together with Jensen's inequality. Each item will be used repeatedly later.

Theorem 1.15 (Range of entropy). Let $X$ take values in a finite alphabet $\mathcal{X}$ . Then

0 \le H(X) \le \log_2|\mathcal{X}|.

The left equality holds if and only if $X$ is deterministic; the right equality holds if and only if $X$ is uniform on $\mathcal{X}$ .

Proof. Each term $-p(x)\log_2 p(x)$ is non-negative because $p(x) \in [0,1]$ makes $\log_2 p(x) \le 0$ , so $H(X)\ge 0$ . The sum vanishes only if every term does, i.e. every $p(x)$ is $0$ or $1$ , which means $X$ is deterministic.

For the upper bound apply Jensen's inequality to the concave function $\log_2$ and the random variable $1/p(X)$ :

H(X) = \mathbb{E}\Bigl[\log_2\frac{1}{p(X)}\Bigr] \le \log_2 \mathbb{E}\Bigl[\frac{1}{p(X)}\Bigr] = \log_2 \sum_{x: p(x)>0} 1 = \log_2 |\text{supp}(p)| \le \log_2|\mathcal{X}|.

Since $\log_2$ is strictly concave, the first inequality is an equality only when $1/p(X)$ is constant, i.e. $p$ is uniform on its support, and the second only when the support is all of $\mathcal{X}$ .∎

Intuition. Uncertainty is largest when you have no idea at all, and "no idea at all" means uniform. Entropy is bounded by the log of the number of possible outcomes, which is why an alphabet of $256$ symbols can never carry more than $8$ bits per symbol however cleverly it is used.

One special case of the entropy formula recurs so often that it gets its own symbol.

Figure 1.16. The binary entropy

h_2(p)

. It vanishes at the deterministic ends

p=0

and

p=1

, peaks at

h_2(\tfrac12)=1

bit, and is concave throughout — so a mixture of two coins is never more predictable than the mixture of their entropies.

Definition 1.17 (Binary entropy function). For $p \in [0,1]$ ,

h_2(p) = -p\log_2 p - (1-p)\log_2(1-p),

the entropy of a single bit that equals $1$ with probability $p$ . It satisfies $h_2(p) = h_2(1-p)$ , $h_2(0) = h_2(1) = 0$ , and $h_2(1/2) = 1$ .

Theorem 1.18 (Concavity of entropy). Regarded as a function of the probability vector $p$ on a fixed finite alphabet, $H$ is concave: for distributions $p_1, p_2$ and $\lambda \in [0,1]$ ,

H\bigl(\lambda p_1 + (1-\lambda)p_2\bigr) \ge \lambda H(p_1) + (1-\lambda)H(p_2).

Proof. The map $t\mapsto -t\log_2 t$ is concave on $[0,1]$ , since its second derivative is $-1/(t\ln 2) < 0$ . Entropy is the sum over $x$ of this concave function applied to the coordinate $p(x)$ , and a sum of concave functions of an affine argument is concave. Explicitly, for each $x$ ,

-\bigl(\lambda p_1(x)+(1-\lambda)p_2(x)\bigr)\log_2\bigl(\lambda p_1(x)+(1-\lambda)p_2(x)\bigr) \ge -\lambda p_1(x)\log_2 p_1(x) - (1-\lambda)p_2(x)\log_2 p_2(x),

and summing over $x$ gives the result.∎

Intuition. Mixing two sources cannot make the result more predictable than the average of the two, because a mixture hides which source produced each symbol — and that hidden label is itself uncertainty. The probabilistic reading is exact: if $Z$ picks source $1$ or $2$ and $X$ is drawn from the chosen source, then $H(X) \ge H(X|Z) = \lambda H(p_1)+(1-\lambda)H(p_2)$ , which is concavity restated.

Theorem 1.19 (Deterministic processing cannot increase entropy). For any function $f$ defined on the alphabet of $X$ ,

H(f(X)) \le H(X),

with equality if and only if $f$ is injective on the support of $p$ .

Proof. Let $Y = f(X)$ . Since $Y$ is determined by $X$ we have $H(Y|X) = 0$ , so the chain rule (Theorem Chain rule for entropy) gives

H(X) = H(X,Y) = H(Y) + H(X|Y) \ge H(Y),

because conditional entropy is non-negative. Equality forces $H(X|Y) = 0$ , i.e. $X$ is determined by $Y$ almost surely, which for a deterministic $f$ means $f$ is injective on the support.∎

Pitfall. The inequality $H(f(X)) \le H(X)$ needs $f$ to be deterministic. If you add independent noise — $Y = X \oplus N$ with $N$ a random bit — then $H(Y)$ can exceed $H(X)$ . Random processing can create entropy; it just cannot create information about $X$ , which is the content of the data processing inequality.

Example 1.20 (Where entropy sits for small alphabets). For which $p$ does a three-symbol source with probabilities $(p, p, 1-2p)$ have maximal entropy, and what is the maximum?

Solution. By Theorem Range of entropy the maximum over all distributions on three symbols is $\log_2 3 \approx 1.585$ , attained only at the uniform distribution. The family $(p,p,1-2p)$ contains the uniform distribution at $p = 1/3$ , so the maximum over the family is $\log_2 3$ at $p = 1/3$ .

Checking directly: $H(p) = -2p\log_2 p - (1-2p)\log_2(1-2p)$ , and $\frac{dH}{dp} = 2\log_2\frac{1-2p}{p}$ , which vanishes exactly when $1-2p = p$ , i.e. $p = 1/3$ . The two routes agree, and the derivative test confirms it is a maximum since $H'$ changes from positive to negative there. □□

Exercises for §1.5 →

1.6Calculating Entropy

Method 1.21 (Computing an entropy from a pmf).

List every outcome with positive probability and its probability $p(x)$ .
Compute the surprisal $-\log_2 p(x)$ of each. (Useful values: $-\log_2 \tfrac12 = 1$ , $-\log_2\tfrac14 = 2$ , $-\log_2 0.1 \approx 3.3219$ , $-\log_2 0.3 \approx 1.7370$ , $-\log_2 0.9 \approx 0.1520$ .)
Form the weighted sum $H = \sum_x p(x)\bigl(-\log_2 p(x)\bigr)$ .
Check $0 \le H \le \log_2 k$ , where $k$ is the number of outcomes with positive probability, and check that $H$ is well below $\log_2 k$ when the distribution is visibly lopsided.

A short table of reference values is worth memorising, because most exercises reduce to one of them.

| Distribution | Probabilities | Entropy (bits) |

|---|---|---|

| Deterministic | $(1)$ | $0$ |

| Fair coin | $(\tfrac12,\tfrac12)$ | $1$ |

| Biased coin | $(0.9, 0.1)$ | $\approx 0.469$ |

| Uniform on $4$ | $(\tfrac14,\tfrac14,\tfrac14,\tfrac14)$ | $2$ |

| Dyadic | $(\tfrac12,\tfrac14,\tfrac18,\tfrac18)$ | $1.75$ |

| Uniform on $n$ | $(1/n,\dots,1/n)$ | $\log_2 n$ |

Example 1.22 (A four-symbol source). Symbols $A,B,C,D$ occur with probabilities $0.4, 0.3, 0.2, 0.1$ . Find $H$ .

Solution. The surprisals are $1.3219$ , $1.7370$ , $2.3219$ , $3.3219$ bits. Weighting,

H \approx 0.4(1.3219) + 0.3(1.7370) + 0.2(2.3219) + 0.1(3.3219) = 0.5288 + 0.5211 + 0.4644 + 0.3322 = 1.846 \text{ bits}.

Sanity check: $0 < 1.846 < \log_2 4 = 2$ , with the gap from $2$ reflecting the mild non-uniformity. □□

Infinite alphabets need a closed form rather than a table. The geometric distribution is the standard example, and its entropy is computable exactly.

Proposition 1.23 (Entropy of a geometric distribution). Let $P(X = k) = (1-p)^{k-1}p$ for $k = 1,2,\dots$ , with $p\in(0,1)$ . Then

H(X) = \frac{h_2(p)}{p} \quad\text{bits},

where $h$ is the binary entropy function.

Proof. Write $q = 1-p$ . Then

H(X) = -\sum_{k\ge 1} q^{k-1}p\,\log_2\bigl(q^{k-1}p\bigr) = -\sum_{k\ge 1} q^{k-1}p\bigl[(k-1)\log_2 q + \log_2 p\bigr].

The second piece sums to $-\log_2 p$ since the probabilities total $1$ . For the first, $\sum_{k\ge1}(k-1)q^{k-1}p = \mathbb{E}[X]-1 = 1/p - 1 = q/p$ . Hence

H(X) = -\frac{q}{p}\log_2 q - \log_2 p = \frac{-q\log_2 q - p\log_2 p}{p} = \frac{h_2(p)}{p}.

∎

Example 1.24 (Reading the geometric formula). How many bits are needed on average to encode the number of fair coin flips until the first head?

Solution. Here $p = 1/2$ , so $H = h_2(1/2)/(1/2) = 1/0.5 = 2$ bits. The unary code — $k-1$ zeros followed by a one — has expected length $\mathbb{E}[X] = 2$ bits and is therefore optimal, which we can confirm against the source coding theorem: $H = 2 \le L^* = 2 < 3$ . Equality is possible because every probability $2^{-k}$ is dyadic. □□

Intuition. Two forces set the size of $H$ : how many outcomes are in play (which raises the ceiling $\log_2 k$ ) and how unevenly the mass is spread (which pushes $H$ below the ceiling). A distribution over a million symbols with $99.9\%$ of its mass on one of them has entropy well under a bit.

Exercises for §1.6 →

1.7Joint Entropy

A source rarely emits one symbol in isolation. Joint entropy extends $H$ to a vector of random variables and is the quantity that the rest of this chapter, and the chapters that follow it, are built on: conditional entropy, mutual information, and entropy rate are all differences of joint entropies.

Definition 1.25 (Joint entropy). Let $(X,Y)$ be a pair of discrete random variables with joint pmf $p(x,y)$ . Their joint entropy is

H(X,Y) = -\sum_{x,y} p(x,y)\log_2 p(x,y) = \mathbb{E}\Bigl[\log_2\frac{1}{p(X,Y)}\Bigr].

More generally, for $X_1,\dots,X_n$ ,

H(X_1,\dots,X_n) = -\sum_{x_1,\dots,x_n} p(x_1,\dots,x_n)\log_2 p(x_1,\dots,x_n).

There is nothing new here: $H(X,Y)$ is the ordinary entropy of the single random variable $(X,Y)$ taking values in $\mathcal{X}\times\mathcal{Y}$ . Everything proved for $H$ therefore applies at once — it is non-negative, it is bounded by $\log_2$ of the size of the joint support, and it is concave in the joint distribution.

Intuition. Treat the pair as one bigger die. $H(X,Y)$ is the average surprise of seeing both coordinates at once, or equivalently the number of bits a compressor needs per pair. If the two coordinates are related, many cells of the table are empty or nearly so, and the pair is cheaper to describe than the two coordinates separately.

Example 1.26 (Independent versus coupled bits). Compute $H(X,Y)$ for (a) two independent fair bits, and (b) the pair with $p(0,0) = p(1,1) = 0.4$ , $p(0,1) = p(1,0) = 0.1$ .

Solution. (a) All four cells have probability $\tfrac14$ , so $H(X,Y) = \log_2 4 = 2$ bits.

(b) Two cells hold $0.4$ and two hold $0.1$ :

H(X,Y) = -2(0.4)\log_2 0.4 - 2(0.1)\log_2 0.1 = 0.8(1.3219) + 0.2(3.3219) \approx 1.058 + 0.664 = 1.722 \text{ bits}.

Both marginals are fair bits in each case, so both pairs have $H(X)+H(Y) = 2$ . The coupled pair costs $1.722$ bits rather than $2$ — the $0.278$ -bit saving is exactly the mutual information we compute later. □□

Pitfall. To evaluate $H(X,Y)$ you must use the joint probabilities $p(x,y)$ , never the product $p(x)p(y)$ of the marginals. Substituting the product silently computes $H(X)+H(Y)$ , which is an upper bound and is correct only under independence.

Exercises for §1.7 →

1.8Joint Entropy Against Its Marginals

Two bounds sandwich the joint entropy between the largest marginal and the sum of the marginals. The lower bound says adding a variable never helps; the upper bound — subadditivity — says dependence always saves.

Theorem 1.27 (Subadditivity and monotonicity). For any pair of discrete random variables,

\max\bigl(H(X), H(Y)\bigr) \ \le\ H(X,Y) \ \le\ H(X) + H(Y).

The left equality holds iff one variable is a deterministic function of the other (specifically $H(X,Y) = H(X)$ iff $Y = f(X)$ almost surely); the right equality holds iff $X$ and $Y$ are independent.

Proof. Lower bound. $X$ is a function of the pair $(X,Y)$ , so Theorem Deterministic processing cannot increase entropy gives $H(X) \le H(X,Y)$ ; the same applies to $Y$ . Equality $H(X,Y) = H(X)$ requires that $(X,Y)$ be recoverable from $X$ , i.e. $Y$ is determined by $X$ .

Upper bound. Compute the difference directly:

H(X)+H(Y)-H(X,Y) = \sum_{x,y} p(x,y)\log_2\frac{p(x,y)}{p(x)p(y)} = D\bigl(p(x,y)\,\big\|\,p(x)p(y)\bigr) \ge 0

by Gibbs' inequality, since $p(x)p(y)$ is a probability distribution on $\mathcal{X}\times\mathcal{Y}$ . Gibbs' equality case forces $p(x,y) = p(x)p(y)$ everywhere, i.e. independence.

(To see the first equality, expand $\log_2 p(x)$ using $\sum_y p(x,y) = p(x)$ : $H(X) = -\sum_{x,y}p(x,y)\log_2 p(x)$ , and similarly for $Y$ .)∎

Intuition. Describing $X$ and $Y$ separately costs $H(X)+H(Y)$ bits. Describing them together can only be cheaper, because a joint description can exploit the fact that some combinations never occur. The saving is the mutual information, and it is zero exactly when there is nothing to exploit.

Example 1.28 (When the joint collapses to a marginal). Let $X$ be uniform on $\{0,1,2,3\}$ and $Y = X \bmod 2$ . Verify both bounds.

Solution. $H(X) = \log_2 4 = 2$ and $H(Y) = 1$ , since $Y$ is a fair bit. The joint puts mass $\tfrac14$ on each of $(0,0),(1,1),(2,0),(3,1)$ and zero elsewhere, so $H(X,Y) = \log_2 4 = 2$ bits.

Lower bound: $\max(2,1) = 2 = H(X,Y)$ — equality, exactly as predicted, because $Y = f(X)$ . Upper bound: $H(X)+H(Y) = 3 > 2$ — strict, because the variables are as dependent as possible. The shortfall $3 - 2 = 1$ bit is $I(X;Y) = H(Y)$ : knowing $X$ resolves $Y$ entirely. □□

The upper bound extends to any number of variables, and the proof is a clean induction once the chain rule is available.

Corollary 1.29 (Independence bound). For any $X_1,\dots,X_n$ ,

H(X_1,\dots,X_n) \le \sum_{i=1}^n H(X_i),

with equality if and only if the $X_i$ are mutually independent.

Proof. By the chain rule, $H(X_1,\dots,X_n) = \sum_i H(X_i \mid X_1,\dots,X_{i-1})$ , and each term satisfies $H(X_i \mid X_1,\dots,X_{i-1}) \le H(X_i)$ by Theorem Conditioning reduces entropy. Summing gives the bound. Equality requires every term to be tight, i.e. $X_i$ independent of $(X_1,\dots,X_{i-1})$ for each $i$ , which is exactly mutual independence.∎

Exercises for §1.8 →

1.9The Chain Rule

The chain rule is the single most used identity in the subject. It is the entropy translation of the probability factorisation $p(x,y) = p(x)p(y|x)$ , and it turns every joint quantity into a telescoping sum of one-symbol conditional quantities.

Theorem 1.30 (Chain rule for entropy). For discrete random variables $X_1,\dots,X_n$ ,

H(X_1, X_2, \dots, X_n) = \sum_{i=1}^{n} H\bigl(X_i \mid X_1, \dots, X_{i-1}\bigr),

where the $i=1$ term is $H(X_1)$ . In particular $H(X,Y) = H(X) + H(Y|X) = H(Y) + H(X|Y)$ .

Proof. For the two-variable case, factor the joint pmf and split the logarithm:

H(X,Y) = -\sum_{x,y} p(x,y)\log_2\bigl(p(x)p(y|x)\bigr) = -\sum_{x,y}p(x,y)\log_2 p(x) - \sum_{x,y}p(x,y)\log_2 p(y|x).

The first sum is $-\sum_x p(x)\log_2 p(x) = H(X)$ , and the second is $H(Y|X)$ by definition. Symmetry of $H(X,Y)$ in its arguments gives the other factorisation.

For general $n$ , induct. Applying the two-variable rule with $X = (X_1,\dots,X_{n-1})$ and $Y = X_n$ ,

H(X_1,\dots,X_n) = H(X_1,\dots,X_{n-1}) + H(X_n \mid X_1,\dots,X_{n-1}),

and the induction hypothesis expands the first term. Alternatively, write $p(x_1,\dots,x_n) = \prod_i p(x_i|x_1,\dots,x_{i-1})$ , take $-\log_2$ , and average.∎

Intuition. Describe the sequence one symbol at a time. The first symbol costs $H(X_1)$ bits; after that, each symbol costs only what is still unknown about it given everything already sent. Total cost is the sum — and it is the same total whatever order you choose to send them in, which is a genuinely useful degree of freedom.

Corollary 1.31 (Conditional chain rule). For discrete $X$ , $Y$ , $Z$ ,

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

Proof. Apply the two-variable chain rule to the conditional distribution given $Z = z$ , obtaining $H(X,Y|Z=z) = H(X|Z=z) + H(Y|X,Z=z)$ , then average over $z$ with weights $p(z)$ . Each term averages to the corresponding conditional entropy by definition.∎

Example 1.32 (Chain rule in both directions). Suppose $H(X) = 2$ , $H(Y) = 3$ and $H(X,Y) = 4$ bits. Find $H(Y|X)$ and $H(X|Y)$ , and say which variable is more informative about the other.

Solution. Rearranging the chain rule, $H(Y|X) = H(X,Y) - H(X) = 4 - 2 = 2$ bits and $H(X|Y) = H(X,Y) - H(Y) = 4 - 3 = 1$ bit.

The reductions are what matter: $H(X) - H(X|Y) = 1$ and $H(Y) - H(Y|X) = 1$ . They agree, as they must — both equal $I(X;Y) = 1$ bit. So neither variable is more informative about the other; mutual information is symmetric even though the conditional entropies differ. The asymmetry in $H(Y|X) = 2$ versus $H(X|Y) = 1$ reflects only that $Y$ was more uncertain to begin with. □□

Pitfall. Do not read " $H(X|Y) < H(Y|X)$ " as " $Y$ tells you more about $X$ than $X$ does about $Y$ ". Conditional entropies measure what is left over, and are not comparable across variables with different marginal entropies. The symmetric measure of shared information is $I(X;Y)$ .

Exercises for §1.9 →

1.10Definition of Conditional Entropy

Conditional entropy measures how much uncertainty about $Y$ survives once $X$ has been observed. It is the information-theoretic counterpart of residual variance in regression, and it is the quantity that turns entropy from a static measure of a source into a measure of prediction difficulty.

There are two objects here, and keeping them apart prevents most of the errors people make with conditional entropy.

Definition 1.33 (Conditional entropy). For a fixed value $x$ with $p(x)>0$ , the entropy of the conditional distribution $p(\cdot\mid x)$ is

H(Y \mid X = x) = -\sum_y p(y|x)\log_2 p(y|x).

The conditional entropy of $Y$ given $X$ is its average over $x$ :

H(Y\mid X) = \sum_x p(x)\,H(Y\mid X = x) = -\sum_{x,y}p(x,y)\log_2 p(y|x) = \mathbb{E}\Bigl[\log_2\frac{1}{p(Y|X)}\Bigr].

$H(Y\mid X=x)$ is a function of $x$ — a different number for each observation. $H(Y\mid X)$ is a single number, the $p(x)$ -weighted average. The theorems of this chapter are about the average; none of them holds value by value.

Note. By the chain rule, $H(Y|X) = H(X,Y)-H(X)$ , and in practice this is usually the fastest route to a number: build the joint, take the marginal, subtract. The definitional form is the one to use when the conditional distributions are what you are given, as with a channel specified by its transition probabilities.

Intuition. After looking at $X$ , how many more bits do you still need to pin down $Y$ ? If $X$ is the month and $Y$ tomorrow's temperature, $H(Y|X)$ is the uncertainty left after the calendar has told you what it can. A perfect predictor drives it to $0$ ; a useless one leaves it at $H(Y)$ .

Example 1.34 (An asymmetric channel). Let $X$ be a fair bit. If $X=0$ then $Y=0$ with certainty; if $X=1$ then $Y$ is an independent fair bit. Find $H(Y|X)$ , $H(X,Y)$ , $H(Y)$ and $H(X|Y)$ .

Solution. Value by value: $H(Y|X{=}0) = 0$ because $Y$ is deterministic there, and $H(Y|X{=}1) = h_2(1/2) = 1$ . Averaging,

H(Y|X) = \tfrac12(0)+\tfrac12(1) = 0.5 \text{ bits}.

The joint pmf is $p(0,0)=\tfrac12$ , $p(1,0)=\tfrac14$ , $p(1,1)=\tfrac14$ , so $H(X,Y) = \tfrac12(1)+\tfrac14(2)+\tfrac14(2) = 1.5$ bits. Since $H(X)=1$ , the chain rule confirms $H(Y|X)=1.5-1=0.5$ .

Going the other way: $P(Y{=}0)=\tfrac34$ and $P(Y{=}1)=\tfrac14$ , so $H(Y) = h_2(1/4) \approx 0.811$ bits and $H(X|Y) = H(X,Y)-H(Y) \approx 1.5-0.811 = 0.689$ bits.

Sanity check: both conditional entropies are non-negative and each is below the corresponding marginal ( $0.5 < 0.811$ and $0.689 < 1$ ), and the two reductions agree: $H(Y)-H(Y|X) \approx 0.311$ and $H(X)-H(X|Y) \approx 0.311$ . That common value is $I(X;Y)$ . □□

Example 1.35 (The deterministic extreme). If $Y = X$ exactly, then given $X=x$ the variable $Y$ is a point mass, so $H(Y|X=x)=0$ for every $x$ and hence $H(Y|X)=0$ . More generally $H(Y|X)=0$ if and only if $Y$ is a deterministic function of $X$ with probability $1$ .

Solution. One direction is the computation above. Conversely, $H(Y|X)=0$ forces $H(Y|X=x)=0$ for every $x$ with $p(x)>0$ , since the average of non-negative numbers vanishes only when each does; and an entropy vanishes only for a point mass (Theorem Range of entropy). So for each such $x$ there is a value $f(x)$ with $p(f(x)|x)=1$ , and $Y=f(X)$ almost surely. □□

Exercises for §1.10 →

1.11Conditioning Reduces Entropy, and Fano's Inequality

Theorem 1.36 (Conditioning reduces entropy). For any discrete $X$ , $Y$ ,

0 \le H(Y\mid X) \le H(Y),

with $H(Y|X)=H(Y)$ if and only if $X$ and $Y$ are independent. More generally, conditioning on more can only help:

H(Y \mid X, Z) \le H(Y\mid X).

Proof. Non-negativity is immediate, since $H(Y|X)$ is an average of entropies and each is non-negative. For the upper bound, subadditivity (Theorem Subadditivity and monotonicity) gives $H(X,Y)\le H(X)+H(Y)$ , and the chain rule rewrites the left side as $H(X)+H(Y|X)$ ; cancelling $H(X)$ leaves $H(Y|X)\le H(Y)$ . The equality case is the equality case of subadditivity, namely independence.

For the second claim, apply the first to the conditional distributions given $Z=z$ : $H(Y|X,Z=z)\le H(Y|Z=z)$ holds for each $z$ . Averaging over $z$ gives $H(Y|X,Z)\le H(Y|Z)$ ; relabelling the roles of $X$ and $Z$ gives the stated form.∎

Pitfall. "Conditioning reduces entropy" is a statement about the average $H(Y|X)$ , not about individual values. It is entirely possible that $H(Y\mid X=x) > H(Y)$ for some particular $x$ : a specific observation can leave you more confused than you were. Concretely, let $P(X{=}a)=0.8$ with $P(Y{=}1\mid X{=}a)=1$ , and $P(X{=}b)=0.2$ with $P(Y{=}1\mid X{=}b)=\tfrac12$ . Then $P(Y{=}1)=0.8(1)+0.2(0.5)=0.9$ , so $H(Y)=h_2(0.9)\approx 0.469$ , while $H(Y\mid X{=}b)=1 > H(Y)$ . The average is safe: $H(Y\mid X)=0.8(0)+0.2(1)=0.2 \le 0.469$ .

Intuition. Data can only help on average. A measurement that turns out to be misleading is always possible, but the ensemble of measurements you might have made cannot, in aggregate, make you worse off — because the prior is itself the average of the posteriors.

The most important consequence of conditional entropy is a quantitative link between uncertainty and guessing error. If $H(Y|X)$ is large, no estimator of $Y$ from $X$ can be reliable. Fano's inequality makes this precise and is the engine of every converse in information theory.

Theorem 1.37 (Fano's inequality). Let $Y$ take values in a finite alphabet $\mathcal{Y}$ , let $X$ be any random variable, and let $\hat Y = g(X)$ be any estimator of $Y$ computed from $X$ . Write $P_e = P(\hat Y \neq Y)$ . Then

H(Y \mid X) \ \le\ h_2(P_e) + P_e \log_2\bigl(|\mathcal{Y}| - 1\bigr) \ \le\ 1 + P_e\log_2|\mathcal{Y}|.

Consequently

P_e \ \ge\ \frac{H(Y\mid X) - 1}{\log_2 |\mathcal{Y}|}.

Proof. Introduce the error indicator $E = \mathbf{1}\{\hat Y \neq Y\}$ , a random variable determined by $(Y,\hat Y)$ . Expand $H(E,Y\mid \hat Y)$ with the conditional chain rule in two ways:

H(E,Y\mid\hat Y) = \underbrace{H(E\mid \hat Y)}_{\le\, h_2(P_e)} + H(Y\mid E,\hat Y) = \underbrace{H(Y\mid\hat Y)}_{\text{what we want}} + \underbrace{H(E\mid Y,\hat Y)}_{=\,0},

the last term vanishing because $E$ is a function of $(Y,\hat Y)$ , and the first being at most $H(E) = h_2(P_e)$ since conditioning reduces entropy.

For the middle term, split on the value of $E$ :

H(Y\mid E,\hat Y) = P(E{=}0)\,H(Y\mid \hat Y, E{=}0) + P(E{=}1)\,H(Y\mid\hat Y,E{=}1).

Given $E=0$ we have $Y=\hat Y$ , so that entropy is $0$ . Given $E=1$ and $\hat Y = \hat y$ , the variable $Y$ ranges over the $|\mathcal{Y}|-1$ values other than $\hat y$ , so its entropy is at most $\log_2(|\mathcal{Y}|-1)$ . Hence $H(Y|E,\hat Y) \le P_e\log_2(|\mathcal Y|-1)$ and

H(Y\mid\hat Y) \le h_2(P_e) + P_e\log_2(|\mathcal Y|-1).

Finally, since $\hat Y = g(X)$ is a function of $X$ , conditioning on $X$ is at least as informative as conditioning on $\hat Y$ : $H(Y\mid X) = H(Y\mid X,\hat Y) \le H(Y\mid \hat Y)$ , the equality because $\hat Y$ adds nothing to $X$ and the inequality because conditioning reduces entropy. The weaker second form follows from $h_2(P_e)\le 1$ and $\log_2(|\mathcal Y|-1) \le \log_2|\mathcal Y|$ , and rearranging gives the bound on $P_e$ .∎

Intuition. Fano says uncertainty is a floor on error. If, after seeing everything you get to see, one bit of uncertainty about a binary $Y$ remains, then no decision rule can do better than coin-flipping. Turned around: a decoder that is nearly always right is proof that almost no conditional entropy was left.

Example 1.38 (Fano in action). A message $Y$ is uniform on $256$ possibilities. After a noisy observation $X$ , the residual uncertainty is $H(Y|X) = 4$ bits. What does Fano guarantee about the error probability of the best possible decoder?

Solution. With $|\mathcal Y| = 256$ so $\log_2|\mathcal Y| = 8$ , the weak form gives

P_e \ \ge\ \frac{H(Y|X)-1}{\log_2|\mathcal Y|} = \frac{4-1}{8} = 0.375.

So every decoder errs at least $37.5\%$ of the time. The sharper form $4 \le h_2(P_e) + P_e\log_2 255$ gives a slightly better bound: at $P_e = 0.42$ the right side is $0.9815 + 0.42(7.994) \approx 4.34 \ge 4$ , while at $P_e = 0.375$ it is $0.9544+2.998 \approx 3.95 < 4$ , so in fact $P_e \gtrsim 0.38$ . Sanity check: $H(Y)=8$ bits and $H(Y|X)=4$ means the observation conveyed $I(X;Y)=4$ bits — half the message — and half a message is not enough to decode it. □□

Exercises for §1.11 →

1.12Chain Rules and the Algebra of Conditioning

Every identity in this chapter survives the addition of a conditioning variable. That is worth stating as a principle, because it lets you re-derive conditional versions of results rather than memorising them.

Proposition 1.39 (Conditioning principle). Let $\mathcal{R}$ be any identity or inequality between information measures that holds for all distributions. Then the statement obtained by appending " $\mid Z$ " to every measure in $\mathcal{R}$ also holds.

Proof. Apply $\mathcal{R}$ to the conditional distribution given $Z=z$ , which is a genuine probability distribution for each $z$ with $p(z)>0$ . This yields the statement with every measure replaced by its "given $Z=z$ " version. Each conditional measure given $Z$ is by definition the $p(z)$ -average of these, and averaging preserves both equalities and inequalities of a fixed direction.∎

Theorem 1.40 (Chain rule, conditional form). For $X_1,\dots,X_n$ and any $Z$ ,

H(X_1,\dots,X_n \mid Z) = \sum_{i=1}^n H\bigl(X_i \mid X_1,\dots,X_{i-1}, Z\bigr).

Proof. Immediate from the chain rule (Theorem Chain rule for entropy) and the conditioning principle.∎

Pitfall. The conditioning principle does not say that conditioning preserves the value of a quantity, and in particular it does not say that conditioning reduces mutual information. It is a fact that $H(Y|X,Z)\le H(Y|X)$ , but $I(X;Y\mid Z)$ can be either larger or smaller than $I(X;Y)$ — see the discussion of conditional mutual information in the next part. Conditioning on a common effect creates dependence where none existed.

Example 1.41 (Expanding a three-variable joint entropy). A system has $H(X) = 1.5$ , $H(Y|X)=0.8$ , $H(Z|X,Y)=0.5$ bits. Find $H(X,Y,Z)$ , and give an upper bound on $H(Z)$ .

Solution. The chain rule expands directly in the given order:

H(X,Y,Z) = H(X)+H(Y|X)+H(Z|X,Y) = 1.5+0.8+0.5 = 2.8 \text{ bits}.

For $H(Z)$ , conditioning reduces entropy gives $H(Z) \ge H(Z|X,Y) = 0.5$ , which is a lower bound; the requested upper bound comes from monotonicity, $H(Z)\le H(X,Y,Z)=2.8$ bits. Both are attainable in principle: $H(Z)=0.5$ when $Z$ is independent of $(X,Y)$ , and $H(Z)=2.8$ only if $(X,Y)$ is a function of $Z$ . □□

Summary. The core identities so far, all proved above:

H(X,Y) = H(X)+H(Y|X), \qquad 0\le H(Y|X)\le H(Y) \le \log_2|\mathcal Y|,

H(X_1,\dots,X_n)=\sum_i H(X_i\mid X_{<i}) \le \sum_i H(X_i),

with equality in the last display exactly under mutual independence, and Fano's inequality $H(Y|X) \le h_2(P_e)+P_e\log_2(|\mathcal Y|-1)$ linking residual entropy to unavoidable error.

Exercises for §1.12 →

Common Mistakes

Confusing information with meaning or importance. Entropy measures statistical unpredictability. A random digit string can have maximal entropy and no significance whatsoever.
Reading a surprisal as an entropy. $-\log_2 p(x)$ is attached to one outcome; $H(X)$ is its average. The rare outcome of a near-deterministic source has enormous surprisal while the source itself has almost no entropy.
Forgetting to fix a base. Mixing $\log_2$ and $\ln$ in one calculation produces answers off by the factor $\ln 2 \approx 0.693$ . Fix the base at the start and state the unit with every number.
Treating entropy as a property of a particular string. Entropy belongs to a distribution; the individual-string analogue is Kolmogorov complexity, a different and uncomputable quantity.
**Expecting a symbol code to reach $H$ exactly.** The gap in $H \le L^{*} < H+1$ is real and closes only when the probabilities are dyadic, or in the limit of long blocks.
Quoting capacity as a property of the input. $C = \max_{p(x)} I(X;Y)$ maximises over inputs; it is a property of the *channel*.
Dropping the minus sign. $\sum p\log p$ is negative; entropy is its negative. If your answer is negative, you dropped the sign.
**Leaving $0\log 0$ undefined in code.** Mathematically it is $0$ ; in a program it is `NaN`. Guard the zero-probability terms explicitly.
**Confusing the entropy of $p$ with a statistic of a sample.** $H$ is a functional of the distribution. What you compute from a finite sample is an *estimate*, and the plug-in estimate is biased downwards.
Assuming the maximum entropy on an alphabet is always attained. It is — at the uniform distribution — but only when the whole alphabet is in the support. A distribution supported on $3$ of $8$ symbols is capped at $\log_2 3$ , not $3$ .
Thinking entropy measures spread in the numerical sense. Relabelling the outcomes changes the variance and leaves the entropy untouched.
Using the single-symbol entropy for a source with memory. That is an upper bound on the true per-symbol cost; the entropy rate of the final sections is the correct quantity.
**Writing $H(X,Y) = H(X)+H(Y)$ unconditionally.** That is the independence case only; in general the sum is an upper bound.
Confusing joint entropy with mutual information. $H(X,Y)$ is the total; $I(X;Y) = H(X)+H(Y)-H(X,Y)$ is the overlap.
**Assuming the joint support is the full product $\mathcal{X}\times\mathcal{Y}$ . ** Dependence empties cells, and $H(X,Y) \le \log_2(\text{number of occupied cells})$ can be far below $\log_2(|\mathcal{X}||\mathcal{Y}|)$ .
Reversing the chain rule. It is $H(X,Y) = H(X) + H(Y|X)$ , never $H(X) + H(X|Y)$ . Check that the conditioning variable is the one already "paid for".
Expanding in an order that makes life hard. The chain rule holds in every order; choose the one whose conditionals you actually know.
Forgetting that the chain rule conditions gracefully. Every identity here remains true with an extra $\mid Z$ attached to every term.
**Believing $H(Y|X)$ can be negative.** It is an average of entropies and so is always $\ge 0$ . (Its continuous analogue, conditional *differential* entropy, genuinely can be negative — see the final section.)
**Confusing $H(Y|X)$ with $I(X;Y)$ . ** The first is what is left; the second is what was removed. They sum to $H(Y)$ .
**Computing $H(Y|X)$ from marginals.** You need $p(y|x)$ or the joint. No function of $p(x)$ and $p(y)$ alone determines $H(Y|X)$ .
**Generalising from a single $x$ . ** $H(Y|X=x)$ may exceed $H(Y)$ ; only the average cannot.
**Reading $H(Y|X)=0$ as "every $x$ determines $y$ ".** It means that for $p$ -almost every $x$ the conditional law is a point mass; values of probability zero are unconstrained.
Applying Fano without checking the alphabet. The bound involves $\log_2(|\mathcal Y|-1)$ ; for a binary $Y$ that term vanishes and Fano reduces to $H(Y|X)\le h_2(P_e)$ , which is much sharper than the generic form.

About the practice questions. They check that you can carry out this chapter's computations correctly, and each one is graded on a single answer. They are not proof exercises: working through them confirms the mechanics, not that you could prove the results yourself. For that, re-read the statements above and try to reconstruct their proofs with the page closed.

Mutual Information and Relative Entropy →

Helpful?