Last modified: 2026-11-07 21:35:35 (PST)
This page builds on the definitions of entropy, cross-entropy and Kullback–Leibler divergence in Probability for Data Science.
Definition 1 (Surprisal) The surprisal of a value \(x\) of a discrete random variable \(X\) with \(\mathbb{P}(X=x) > 0\) is
\[s(x) \stackrel{\text{def}}{=}-\log \mathbb{P}(X=x).\]
With base-2 logarithms, surprisal is also called the Shannon information content of the value \(x\) (MacKay 2003, sec. 2.4).
Definition 2 (Bit (shannon)) A bit, also called a shannon (symbol Sh) (International Electrotechnical Commission 2008), is the unit of information when the logarithm in surprisal, and in every quantity built from it, has base \(2\).
One bit is the surprisal of a value with probability \(1/2\): for a value \(x\) of a discrete random variable \(X\),
\[ \begin{aligned} s(x) = 1 \text{ bit} &\iff -\log_2 \mathbb{P}(X=x) = 1\\ &\iff \mathbb{P}(X=x) = 2^{-1} = \tfrac{1}{2}. \end{aligned} \]
In words, a bit is the surprisal of the outcome of one binary trial whose two outcomes are equally likely, such as one toss of a fair coin.
Example 1 (Counting bits with fair coins) One toss of a fair coin has \(2\) equally likely outcomes, and one binary digit is enough to record which one happened. Two tosses have \(4\) outcomes, and two binary digits record them. In general, \(k\) tosses have \(n = 2^k\) equally likely outcomes, and \(k = \log_2 n\) binary digits record them.
Each of those \(n\) outcomes has probability \(p = 1/n\), so
\[ \begin{aligned} k &= \log_2 n \\ &= \log_2 \frac{1}{p} \\ &= -\log_2 p, \end{aligned} \]
which is the surprisal of the outcome, in bits.
Ten tosses that all land heads have probability \(2^{-10}\), so
\[ \begin{aligned} s(\text{ten heads}) &= -\log_2 2^{-10} \\ &= 10 \text{ bits}. \end{aligned} \]
Theorem 1 (Surprisal as a logarithm to base one half) For a value \(x\) of a discrete random variable \(X\) with \(\mathbb{P}(X=x) > 0\), the surprisal in bits is
\[s(x) = \log_{1/2} \mathbb{P}(X=x).\]
Proof. Write \(p = \mathbb{P}(X=x)\). The change of base formula gives
\[\log_b y = \frac{{\operatorname{log}\mathopen{}\left\{y\right\}\mathclose{}}}{{\operatorname{log}\mathopen{}\left\{b\right\}\mathclose{}}}\]
for \(y > 0\) and \(b > 0\) with \(b \ne 1\). With \(b = 1/2\) and \(y = p\),
\[ \begin{aligned} \log_{1/2} p &= \frac{{\operatorname{log}\mathopen{}\left\{p\right\}\mathclose{}}}{{\operatorname{log}\mathopen{}\left\{1/2\right\}\mathclose{}}} \\ &= \frac{{\operatorname{log}\mathopen{}\left\{p\right\}\mathclose{}}}{-{\operatorname{log}\mathopen{}\left\{2\right\}\mathclose{}}} \\ &= -\frac{{\operatorname{log}\mathopen{}\left\{p\right\}\mathclose{}}}{{\operatorname{log}\mathopen{}\left\{2\right\}\mathclose{}}} \\ &= -\log_2 p \\ &= s(x). \end{aligned} \]
The step from the third to the fourth line is the change of base formula with \(b = 2\).
Example 2 (Halvings of certainty for a loaded coin)
A coin lands heads with probability \(0.2\). The chunk computes the surprisal of heads in two ways: as \(-\log_2 0.2\), and as \(\log_{1/2} 0.2\).
Both give \(2.322\) bits (Theorem 1). Halving \(1\) that many times gives \(0.5^{2.322} = 0.2\), the probability of heads.
Remark 1 (Surprisal as halvings of certainty). Start from certainty, probability \(1\). Each halving multiplies the probability by \(1/2\). After \(s\) halvings the probability is \((1/2)^s\), and solving \((1/2)^s = p\) for \(s\) gives \(s = \log_{1/2} p\). This count is only motivation. Theorem 1 proves that this \(s\) is the surprisal in bits. So the surprisal of a value is the number of times certainty must be halved to reach the probability of that value. When \(p\) is not \((1/2)^k\) for a whole number \(k\), the number of halvings is not a whole number.
Definition 3 (Nat) A nat is the unit of information when the logarithm in surprisal, and in every quantity built from it, is the natural logarithm.
One nat is the surprisal of a value with probability \(1/\text{e}\): for a value \(x\) of a discrete random variable \(X\),
\[ \begin{aligned} s(x) = 1 \text{ nat} &\iff -\ln \mathbb{P}(X=x) = 1\\ &\iff \mathbb{P}(X=x) = \text{e}^{-1} = 1/\text{e}\approx 0.368. \end{aligned} \]
Remark 2 (Converting between bits and nats). For any probability \(p \in (0, 1]\), the change-of-base rule for logarithms gives
\[ \begin{aligned} -\log_2 p &= \frac{-\ln p}{\ln 2}\\ &\approx 1.443 \times (-\ln p). \end{aligned} \]
So an outcome with a surprisal of \(1\) nat has a surprisal of \(1 / \ln 2 \approx 1.443\) bits, and the \(\ln 2 \approx 0.693\) nats of Example 3 are exactly \(\ln 2 / \ln 2 = 1\) bit.
A bit as a unit of information is not the same thing as a bit as a binary digit. The name shannon refers only to the unit of information, so it avoids this ambiguity. A binary digit whose two values are equally likely has a surprisal of exactly \(1\) bit, whichever value it takes. A binary digit that is \(0\) nine times in ten does not: the value \(0\) has a surprisal of \(-\log_2 0.9 \approx 0.152\) bits, and the value \(1\) has a surprisal of \(-\log_2 0.1 \approx 3.322\) bits.
Remark 3 (Unlikely outcomes carry more information). Surprisal is large when an outcome was unlikely, and it falls to \(0\) as the outcome becomes certain. Correctly predicting heads on one toss of a fair coin is worth \(1\) bit; correctly predicting ten heads in a row is worth \(10\) bits.
Remark 4 (Entropy is expected surprisal). The entropy of a discrete random variable \(X\) is the expectation of its surprisal:
\[ \begin{aligned} H(X) &= {\mathbb{E}\mathopen{}\left[-\log \mathbb{P}(X)\right]\mathclose{}} \\ &= {\mathbb{E}\mathopen{}\left[s(X)\right]\mathclose{}}. \end{aligned} \]
So \(H(X)\) is the average number of bits (with base-2 logarithms) needed to record a value of \(X\) when each value \(x\) costs \(s(x)\) bits. The source coding theorem, on a later page of these notes, makes that average precise: no uniquely decodable code does better.
Definition 4 (Rarity) The rarity of a value \(x\) of a discrete random variable \(X\) is the reciprocal of its probability mass:
\[{\mathbb{r}\mathopen{}\left(x\right)\mathclose{}} \stackrel{\text{def}}{=}\frac{1}{\mathbb{P}(X=x)}.\]
For a continuous random variable \(X\) with density \(\mathbb{p}\), the rarity of a value \(x\) is the reciprocal of the density:
\[{\mathbb{r}\mathopen{}\left(x\right)\mathclose{}} \stackrel{\text{def}}{=}\frac{1}{\mathbb{p}(x)}.\]
When the mass or the density is \(0\), the rarity is \(\infty\).
Example 4 (Rarity of the outcomes of a die)
Let \(X\) be the roll of a fair six-sided die. Each outcome has probability \(1/6\).
rarity <- function(p) 1 / p
p_fair <- 1 / 6
p_loaded_six <- 1 / 2
p_loaded_other <- (1 - p_loaded_six) / 5
rarity_fair <- rarity(p_fair)
rarity_loaded_six <- rarity(p_loaded_six)
rarity_loaded_other <- rarity(p_loaded_other)
rarities <- c(
fair = rarity_fair,
loaded_six = rarity_loaded_six,
loaded_other = rarity_loaded_other
)
rarities
#> fair loaded_six loaded_other
#> 6 2 10So each face of the fair die has rarity \({\mathbb{r}\mathopen{}\left(x\right)\mathclose{}} = 6\): one roll in six.
Suppose the die is loaded so that a six has probability \(1/2\). Then \({\mathbb{r}\mathopen{}\left(6\right)\mathclose{}} = 2\). If the other five faces share the rest equally, each has \({\mathbb{r}\mathopen{}\left(x\right)\mathclose{}} = 10\). The more probable an outcome, the lower its rarity.
Remark 5 (Source of the name). Leinster writes that, for a community whose \(i\)th species has relative abundance \(p_i\), “\(1/p_i\) is a measure of its rarity or specialness” (Leinster 2021, sec. 2.4, p. 52). The name “rarity” for the reciprocal of a probability is borrowed from there.
Theorem 2 (Surprisal is the logarithm of the rarity) Let \(X\) be a discrete random variable, and let \(x\) be a value of \(X\) with \(\mathbb{P}(X=x) > 0\). Then the surprisal of \(x\) is the logarithm of its rarity:
\[{\mathbb{s}\mathopen{}\left(x\right)\mathclose{}} = {\operatorname{log}\mathopen{}\left\{{\mathbb{r}\mathopen{}\left(x\right)\mathclose{}}\right\}\mathclose{}}.\]
Proof. \[ \begin{aligned} {\mathbb{s}\mathopen{}\left(x\right)\mathclose{}} &= -{\operatorname{log}\mathopen{}\left\{\mathbb{P}(X=x)\right\}\mathclose{}} && \text{(definition of surprisal)} \\ &= {\operatorname{log}\mathopen{}\left\{\frac{1}{\mathbb{P}(X=x)}\right\}\mathclose{}} && \text{(logarithm of a reciprocal)} \\ &= {\operatorname{log}\mathopen{}\left\{{\mathbb{r}\mathopen{}\left(x\right)\mathclose{}}\right\}\mathclose{}}. && \text{(definition of rarity)} \end{aligned} \]
Theorem 3 (Surprisal of a continuous value is the logarithm of the rarity) Let \(X\) be a continuous random variable with density \(\mathbb{p}\), and let \(x\) be a value with \(\mathbb{p}(x) > 0\). Then the surprisal of \(x\) is the logarithm of its rarity:
\[{\mathbb{s}\mathopen{}\left(x\right)\mathclose{}} = {\operatorname{log}\mathopen{}\left\{{\mathbb{r}\mathopen{}\left(x\right)\mathclose{}}\right\}\mathclose{}}.\]
Proof. \[ \begin{aligned} {\mathbb{s}\mathopen{}\left(x\right)\mathclose{}} &= -{\operatorname{log}\mathopen{}\left\{\mathbb{p}(x)\right\}\mathclose{}} && \text{(definition of surprisal)} \\ &= {\operatorname{log}\mathopen{}\left\{\frac{1}{\mathbb{p}(x)}\right\}\mathclose{}} && \text{(logarithm of a reciprocal)} \\ &= {\operatorname{log}\mathopen{}\left\{{\mathbb{r}\mathopen{}\left(x\right)\mathclose{}}\right\}\mathclose{}}. && \text{(definition of rarity)} \end{aligned} \]
Corollary 1 (Surprisal of a discrete value is nonnegative) Let \(X\) be a discrete random variable, and let \(x\) be a value of \(X\) with \(\mathbb{P}(X=x) > 0\). Then the rarity of \(x\) is at least \(1\), with equality exactly when \(\mathbb{P}(X=x) = 1\), and the surprisal satisfies
\[{\mathbb{s}\mathopen{}\left(x\right)\mathclose{}} \ge 0.\]
Proof. Since \(0 < \mathbb{P}(X=x) \le 1\), the rarity \({\mathbb{r}\mathopen{}\left(x\right)\mathclose{}} = 1 / \mathbb{P}(X=x)\) is at least \(1\), with equality exactly when \(\mathbb{P}(X=x) = 1\). The logarithm is increasing, and \({\operatorname{log}\mathopen{}\left\{1\right\}\mathclose{}} = 0\), so by Theorem 2, \({\mathbb{s}\mathopen{}\left(x\right)\mathclose{}} = {\operatorname{log}\mathopen{}\left\{{\mathbb{r}\mathopen{}\left(x\right)\mathclose{}}\right\}\mathclose{}} \ge 0\).
Remark 7 (Values of the probability, the rarity and the surprisal). For a discrete random variable, the mass \(\mathbb{P}(X=x)\) of a value with a mass above \(0\), its rarity \({\mathbb{r}\mathopen{}\left(x\right)\mathclose{}}\) and its surprisal \({\mathbb{s}\mathopen{}\left(x\right)\mathclose{}}\) take the values in the middle column. For a continuous random variable, the density \(\mathbb{p}(x)\) takes the place of the mass. At a value \(x\) with a density above \(0\), the rarity \({\mathbb{r}\mathopen{}\left(x\right)\mathclose{}}\) is the reciprocal of \(\mathbb{p}(x)\), and the surprisal \({\mathbb{s}\mathopen{}\left(x\right)\mathclose{}}\) is the surprisal of a continuous value. Their values are in the right column.
| Mass \(\mathbb{P}(X=x)\) | Density \(\mathbb{p}(x)\) | |
|---|---|---|
| Mass or density | \((0, 1]\) | \((0, \infty)\) |
| Rarity \({\mathbb{r}\mathopen{}\left(x\right)\mathclose{}}\) | \([1, \infty)\) | \((0, \infty)\) |
| Surprisal \({\mathbb{s}\mathopen{}\left(x\right)\mathclose{}}\) | \([0, \infty)\) | \((-\infty, \infty)\) |
Remark 8 (Rarity and odds). Let \(x\) be a value of a discrete random variable \(X\), and let \(A\) be the event \(X = x\) with probability \(p = \mathbb{P}(X=x)\). The odds in favour of \(A\) are \(p / (1 - p)\), and the odds against \(A\) are \((1 - p) / p\) (Grinstead and Snell 1997, Definition 1.4). The rarity of \(x\) is \({\mathbb{r}\mathopen{}\left(x\right)\mathclose{}} = 1/p\), so the odds against \(A\) are \({\mathbb{r}\mathopen{}\left(x\right)\mathclose{}} - 1\).
The first printed line shows that, for each \(p\), the rarity of the value exceeds the odds against its event by exactly \(1\). A value with probability \(1/4\) has rarity \(4\), and its event has odds of \(3\) to \(1\) against. The two differ by exactly \(1\), so they are relatively close when the rarity is large. At \(p = 1\) the rarity is \(1\) and the odds against are \(0\), but the odds in favour divide by zero.
The odds compare an event with its complement, and the odds against take values in \([0, \infty)\) when \(p\) is above \(0\). At \(p = 0\), the odds against and the rarity divide by zero, and both tend to \(\infty\) as \(p\) decreases to \(0\). For a value of a discrete random variable with \(p\) above \(0\), the rarity takes values in \([1, \infty)\). For a continuous random variable, the event \(X = x\) for a single value has probability \(0\), so its odds against and \(1/\mathbb{P}(X=x)\) are not defined, but the rarity of the value is defined from the density. An event such as \(X \le c\) can have a probability above \(0\), so it can have odds.
Definition 5 (Perplexity) The perplexity of a discrete random variable \(X\) is the exponential of its entropy, with the same base as the logarithm in the entropy:
\[{\mathrm{PP}\mathopen{}\left(X\right)\mathclose{}} \stackrel{\text{def}}{=}b^{{\mathbb{H}\mathopen{}\left(X\right)\mathclose{}}}.\]
With base-2 logarithms, \({\mathrm{PP}\mathopen{}\left(X\right)\mathclose{}} = 2^{{\mathbb{H}\mathopen{}\left(X\right)\mathclose{}}}\) with \({\mathbb{H}\mathopen{}\left(X\right)\mathclose{}}\) in bits. With natural logarithms, \({\mathrm{PP}\mathopen{}\left(X\right)\mathclose{}} = \text{e}^{{\mathbb{H}\mathopen{}\left(X\right)\mathclose{}}}\) with \({\mathbb{H}\mathopen{}\left(X\right)\mathclose{}}\) in nats. The two give the same value.
Theorem 4 (Perplexity is the probability-weighted geometric mean of the rarities) For a discrete random variable \(X\), the perplexity is a weighted geometric mean of the rarities, each raised to its probability. Take \(x\) over the values with \(\mathbb{P}(X=x) > 0\). Then
\[{\mathrm{PP}\mathopen{}\left(X\right)\mathclose{}} = \prod_x {\mathbb{r}\mathopen{}\left(x\right)\mathclose{}}^{\mathbb{P}(X=x)}.\]
Proof. \[ \begin{aligned} {\mathrm{PP}\mathopen{}\left(X\right)\mathclose{}} &= b^{{\mathbb{H}\mathopen{}\left(X\right)\mathclose{}}} && \text{(definition of perplexity)} \\ &= b^{{\mathbb{E}\mathopen{}\left[{\mathbb{s}\mathopen{}\left(X\right)\mathclose{}}\right]\mathclose{}}} && \text{(entropy is expected surprisal)} \\ &= b^{\sum_x \mathbb{P}(X=x) \log_b {\mathbb{r}\mathopen{}\left(x\right)\mathclose{}}} && \text{(surprisal is the logarithm of the rarity)} \\ &= \prod_x b^{\mathbb{P}(X=x) \log_b {\mathbb{r}\mathopen{}\left(x\right)\mathclose{}}} && \text{(a sum in the exponent is a product)} \\ &= \prod_x {\mathbb{r}\mathopen{}\left(x\right)\mathclose{}}^{\mathbb{P}(X=x)} && \text{(} b^{\log_b y} = y \text{)} \end{aligned} \]
Example 6 (Perplexity of a uniform distribution)
If \(X\) is uniform on \(k\) values, then every value has probability \(1/k\) and rarity \(k\), so by Theorem 4 the perplexity of \(X\) is \(k\). In general, the perplexity is the count of equally likely values that would give the same entropy as \(X\).
Example 7 (Perplexity of a loaded die)
Let \(X\) be the roll of the loaded die from Example 4, where a six has probability \(1/2\) and each other face has probability \(1/10\). The code computes the perplexity from the entropy in bits, and then from the rarities by Theorem 4.
Both routes give a perplexity of about \(4.47\). The loaded die has the same entropy as a fair die with about that many faces, fewer than the \(6\) faces it has.
Remark 9 (Source of the name). The name comes from speech recognition (Jelinek et al. 1977). Leinster defines the “diversity of order 1” as the exponential of the entropy (Leinster 2021, Definition 2.4.1). He calls a diversity index an “effective number” when it is \(k\) for \(k\) species with the same abundance (Leinster 2021, Definition 2.4.5).
Remark 10 (Differential entropy differs from entropy). A density value is not a probability, so the surprisal of a continuous value and the entropy of a continuous random variable (the differential entropy) behave differently from their discrete counterparts:
Definition 6 (Collision probability) The collision probability of a discrete random variable \(X\) is the chance that two independent copies \(X\) and \(X'\) of \(X\) take the same value:
\[\mathbb{P}(X = X') = \sum_x \mathbb{P}(X=x)^2.\]
Definition 7 (Rényi entropy of order 2 (collision entropy)) The Rényi entropy of order 2, also called the collision entropy (Wikipedia contributors 2026), of a discrete random variable \(X\) is the negative logarithm of the expectation of its probability, where \(\mathbb{P}(X)\) is the probability mass function evaluated at the random variable \(X\) itself:
\[H_2(X) = -\log {\mathbb{E}\mathopen{}\left[\mathbb{P}(X)\right]\mathclose{}}.\]
Rényi introduced this case of a family of entropies (Rényi 1961).
Theorem 5 (The expected probability is the collision probability) Let \(X\) be a discrete random variable, and let \(X'\) be an independent copy of \(X\). Then
\[{\mathbb{E}\mathopen{}\left[\mathbb{P}(X)\right]\mathclose{}} = \sum_x \mathbb{P}(X=x)^2 = \mathbb{P}(X = X').\]
Proof. The expectation of \(\mathbb{P}(X)\) adds, over the values \(x\), the value \(\mathbb{P}(X=x)\) times its probability \(\mathbb{P}(X=x)\):
\[ \begin{aligned} {\mathbb{E}\mathopen{}\left[\mathbb{P}(X)\right]\mathclose{}} &= \sum_x \mathbb{P}(X=x) \, \mathbb{P}(X=x) \\ &= \sum_x \mathbb{P}(X=x)^2. \end{aligned} \]
By the definition of the collision probability, the last sum is \(\mathbb{P}(X = X')\).
Theorem 6 (The collision entropy is at most the Shannon entropy) Let \(X\) be a discrete random variable with values \(x_1, \ldots, x_n\). Then the collision entropy is at most the entropy:
\[H_2(X) \le {\mathbb{H}\mathopen{}\left(X\right)\mathclose{}}.\]
The two coincide exactly when each value that \(X\) takes with positive probability has the same probability.
Proof. Write \(\mathbb{P}(X)\) for the probability mass function evaluated at \(X\). The function \(-\log\) is strictly convex, so Jensen’s inequality gives
\[{\mathbb{E}\mathopen{}\left[-\log \mathbb{P}(X)\right]\mathclose{}} \ge -\log {\mathbb{E}\mathopen{}\left[\mathbb{P}(X)\right]\mathclose{}},\]
with equality exactly when \(\mathbb{P}(X)\) is constant. The left side is \({\mathbb{H}\mathopen{}\left(X\right)\mathclose{}}\). The right side is \(H_2(X)\) by its definition. The function \(\mathbb{P}(X)\) is constant exactly when every value that \(X\) takes with positive probability has that same probability.
Example 8 (Collision entropy and entropy of a three-valued random variable)
Let \(X\) take three values with probabilities \(1/2\), \(1/4\) and \(1/4\). The code below computes the expected probability, the collision entropy and the entropy, with base-2 logarithms.
p <- c(1 / 2, 1 / 4, 1 / 4)
expected_prob <- sum(p^2)
collision_entropy <- -log2(expected_prob)
shannon_entropy <- -sum(p * log2(p))
c(
expected_prob = expected_prob,
collision_entropy = collision_entropy,
shannon_entropy = shannon_entropy
)
#> expected_prob collision_entropy shannon_entropy
#> 0.375000 1.415037 1.500000By Theorem 5, the expected probability \({\mathbb{E}\mathopen{}\left[\mathbb{P}(X)\right]\mathclose{}} = 0.375\) is the collision probability. The collision entropy is \(H_2(X) = 1.415\) bits. The entropy is \({\mathbb{H}\mathopen{}\left(X\right)\mathclose{}} = 1.5\) bits. As Theorem 6 states, \(H_2(X) \le {\mathbb{H}\mathopen{}\left(X\right)\mathclose{}}\), and the two differ because the three values are not equally likely.
Remark 11 (Two ways to summarize a random variable by its probabilities). Entropy is the expectation of the surprisal \(-\log \mathbb{P}(X)\). Taking the expectation of the probability \(\mathbb{P}(X)\) itself summarizes \(X\) differently. For a discrete random variable, Theorem 5 identifies that expectation with the collision probability, so the collision entropy is \(H_2(X) = -\log \mathbb{P}(X = X')\).
For a continuous random variable with density \(\mathbb{p}\), the analogue is \({\mathbb{E}\mathopen{}\left[\mathbb{p}(X)\right]\mathclose{}} = \int \mathbb{p}(x)^2\,dx\). The expected-density exercises derive this quantity, then compute it in the uniform case and the normal case.
Theorem 6 compares the collision entropy with the Shannon entropy.
Remark 12 (Surprisal and the Fisher information). When the probabilities depend on a parameter \(\theta\), the surprisal of a value \(x\) is \(-\log \mathbb{p}(x \mid \theta)\), which is minus the log-likelihood:
\[\mathbb{s}_{\theta}(x) = -\log \mathbb{p}(x \mid \theta) = -\ell(\theta).\]
Its derivative with respect to \(\theta\) is minus the score:
\[\frac{\partial}{\partial \theta} \mathbb{s}_{\theta}(x) = -{\ell'\mathopen{}\left(\theta\right)\mathclose{}}.\]
The expected squared score is the expected information, also called the Fisher information. It is also the expected second derivative of the surprisal, when the outcome \(X\) is drawn from the model at the true parameter value \(\theta_0\), and the score is evaluated at that same outcome \(X\):
\[ \mathcal{I}(\theta_0) = \mathbb{E}_{\theta_0}\mathopen{}\left[{\ell'\mathopen{}\left(\theta_0\right)\mathclose{}}^2\right]\mathclose{} = \mathbb{E}_{\theta_0}\mathopen{}\left[\left.{\frac{\partial^2}{\partial \theta^2} \mathbb{s}_{\theta}(X)}\right|_{\theta= \theta_0}\right]\mathclose{}. \]
It is also the second derivative, at the true parameter value, of the Kullback–Leibler divergence between the model at that value and the model at the varying value (proved in the sds notes):
\[\left.{\frac{\partial^2}{\partial \theta^2} {{D_{\mathrm{KL}}}\mathopen{}\left(\theta_0 \,\Vert\, \theta\right)\mathclose{}}}\right|_{\theta= \theta_0} = \mathcal{I}(\theta_0).\]
Definition 8 (Joint entropy) Let \(X\) and \(Y\) be discrete random variables with joint probability mass function \(p(x, y) \stackrel{\text{def}}{=}\mathbb{P}(X=x, Y=y)\). Their joint entropy is the entropy of the pair \((X, Y)\):
\[H(X, Y) \stackrel{\text{def}}{=}{\mathbb{E}\mathopen{}\left[-\log p(X, Y)\right]\mathclose{}}.\]
Definition 9 (Entropy given one value) For \(X\) and \(Y\) as in Definition 8, write \(p(y \mid x) \stackrel{\text{def}}{=}\mathbb{P}(Y=y \mid X=x)\). The entropy of \(Y\) given \(X=x\), for a value \(x\) with \(\mathbb{P}(X=x) > 0\), is the expectation of \(-\log p(Y \mid x)\) given \(X=x\):
\[H(Y \mid X=x) \stackrel{\text{def}}{=}{{\mathbb{E}\mathopen{}\left[-\log p(Y \mid x) \mid X=x\right]\mathclose{}}}.\]
Definition 10 (Conditional entropy) For \(X\) and \(Y\) as in Definition 8 and \(p(y \mid x)\) as in Definition 9, the conditional entropy of \(Y\) given \(X\) is the expectation of \(-\log p(Y \mid X)\):
\[H(Y \mid X) \stackrel{\text{def}}{=}{\mathbb{E}\mathopen{}\left[-\log p(Y \mid X)\right]\mathclose{}}.\]
Theorem 7 (Conditional entropy as an average of entropies given a value) For \(X\) and \(Y\) as in Definition 8,
\[H(Y \mid X) = \sum_{x} p(x) \, H(Y \mid X=x),\]
where \(p(x) \stackrel{\text{def}}{=}\mathbb{P}(X=x)\), and the sum runs over the values \(x\) with \(p(x) > 0\).
Proof. The law of iterated expectations conditions on \(X\):
\[ \begin{aligned} H(Y \mid X) &= {\mathbb{E}\mathopen{}\left[-\log p(Y \mid X)\right]\mathclose{}} \\ &= {\mathbb{E}\mathopen{}\left[{{\mathbb{E}\mathopen{}\left[-\log p(Y \mid X) \mid X\right]\mathclose{}}}\right]\mathclose{}} \\ &= \sum_{x} p(x) \, {{\mathbb{E}\mathopen{}\left[-\log p(Y \mid x) \mid X=x\right]\mathclose{}}} \\ &= \sum_{x} p(x) \, H(Y \mid X=x). \end{aligned} \]
The third line is the definition of expectation over the values \(x\) of \(X\), and the last line is Definition 9.
Theorem 8 (Chain rule for entropy) For discrete random variables \(X\) and \(Y\),
\[H(X, Y) = H(X) + H(Y \mid X).\]
Proof. Use the notation of Definition 8 and Definition 9. With probability \(1\), \(p(X, Y) = p(X) \, p(Y \mid X)\) and \(p(X, Y) > 0\), so
\[-\log p(X, Y) = -\log p(X) - \log p(Y \mid X).\]
Both terms on the right are nonnegative, so the expectation of the sum is the sum of the expectations:
\[ \begin{aligned} H(X, Y) &= {\mathbb{E}\mathopen{}\left[-\log p(X, Y)\right]\mathclose{}} \\ &= {\mathbb{E}\mathopen{}\left[-\log p(X)\right]\mathclose{}} + {\mathbb{E}\mathopen{}\left[-\log p(Y \mid X)\right]\mathclose{}} \\ &= H(X) + H(Y \mid X). \end{aligned} \]
Corollary 2 (Chain rule for entropy, other order) For discrete random variables \(X\) and \(Y\),
\[{\mathbb{H}\mathopen{}\left(X, Y\right)\mathclose{}} = {\mathbb{H}\mathopen{}\left(X \mid Y\right)\mathclose{}} + {\mathbb{H}\mathopen{}\left(Y\right)\mathclose{}}.\]
Proof. The pair \((Y, X)\) takes each value \((y, x)\) with the same probability that \((X, Y)\) takes \((x, y)\), so
\[{\mathbb{H}\mathopen{}\left(Y, X\right)\mathclose{}} = {\mathbb{H}\mathopen{}\left(X, Y\right)\mathclose{}}.\]
The chain rule, applied with the roles of \(X\) and \(Y\) exchanged, gives
\[{\mathbb{H}\mathopen{}\left(Y, X\right)\mathclose{}} = {\mathbb{H}\mathopen{}\left(Y\right)\mathclose{}} + {\mathbb{H}\mathopen{}\left(X \mid Y\right)\mathclose{}}.\]
Combining the two displays gives the claim.
Corollary 3 (Conditional entropy as a difference) For discrete random variables \(X\) and \(Y\) with finite entropies,
\[{\mathbb{H}\mathopen{}\left(X \mid Y\right)\mathclose{}} = {\mathbb{H}\mathopen{}\left(X, Y\right)\mathclose{}} - {\mathbb{H}\mathopen{}\left(Y\right)\mathclose{}}.\]
Proof. Subtract \({\mathbb{H}\mathopen{}\left(Y\right)\mathclose{}}\) from both sides of Corollary 2:
\[ \begin{aligned} {\mathbb{H}\mathopen{}\left(X, Y\right)\mathclose{}} - {\mathbb{H}\mathopen{}\left(Y\right)\mathclose{}} &= {\mathbb{H}\mathopen{}\left(X \mid Y\right)\mathclose{}} + {\mathbb{H}\mathopen{}\left(Y\right)\mathclose{}} - {\mathbb{H}\mathopen{}\left(Y\right)\mathclose{}} \\ &= {\mathbb{H}\mathopen{}\left(X \mid Y\right)\mathclose{}}. \end{aligned} \]
Example 9 (Chain rule for entropy with a noisy copy)
Let \(X\) be a fair coin toss, coded \(0\) or \(1\). Let \(Y\) be a noisy copy of \(X\): it equals \(X\) with probability \(0.8\) and the other value with probability \(0.2\). The joint probabilities are \(0.4\) for \((0, 0)\) and \((1, 1)\), and \(0.1\) for \((0, 1)\) and \((1, 0)\). The chunk computes each entropy from its definition, in bits.
entropy <- function(p) -sum(p * log2(p))
joint <- matrix(
data = c(0.4, 0.1, 0.1, 0.4),
nrow = 2,
dimnames = list(x = 0:1, y = 0:1)
)
p_y <- colSums(joint)
cond_x_given_y <- sweep(x = joint, MARGIN = 2, STATS = p_y, FUN = "/")
h_x_given_y_values <- apply(X = cond_x_given_y, MARGIN = 2, FUN = entropy)
h_x_given_y <- sum(p_y * h_x_given_y_values)
h_xy <- entropy(joint)
h_y <- entropy(p_y)
c(h_xy = h_xy, h_x_given_y = h_x_given_y, h_y = h_y)
#> h_xy h_x_given_y h_y
#> 1.7219281 0.7219281 1.0000000The chunk computes \({\mathbb{H}\mathopen{}\left(X \mid Y\right)\mathclose{}}\) as the average of the entropies given each value of \(Y\), as in Theorem 7 with \(X\) and \(Y\) exchanged. Here \({\mathbb{H}\mathopen{}\left(X, Y\right)\mathclose{}} = 1.722\) bits, \({\mathbb{H}\mathopen{}\left(X \mid Y\right)\mathclose{}} = 0.722\) bits and \({\mathbb{H}\mathopen{}\left(Y\right)\mathclose{}} = 1\) bits. So \({\mathbb{H}\mathopen{}\left(X \mid Y\right)\mathclose{}} + {\mathbb{H}\mathopen{}\left(Y\right)\mathclose{}} = 1.722\) bits agrees with \({\mathbb{H}\mathopen{}\left(X, Y\right)\mathclose{}}\) (Corollary 2), and \({\mathbb{H}\mathopen{}\left(X, Y\right)\mathclose{}} - {\mathbb{H}\mathopen{}\left(Y\right)\mathclose{}} = 0.722\) bits agrees with \({\mathbb{H}\mathopen{}\left(X \mid Y\right)\mathclose{}}\) (Corollary 3).
Definition 11 (Joint surprisal) Let \(X\) and \(Y\) be discrete random variables with joint probability mass function \(p(x, y) \stackrel{\text{def}}{=}\mathbb{P}(X=x, Y=y)\). The joint surprisal of a pair of values \((x, y)\) with \(p(x, y) > 0\) is the surprisal of that pair:
\[{\mathbb{s}\mathopen{}\left(x, y\right)\mathclose{}} \stackrel{\text{def}}{=}-\log p(x, y).\]
Definition 12 (Conditional surprisal) For \(X\) and \(Y\) as in Definition 11, the conditional surprisal of a value \(y\) given a value \(x\) with \(\mathbb{P}(X=x) > 0\) and \(\mathbb{P}(Y=y \mid X=x) > 0\) is
\[{\mathbb{s}\mathopen{}\left(y \mid x\right)\mathclose{}} \stackrel{\text{def}}{=}-\log \mathbb{P}(Y=y \mid X=x).\]
Example 10 (Joint and conditional surprisal of a noisy copy)
Let \(X\) be a fair coin toss, coded \(0\) or \(1\). Let \(Y\) be a noisy copy of \(X\): it equals \(X\) with probability \(0.8\) and the other value with probability \(0.2\). Take the pair of values \(x = 0\) and \(y = 1\). The joint probability is \(\mathbb{P}(X=0, Y=1) = 0.1\), the probability of \(X=0\) is \(0.5\), and the conditional probability is \(\mathbb{P}(Y=1 \mid X=0) = 0.2\). The chunk computes the three surprisals, in bits.
The joint surprisal is \({\mathbb{s}\mathopen{}\left(0, 1\right)\mathclose{}} = 3.322\) bits, the surprisal of \(x = 0\) alone is \({\mathbb{s}\mathopen{}\left(0\right)\mathclose{}} = 1\) bit, and the conditional surprisal is \({\mathbb{s}\mathopen{}\left(1 \mid 0\right)\mathclose{}} = 2.322\) bits.
Theorem 9 (Chain rule for surprisal) For discrete random variables \(X\) and \(Y\) and values \(x\) and \(y\) with \(\mathbb{P}(X=x, Y=y) > 0\),
\[{\mathbb{s}\mathopen{}\left(x, y\right)\mathclose{}} = {\mathbb{s}\mathopen{}\left(x\right)\mathclose{}} + {\mathbb{s}\mathopen{}\left(y \mid x\right)\mathclose{}}.\]
Proof. Since \(\mathbb{P}(X=x, Y=y) = \mathbb{P}(X=x) \, \mathbb{P}(Y=y \mid X=x)\),
\[ \begin{aligned} {\mathbb{s}\mathopen{}\left(x, y\right)\mathclose{}} &= -\log \mathbb{P}(X=x, Y=y) \\ &= -\log \mathopen{}\left[\mathbb{P}(X=x) \, \mathbb{P}(Y=y \mid X=x)\right]\mathclose{} \\ &= -\log \mathbb{P}(X=x) - \log \mathbb{P}(Y=y \mid X=x) \\ &= {\mathbb{s}\mathopen{}\left(x\right)\mathclose{}} + {\mathbb{s}\mathopen{}\left(y \mid x\right)\mathclose{}}. \end{aligned} \]
Corollary 4 (Conditional surprisal as a difference) For \(X\), \(Y\), \(x\) and \(y\) as in Theorem 9,
\[{\mathbb{s}\mathopen{}\left(y \mid x\right)\mathclose{}} = {\mathbb{s}\mathopen{}\left(x, y\right)\mathclose{}} - {\mathbb{s}\mathopen{}\left(x\right)\mathclose{}}.\]
Proof. Subtract \({\mathbb{s}\mathopen{}\left(x\right)\mathclose{}}\) from both sides of Theorem 9:
\[ \begin{aligned} {\mathbb{s}\mathopen{}\left(x, y\right)\mathclose{}} - {\mathbb{s}\mathopen{}\left(x\right)\mathclose{}} &= {\mathbb{s}\mathopen{}\left(x\right)\mathclose{}} + {\mathbb{s}\mathopen{}\left(y \mid x\right)\mathclose{}} - {\mathbb{s}\mathopen{}\left(x\right)\mathclose{}} \\ &= {\mathbb{s}\mathopen{}\left(y \mid x\right)\mathclose{}}. \end{aligned} \]
Example 11 (Chain rule for surprisal with a noisy copy)
For the pair of values in Example 10, the chunk recomputes the three surprisals in bits.
The surprisal of \(x = 0\) plus the conditional surprisal of \(y = 1\) given \(x = 0\) is \(3.322\) bits. This sum is the joint surprisal \({\mathbb{s}\mathopen{}\left(0, 1\right)\mathclose{}} = 3.322\) bits (Theorem 9). Subtracting \({\mathbb{s}\mathopen{}\left(0\right)\mathclose{}} = 1\) bit from the joint surprisal recovers \({\mathbb{s}\mathopen{}\left(1 \mid 0\right)\mathclose{}} = 2.322\) bits (Corollary 4).
Lemma 1 (Chain rule for surprisal with the conditioning reversed) For discrete random variables \(X\) and \(Y\) and outcomes \(x\) and \(y\) with \(\mathbb{P}(X=x, Y=y) > 0\),
\[{\mathbb{s}\mathopen{}\left(x, y\right)\mathclose{}} = {\mathbb{s}\mathopen{}\left(x \mid y\right)\mathclose{}} + {\mathbb{s}\mathopen{}\left(y\right)\mathclose{}}.\]
Proof. Applying Theorem 9 with the roles of \(X\) and \(Y\) swapped gives
\[{\mathbb{s}\mathopen{}\left(y, x\right)\mathclose{}} = {\mathbb{s}\mathopen{}\left(y\right)\mathclose{}} + {\mathbb{s}\mathopen{}\left(x \mid y\right)\mathclose{}}.\]
Both \(\mathbb{P}(Y=y, X=x)\) and \(\mathbb{P}(X=x, Y=y)\) are the probability of the same pair of values, so \({\mathbb{s}\mathopen{}\left(y, x\right)\mathclose{}} = {\mathbb{s}\mathopen{}\left(x, y\right)\mathclose{}}\). Substituting this into the display above, and swapping the two summands, gives the claim.
Example 12 (Chain rule for surprisal with the conditioning reversed, for a noisy copy)
For the pair of values in Example 10, \(\mathbb{P}(X=0, Y=1) = 0.1\), \(\mathbb{P}(Y=1) = 0.5\) and \(\mathbb{P}(X=0 \mid Y=1) = 0.2\). The chunk computes the three surprisals in bits.
The conditional surprisal of \(x = 0\) given \(y = 1\) plus the surprisal of \(y = 1\) is \(3.322\) bits. This sum is the joint surprisal \({\mathbb{s}\mathopen{}\left(0, 1\right)\mathclose{}} = 3.322\) bits (Lemma 1).
Remark 13 (The chain rule for entropy is the chain rule for surprisal on average). The entropy of a pair is the expectation of its joint surprisal, and the conditional entropy is the expectation of the conditional surprisal:
\[ \begin{aligned} {\mathbb{H}\mathopen{}\left(X, Y\right)\mathclose{}} &= {\mathbb{E}\mathopen{}\left[{\mathbb{s}\mathopen{}\left(X, Y\right)\mathclose{}}\right]\mathclose{}} \\ {\mathbb{H}\mathopen{}\left(Y \mid X\right)\mathclose{}} &= {\mathbb{E}\mathopen{}\left[{\mathbb{s}\mathopen{}\left(Y \mid X\right)\mathclose{}}\right]\mathclose{}}. \end{aligned} \]
Taking the expectation of both sides of Theorem 9 therefore gives Theorem 8.
Definition 13 (Mutual information) The mutual information between discrete random variables \(X\) and \(Y\) with finite entropies is the sum of their entropies minus their joint entropy:
\[I(X; Y) \stackrel{\text{def}}{=}{\mathbb{H}\mathopen{}\left(X\right)\mathclose{}} + {\mathbb{H}\mathopen{}\left(Y\right)\mathclose{}} - {\mathbb{H}\mathopen{}\left(X, Y\right)\mathclose{}}.\]
Theorem 10 (Mutual information is symmetric) For discrete random variables \(X\) and \(Y\) with finite entropies,
\[I(X; Y) = I(Y; X).\]
Proof. The joint entropy of the pair \((X, Y)\) equals that of \((Y, X)\), because both are the entropy of the same two values, listed in either order. So Definition 13 gives
\[ \begin{aligned} I(X; Y) &= {\mathbb{H}\mathopen{}\left(X\right)\mathclose{}} + {\mathbb{H}\mathopen{}\left(Y\right)\mathclose{}} - {\mathbb{H}\mathopen{}\left(X, Y\right)\mathclose{}} \\ &= {\mathbb{H}\mathopen{}\left(Y\right)\mathclose{}} + {\mathbb{H}\mathopen{}\left(X\right)\mathclose{}} - {\mathbb{H}\mathopen{}\left(Y, X\right)\mathclose{}} \\ &= I(Y; X). \end{aligned} \]
Theorem 11 (Mutual information as a reduction in entropy) For discrete random variables \(X\) and \(Y\) with finite entropies, the mutual information is the reduction in the entropy of either variable from learning the other:
\[I(X; Y) = {\mathbb{H}\mathopen{}\left(Y\right)\mathclose{}} - {\mathbb{H}\mathopen{}\left(Y \mid X\right)\mathclose{}} = {\mathbb{H}\mathopen{}\left(X\right)\mathclose{}} - {\mathbb{H}\mathopen{}\left(X \mid Y\right)\mathclose{}}.\]
Proof. Subtract \({\mathbb{H}\mathopen{}\left(X\right)\mathclose{}}\) from both sides of the chain rule:
\[{\mathbb{H}\mathopen{}\left(Y \mid X\right)\mathclose{}} = {\mathbb{H}\mathopen{}\left(X, Y\right)\mathclose{}} - {\mathbb{H}\mathopen{}\left(X\right)\mathclose{}}.\]
Substituting into Definition 13 gives
\[ \begin{aligned} {\mathbb{H}\mathopen{}\left(Y\right)\mathclose{}} - {\mathbb{H}\mathopen{}\left(Y \mid X\right)\mathclose{}} &= {\mathbb{H}\mathopen{}\left(Y\right)\mathclose{}} - \mathopen{}\left[{\mathbb{H}\mathopen{}\left(X, Y\right)\mathclose{}} - {\mathbb{H}\mathopen{}\left(X\right)\mathclose{}}\right]\mathclose{} \\ &= {\mathbb{H}\mathopen{}\left(X\right)\mathclose{}} + {\mathbb{H}\mathopen{}\left(Y\right)\mathclose{}} - {\mathbb{H}\mathopen{}\left(X, Y\right)\mathclose{}} \\ &= I(X; Y). \end{aligned} \]
The chain rule also gives \({\mathbb{H}\mathopen{}\left(X \mid Y\right)\mathclose{}} = {\mathbb{H}\mathopen{}\left(X, Y\right)\mathclose{}} - {\mathbb{H}\mathopen{}\left(Y\right)\mathclose{}}\), so the same steps with \(X\) and \(Y\) exchanged give \({\mathbb{H}\mathopen{}\left(X\right)\mathclose{}} - {\mathbb{H}\mathopen{}\left(X \mid Y\right)\mathclose{}} = I(X; Y)\).
Theorem 12 (Mutual information from the conditional entropies) For discrete random variables \(X\) and \(Y\) with finite entropies,
\[I(X; Y) = {\mathbb{H}\mathopen{}\left(X, Y\right)\mathclose{}} - \mathopen{}\left[{\mathbb{H}\mathopen{}\left(X \mid Y\right)\mathclose{}} + {\mathbb{H}\mathopen{}\left(Y \mid X\right)\mathclose{}}\right]\mathclose{}.\]
Proof. By Corollary 3 and the chain rule, the entropy of each variable is the joint entropy minus a conditional entropy:
\[ \begin{aligned} {\mathbb{H}\mathopen{}\left(X\right)\mathclose{}} &= {\mathbb{H}\mathopen{}\left(X, Y\right)\mathclose{}} - {\mathbb{H}\mathopen{}\left(Y \mid X\right)\mathclose{}} \\ {\mathbb{H}\mathopen{}\left(Y\right)\mathclose{}} &= {\mathbb{H}\mathopen{}\left(X, Y\right)\mathclose{}} - {\mathbb{H}\mathopen{}\left(X \mid Y\right)\mathclose{}}. \end{aligned} \]
Substituting both into Definition 13 gives
\[ \begin{aligned} I(X; Y) &= {\mathbb{H}\mathopen{}\left(X\right)\mathclose{}} + {\mathbb{H}\mathopen{}\left(Y\right)\mathclose{}} - {\mathbb{H}\mathopen{}\left(X, Y\right)\mathclose{}} \\ &= \mathopen{}\left[{\mathbb{H}\mathopen{}\left(X, Y\right)\mathclose{}} - {\mathbb{H}\mathopen{}\left(Y \mid X\right)\mathclose{}}\right]\mathclose{} + \mathopen{}\left[{\mathbb{H}\mathopen{}\left(X, Y\right)\mathclose{}} - {\mathbb{H}\mathopen{}\left(X \mid Y\right)\mathclose{}}\right]\mathclose{} - {\mathbb{H}\mathopen{}\left(X, Y\right)\mathclose{}} \\ &= {\mathbb{H}\mathopen{}\left(X, Y\right)\mathclose{}} - \mathopen{}\left[{\mathbb{H}\mathopen{}\left(X \mid Y\right)\mathclose{}} + {\mathbb{H}\mathopen{}\left(Y \mid X\right)\mathclose{}}\right]\mathclose{}. \end{aligned} \]
Theorem 13 (Decomposition of the sum of entropies) For discrete random variables \(X\) and \(Y\) with finite entropies,
\[{\mathbb{H}\mathopen{}\left(X\right)\mathclose{}} + {\mathbb{H}\mathopen{}\left(Y\right)\mathclose{}} = {\mathbb{H}\mathopen{}\left(X \mid Y\right)\mathclose{}} + 2 \, I(X; Y) + {\mathbb{H}\mathopen{}\left(Y \mid X\right)\mathclose{}}.\]
Proof. Rearranging Theorem 12 gives
\[{\mathbb{H}\mathopen{}\left(X, Y\right)\mathclose{}} = I(X; Y) + {\mathbb{H}\mathopen{}\left(X \mid Y\right)\mathclose{}} + {\mathbb{H}\mathopen{}\left(Y \mid X\right)\mathclose{}}.\]
Rearranging Definition 13 gives
\[{\mathbb{H}\mathopen{}\left(X\right)\mathclose{}} + {\mathbb{H}\mathopen{}\left(Y\right)\mathclose{}} = I(X; Y) + {\mathbb{H}\mathopen{}\left(X, Y\right)\mathclose{}}.\]
Substituting the first display into the second gives
\[ \begin{aligned} {\mathbb{H}\mathopen{}\left(X\right)\mathclose{}} + {\mathbb{H}\mathopen{}\left(Y\right)\mathclose{}} &= I(X; Y) + \mathopen{}\left[I(X; Y) + {\mathbb{H}\mathopen{}\left(X \mid Y\right)\mathclose{}} + {\mathbb{H}\mathopen{}\left(Y \mid X\right)\mathclose{}}\right]\mathclose{} \\ &= {\mathbb{H}\mathopen{}\left(X \mid Y\right)\mathclose{}} + 2 \, I(X; Y) + {\mathbb{H}\mathopen{}\left(Y \mid X\right)\mathclose{}}. \end{aligned} \]
Theorem 14 (Twice the mutual information) For discrete random variables \(X\) and \(Y\) with finite entropies,
\[2 \, I(X; Y) = \mathopen{}\left[{\mathbb{H}\mathopen{}\left(X\right)\mathclose{}} - {\mathbb{H}\mathopen{}\left(X \mid Y\right)\mathclose{}}\right]\mathclose{} + \mathopen{}\left[{\mathbb{H}\mathopen{}\left(Y\right)\mathclose{}} - {\mathbb{H}\mathopen{}\left(Y \mid X\right)\mathclose{}}\right]\mathclose{}.\]
Proof. By Theorem 11,
\[ \begin{aligned} {\mathbb{H}\mathopen{}\left(X\right)\mathclose{}} - {\mathbb{H}\mathopen{}\left(X \mid Y\right)\mathclose{}} &= I(X; Y) \\ {\mathbb{H}\mathopen{}\left(Y\right)\mathclose{}} - {\mathbb{H}\mathopen{}\left(Y \mid X\right)\mathclose{}} &= I(X; Y). \end{aligned} \]
Adding the two displays gives
\[ \begin{aligned} \mathopen{}\left[{\mathbb{H}\mathopen{}\left(X\right)\mathclose{}} - {\mathbb{H}\mathopen{}\left(X \mid Y\right)\mathclose{}}\right]\mathclose{} + \mathopen{}\left[{\mathbb{H}\mathopen{}\left(Y\right)\mathclose{}} - {\mathbb{H}\mathopen{}\left(Y \mid X\right)\mathclose{}}\right]\mathclose{} &= I(X; Y) + I(X; Y) \\ &= 2 \, I(X; Y). \end{aligned} \]
Example 13 (Mutual information identities with a noisy copy)
Take the fair coin \(X\) and its noisy copy \(Y\) from Example 9. The chunk computes the entropies from the joint probabilities in bits, then the mutual information in four ways.
entropy <- function(p) -sum(p * log2(p))
joint <- matrix(
data = c(0.4, 0.1, 0.1, 0.4),
nrow = 2
)
h_xy <- entropy(joint)
h_x <- entropy(rowSums(joint))
h_y <- entropy(colSums(joint))
h_x_given_y <- h_xy - h_y
h_y_given_x <- h_xy - h_x
mi_definition <- h_x + h_y - h_xy
mi_reduction <- h_y - h_y_given_x
mi_conditionals <- h_xy - (h_x_given_y + h_y_given_x)
mi_twice <- ((h_x - h_x_given_y) + (h_y - h_y_given_x)) / 2
c(mi_definition, mi_reduction, mi_conditionals, mi_twice)
#> [1] 0.2780719 0.2780719 0.2780719 0.2780719All four agree: \(I(X; Y) = 0.278\) bits (Definition 13, Theorem 11, Theorem 12 and Theorem 14). Also \({\mathbb{H}\mathopen{}\left(X\right)\mathclose{}} + {\mathbb{H}\mathopen{}\left(Y\right)\mathclose{}} = 2\) bits matches \({\mathbb{H}\mathopen{}\left(X \mid Y\right)\mathclose{}} + 2 \, I(X; Y) + {\mathbb{H}\mathopen{}\left(Y \mid X\right)\mathclose{}} = 2\) bits (Theorem 13).
Remark 14 (Entropies as areas). The identities above match a picture of two overlapping regions, with the area of one region standing for \({\mathbb{H}\mathopen{}\left(X\right)\mathclose{}}\) and the area of the other for \({\mathbb{H}\mathopen{}\left(Y\right)\mathclose{}}\). The overlap has area \(I(X; Y)\) (Definition 13). The part of the first region outside the overlap has area \({\mathbb{H}\mathopen{}\left(X \mid Y\right)\mathclose{}}\), and the part of the second region outside the overlap has area \({\mathbb{H}\mathopen{}\left(Y \mid X\right)\mathclose{}}\). The two regions together have area \({\mathbb{H}\mathopen{}\left(X, Y\right)\mathclose{}}\) (Theorem 12). The picture is a mnemonic for two variables only.
Theorem 15 (Mutual information as a divergence) Let \(X\) and \(Y\) be discrete random variables with joint probability mass function \(p(x, y)\) and marginal probability mass functions \(p(x)\) and \(p(y)\). If their entropies are finite, then their mutual information is the Kullback–Leibler divergence of the product of the marginals from the joint distribution:
\[I(X; Y) = \sum_{x, y} p(x, y) \log \frac{p(x, y)}{p(x) \, p(y)},\]
where the sum runs over the pairs with \(p(x, y) > 0\).
Proof. The entropies are finite, so the expectations below are finite and can be split and regrouped. With probability \(1\), \(p(X, Y) > 0\), \(p(X) > 0\) and \(p(Y) > 0\). By Definition 13 and the definitions of entropy and joint entropy,
\[ \begin{aligned} I(X; Y) &= {\mathbb{H}\mathopen{}\left(X\right)\mathclose{}} + {\mathbb{H}\mathopen{}\left(Y\right)\mathclose{}} - {\mathbb{H}\mathopen{}\left(X, Y\right)\mathclose{}} \\ &= {\mathbb{E}\mathopen{}\left[-\log p(X)\right]\mathclose{}} + {\mathbb{E}\mathopen{}\left[-\log p(Y)\right]\mathclose{}} - {\mathbb{E}\mathopen{}\left[-\log p(X, Y)\right]\mathclose{}} \\ &= {\mathbb{E}\mathopen{}\left[\log p(X, Y) - \log p(X) - \log p(Y)\right]\mathclose{}} \\ &= {\mathbb{E}\mathopen{}\left[\log \frac{p(X, Y)}{p(X) \, p(Y)}\right]\mathclose{}} \\ &= \sum_{x, y} p(x, y) \log \frac{p(x, y)}{p(x) \, p(y)}. \end{aligned} \]
The last line is the definition of expectation over the pairs with \(p(x, y) > 0\). It is the divergence of \(p(x) \, p(y)\) from \(p(x, y)\) by the discrete formula.
Example 14 (Mutual information of a noisy copy)
Let \(X\) be a fair coin toss, coded \(0\) or \(1\). Let \(Y\) equal \(X\) with probability \(0.8\) and the other value with probability \(0.2\). The joint distribution gives probability \(0.4\) to \((0, 0)\) and \((1, 1)\) and \(0.1\) to \((0, 1)\) and \((1, 0)\). The chunk computes the mutual information in bits from the divergence formula in Theorem 15.
So \(I(X; Y) = 0.278\) bits. This matches \({\mathbb{H}\mathopen{}\left(Y\right)\mathclose{}} - {\mathbb{H}\mathopen{}\left(Y \mid X\right)\mathclose{}}\), which is \(1\) bit minus the entropy of a coin with probabilities \(0.8\) and \(0.2\). That is \(1 - 0.722\) bits.
Theorem 16 (The divergence is nonnegative) Let \(p\) and \(q\) be probability mass functions on the values \(x_1, x_2, \ldots\), with \(q(x) > 0\) wherever \(p(x) > 0\), and suppose that
\[\sum_x p(x) \, \bigl\lvert \log_2 \bigl( p(x) / q(x) \bigr) \bigr\rvert < \infty.\]
Then the Kullback–Leibler divergence satisfies
\[D_2(p \,\|\, q) \ge 0,\]
with \(D_2(p \,\|\, q) = 0\) exactly when \(q = p\).
Proof. Every sum here runs over the values \(x\) with \(p(x) > 0\). For every \(t > 0\), \(\ln t \le t - 1\), with equality exactly when \(t = 1\). Apply this with \(t = q(x) / p(x)\), and multiply by \(p(x) > 0\):
\[ p(x) \ln \frac{q(x)}{p(x)} \le q(x) - p(x), \]
with equality exactly when \(q(x) = p(x)\). Both sides are summable over \(x\). The left side does by the assumption in the statement, and the right side does because \(\sum_x p(x) = 1\) and \(\sum_x q(x) \le 1\). So the relation holds for the totals over \(x\):
\[ \sum_x p(x) \ln \frac{q(x)}{p(x)} \le \sum_x q(x) - 1 \le 0. \]
The left side is \(-\ln 2 \cdot D_2(p \,\|\, q)\), so \(D_2(p \,\|\, q) \ge 0\).
If \(D_2(p \,\|\, q) = 0\), both relations hold with equality. The first forces \(q(x) = p(x)\) at every \(x\) with \(p(x) > 0\). The second then gives \(\sum_x q(x) = 1\), so \(q\) has no mass where \(p\) has none, and \(q = p\). Conversely, \(q = p\) gives \(\log_2 (p(x)/q(x)) = 0\) for every \(x\).
Example 15 (Divergence of a biased coin from a fair coin)
Let \(p = (0.9, 0.1)\) be the probability mass function of a biased coin, and let \(q = (0.5, 0.5)\) be a fair coin. The code below computes the divergence both ways, in bits.
Both divergences between the two coins are positive, as Theorem 16 requires, and they differ, so swapping \(p\) and \(q\) changes the divergence. The divergence of \(p\) from itself is \(0\).
Theorem 17 (Mutual information is nonnegative) For discrete random variables \(X\) and \(Y\) with finite entropies,
\[I(X; Y) \ge 0.\]
Equality holds exactly when \(X\) and \(Y\) are independent.
Proof. Let \(p(x, y)\) be the joint mass function, with marginals \(p(x)\) and \(p(y)\). By Theorem 15, \(I(X; Y)\) is the divergence of \(p(x) \, p(y)\) from \(p(x, y)\), and the sum defining it is absolutely summable, as the proof of that result shows. The mass function \(p(x) \, p(y)\) is positive wherever \(p(x, y)\) is positive, because each marginal is at least \(p(x, y)\) there. By Theorem 16, the divergence is nonnegative, with equality exactly when the two mass functions agree. The logarithm satisfies \(\log_b t = \ln t / \ln b\), so the divergence with \(\log_b\) is the divergence with \(\log_2\) times \(\ln 2 / \ln b\), which has the same sign and the same zero. Hence \(I(X; Y) \ge 0\), and \(I(X; Y) = 0\) exactly when \(p(x, y) = p(x) \, p(y)\) for every pair, which is independence.
Example 16 (Mutual information of dependent and independent coins)
For the noisy copy in Example 14, the mutual information is positive, because \(Y\) depends on \(X\). For two independent fair coins, every joint probability is \(0.25\). The chunk computes the mutual information of both pairs.
joint_dependent <- matrix(data = c(0.4, 0.1, 0.1, 0.4), nrow = 2)
ratio_dependent <- joint_dependent / outer(
X = rowSums(joint_dependent),
Y = colSums(joint_dependent)
)
mi_dependent <- sum(joint_dependent * log2(ratio_dependent))
joint_independent <- matrix(data = 0.25, nrow = 2, ncol = 2)
product_independent <- outer(
X = rowSums(joint_independent),
Y = colSums(joint_independent)
)
ratio_independent <- joint_independent / product_independent
terms_independent <- joint_independent * log2(ratio_independent)
mi_independent <- sum(terms_independent)
c(mi_dependent = mi_dependent, mi_independent = mi_independent)
#> mi_dependent mi_independent
#> 0.2780719 0.0000000So the mutual information of the independent coins is \(0\) bits, and that of the dependent pair is \(0.278\) bits (Theorem 17).
Corollary 5 (Conditioning reduces entropy) For discrete random variables \(X\) and \(Y\) with finite entropies,
\[{\mathbb{H}\mathopen{}\left(Y \mid X\right)\mathclose{}} \le {\mathbb{H}\mathopen{}\left(Y\right)\mathclose{}}.\]
Equality holds exactly when \(X\) and \(Y\) are independent.
Proof. By Theorem 11,
\[{\mathbb{H}\mathopen{}\left(Y\right)\mathclose{}} - {\mathbb{H}\mathopen{}\left(Y \mid X\right)\mathclose{}} = I(X; Y).\]
By Theorem 17, the right side is nonnegative, and it is \(0\) exactly when \(X\) and \(Y\) are independent.
Example 17 (Learning a noisy copy lowers the entropy)
For the coin \(X\) and noisy copy \(Y\) in Example 14, the entropy of \(Y\) is \(1\) bit. Given \(X\), the variable \(Y\) is a coin with probabilities \(0.8\) and \(0.2\). The chunk computes the conditional entropy from that coin.
Here \({\mathbb{H}\mathopen{}\left(Y \mid X\right)\mathclose{}} = 0.722\) bits, which is below \({\mathbb{H}\mathopen{}\left(Y\right)\mathclose{}} = 1\) bit (Corollary 5).
Remark 15 (Mutual information as a divergence). Cover and Thomas (2006, sec. 2.3) define mutual information as the Kullback–Leibler divergence of the product of the marginals of \((X, Y)\) from their joint distribution. Theorem 15 proves that this divergence equals \({\mathbb{H}\mathopen{}\left(Y\right)\mathclose{}} - {\mathbb{H}\mathopen{}\left(Y \mid X\right)\mathclose{}}\) (Cover and Thomas 2006, sec. 2.4), and Theorem 17 proves that \(I(X; Y) \ge 0\) (Cover and Thomas 2006, sec. 2.6). Learning \(X\) never raises the entropy of \(Y\) on average (Corollary 5).
Theorem 18 (Mutual information of a variable with itself) For a discrete random variable \(X\) with finite entropy,
\[I(X; X) = {\mathbb{H}\mathopen{}\left(X\right)\mathclose{}}.\]
Proof. Given \(X=x\), the variable \(X\) equals \(x\) with probability \(1\), so \(p(x \mid x) = 1\). Hence \(-\log p(X \mid x) = -\log 1 = 0\) given \(X=x\), and the expectation of this constant is \(0\):
\[{\mathbb{H}\mathopen{}\left(X \mid X=x\right)\mathclose{}} = 0.\]
By Theorem 7,
\[ \begin{aligned} {\mathbb{H}\mathopen{}\left(X \mid X\right)\mathclose{}} &= \sum_{x} p(x) \, {\mathbb{H}\mathopen{}\left(X \mid X=x\right)\mathclose{}} \\ &= 0. \end{aligned} \]
By Theorem 11 with \(Y = X\),
\[ \begin{aligned} I(X; X) &= {\mathbb{H}\mathopen{}\left(X\right)\mathclose{}} - {\mathbb{H}\mathopen{}\left(X \mid X\right)\mathclose{}} \\ &= {\mathbb{H}\mathopen{}\left(X\right)\mathclose{}}. \end{aligned} \]
Example 18 (A fair coin is fully informative about itself)
Let \(X\) be a fair coin toss. Its entropy is \(1\) bit. Given \(X\) itself, there is no uncertainty left, so \({\mathbb{H}\mathopen{}\left(X \mid X\right)\mathclose{}} = 0\). Hence \(I(X; X) = 1 - 0 = 1\) bit (Theorem 18), the same as \({\mathbb{H}\mathopen{}\left(X\right)\mathclose{}}\).
Definition 14 (Information gain) A decision tree splits the points at a node into branches. The information gain of the split is the entropy of the class labels at the node, minus the entropy of the labels in each branch, weighted by the share of the node’s points that branch holds (Quinlan 1986).
Remark 16 (Information gain is mutual information). Draw one point uniformly at random from the node of Definition 14, and let \(Y\) be its class and \(X\) the branch it falls into. Then the entropy at the node is \(H(Y)\), the weighted entropy left in the branches is \(H(Y \mid X)\), and the information gain is the mutual information \(I(X; Y)\).
Exercise 1 (Choosing between two splits) A node holds \(20\) points, \(10\) red and \(10\) green. Two candidate splits each send the points into two branches:
| split | branch | red | green |
|---|---|---|---|
| A | yes | \(4\) | \(0\) |
| no | \(6\) | \(10\) | |
| B | yes | \(5\) | \(10\) |
| no | \(5\) | \(0\) |
Draw one point uniformly at random from the node, let \(Y\) be its color, and let \(X\) be the branch it falls into (Remark 16). The information gain of each split (Definition 14) is then \(I(X; Y)\). Use base-2 logarithms throughout.
Compute \(H(Y)\).
For each split, compute \(H(Y \mid X = x)\) for both branches, and then \(H(Y \mid X)\).
Compute the information gain \(I(X; Y)\) for each split. Which split has the larger gain?
Solution 1.
Half the points are red, so
\[ \begin{aligned} H(Y) &= -\tfrac{1}{2} \log_2 \tfrac{1}{2} - \tfrac{1}{2} \log_2 \tfrac{1}{2} \\ &= 1 \text{ bit}. \end{aligned} \]
A branch holding one color only has entropy \(0\). For split A, the “no” branch holds \(6\) red and \(10\) green points of \(16\):
\[ \begin{aligned} H(Y \mid X = \text{no}) &= -\tfrac{6}{16} \log_2 \tfrac{6}{16} - \tfrac{10}{16} \log_2 \tfrac{10}{16} \\ &\approx 0.531 + 0.424 \\ &\approx 0.954 \text{ bits}. \end{aligned} \]
The “yes” branch holds \(4\) of the \(20\) points and the “no” branch \(16\), so
\[ \begin{aligned} H(Y \mid X) &= \tfrac{4}{20} \cdot 0 + \tfrac{16}{20} \cdot 0.954 \\ &\approx 0.764 \text{ bits}. \end{aligned} \]
For split B, the “yes” branch holds \(5\) red and \(10\) green points of \(15\):
\[ \begin{aligned} H(Y \mid X = \text{yes}) &= -\tfrac{1}{3} \log_2 \tfrac{1}{3} - \tfrac{2}{3} \log_2 \tfrac{2}{3} \\ &\approx 0.528 + 0.390 \\ &\approx 0.918 \text{ bits}. \end{aligned} \]
The “yes” branch holds \(15\) of the \(20\) points and the “no” branch \(5\), so
\[ \begin{aligned} H(Y \mid X) &= \tfrac{15}{20} \cdot 0.918 + \tfrac{5}{20} \cdot 0 \\ &\approx 0.689 \text{ bits}. \end{aligned} \]
By Theorem 11, the gain is \(H(Y) - H(Y \mid X)\):
Split B has the larger gain. Both splits isolate a branch of one color, so the gain depends on the other, mixed branch. B’s mixed branch, \(5\) red against \(10\) green, is more lopsided than A’s \(6\) against \(10\), so it has less entropy, and it also holds fewer of the points, \(15\) against \(16\), so its entropy gets less weight.
Theorem 19 (Chain rule for entropy, many variables) For discrete random variables \(X_1, \ldots, X_n\) with finite entropies,
\[{\mathbb{H}\mathopen{}\left(X_1, \ldots, X_n\right)\mathclose{}} = \sum_{i=1}^{n} {\mathbb{H}\mathopen{}\left(X_i \mid X_1, \ldots, X_{i-1}\right)\mathclose{}},\]
where the term for \(i = 1\) is \({\mathbb{H}\mathopen{}\left(X_1\right)\mathclose{}}\).
Proof. The proof is by induction on \(n\). The claim for \(n = 1\) is \({\mathbb{H}\mathopen{}\left(X_1\right)\mathclose{}} = {\mathbb{H}\mathopen{}\left(X_1\right)\mathclose{}}\).
Let \(n \ge 2\), and suppose the claim holds for \(n - 1\) variables. Treat \((X_1, \ldots, X_{n-1})\) as a single variable. The chain rule for two variables (Theorem 8) gives
\[{\mathbb{H}\mathopen{}\left(X_1, \ldots, X_n\right)\mathclose{}} = {\mathbb{H}\mathopen{}\left(X_1, \ldots, X_{n-1}\right)\mathclose{}} + {\mathbb{H}\mathopen{}\left(X_n \mid X_1, \ldots, X_{n-1}\right)\mathclose{}}.\]
The induction hypothesis expands the first summand on the right:
\[ \begin{aligned} {\mathbb{H}\mathopen{}\left(X_1, \ldots, X_n\right)\mathclose{}} &= \sum_{i=1}^{n-1} {\mathbb{H}\mathopen{}\left(X_i \mid X_1, \ldots, X_{i-1}\right)\mathclose{}} + {\mathbb{H}\mathopen{}\left(X_n \mid X_1, \ldots, X_{n-1}\right)\mathclose{}} \\ &= \sum_{i=1}^{n} {\mathbb{H}\mathopen{}\left(X_i \mid X_1, \ldots, X_{i-1}\right)\mathclose{}}. \end{aligned} \]
Example 19 (Chain rule for entropy along a chain of noisy copies)
Let \(X_1\) be a fair coin toss, coded \(0\) or \(1\). Let \(X_2\) be a noisy copy of \(X_1\) that flips it with probability \(0.2\), and let \(X_3\) be a noisy copy of \(X_2\) that flips it with probability \(0.2\), independently of \(X_1\) given \(X_2\). The chunk builds the joint probabilities of \((X_1, X_2, X_3)\) and compares their entropy, in bits, with the sum in Theorem 19.
flip <- 0.2
channel <- matrix(
data = c(1 - flip, flip, flip, 1 - flip),
nrow = 2,
byrow = TRUE
)
joint <- array(data = 0, dim = c(2, 2, 2))
for (x1 in 1:2) {
for (x2 in 1:2) {
for (x3 in 1:2) {
joint[x1, x2, x3] <- 0.5 * channel[x1, x2] * channel[x2, x3]
}
}
}
h_joint <- -sum(joint * log2(joint))
h_coin <- -flip * log2(flip) - (1 - flip) * log2(1 - flip)
h_sum <- 1 + h_coin + h_coin
c(h_joint = h_joint, h_sum = h_sum)
#> h_joint h_sum
#> 2.443856 2.443856The first term of the sum is \({\mathbb{H}\mathopen{}\left(X_1\right)\mathclose{}} = 1\) bit. Given \(X_1\), the variable \(X_2\) is a coin with flip probability \(0.2\), and given \((X_1, X_2)\) the variable \(X_3\) is the same kind of coin, so each of the other two terms is \(0.722\) bits. The sum is \(2.444\) bits, which equals \({\mathbb{H}\mathopen{}\left(X_1, X_2, X_3\right)\mathclose{}} = 2.444\) bits.
Definition 15 (Conditional mutual information) The conditional mutual information of discrete random variables \(X\) and \(Y\) given a third one, \(Z\), with finite entropies, is the reduction in the conditional entropy of \(Y\) given \(Z\) from also learning \(X\):
\[I(X; Y \mid Z) \stackrel{\text{def}}{=}{\mathbb{H}\mathopen{}\left(Y \mid Z\right)\mathclose{}} - {\mathbb{H}\mathopen{}\left(Y \mid X, Z\right)\mathclose{}}.\]
Example 20 (Conditional mutual information along a chain of noisy copies)
Take the chain of noisy copies \(X_1\), \(X_2\), \(X_3\) from Example 19. Once \(X_2\) is known, \(X_1\) adds nothing to the prediction of \(X_3\), so \({\mathbb{H}\mathopen{}\left(X_3 \mid X_1, X_2\right)\mathclose{}} = {\mathbb{H}\mathopen{}\left(X_3 \mid X_2\right)\mathclose{}}\), and both equal the entropy \(h\) of a coin with flip probability \(0.2\). The chunk computes the conditional mutual information.
So \(I(X_1; X_3 \mid X_2) = 0\) bits.
Theorem 20 (Chain rule for mutual information) For discrete random variables \(X\), \(Y\) and \(Z\) whose entropies \({\mathbb{H}\mathopen{}\left(X\right)\mathclose{}}\), \({\mathbb{H}\mathopen{}\left(Y\right)\mathclose{}}\) and \({\mathbb{H}\mathopen{}\left(Z\right)\mathclose{}}\) are finite,
\[I(X, Z; Y) = I(Z; Y) + I(X; Y \mid Z).\]
Proof. By Theorem 11, applied to the pair \((X, Z)\) and to \(Z\),
\[ \begin{aligned} I(X, Z; Y) &= {\mathbb{H}\mathopen{}\left(Y\right)\mathclose{}} - {\mathbb{H}\mathopen{}\left(Y \mid X, Z\right)\mathclose{}} \\ I(Z; Y) &= {\mathbb{H}\mathopen{}\left(Y\right)\mathclose{}} - {\mathbb{H}\mathopen{}\left(Y \mid Z\right)\mathclose{}}. \end{aligned} \]
Subtracting the second display from the first gives
\[ \begin{aligned} I(X, Z; Y) - I(Z; Y) &= {\mathbb{H}\mathopen{}\left(Y \mid Z\right)\mathclose{}} - {\mathbb{H}\mathopen{}\left(Y \mid X, Z\right)\mathclose{}} \\ &= I(X; Y \mid Z), \end{aligned} \]
where the last line is Definition 15.
Example 21 (Chain rule for mutual information along a chain of noisy copies)
For the chain in Example 19, the marginal distribution of \(X_3\) is a fair coin, so \({\mathbb{H}\mathopen{}\left(X_3\right)\mathclose{}} = 1\) bit. The chunk computes the mutual information of \(X_3\) with \(X_2\), and with the pair \((X_1, X_2)\).
Here \(I(X_2; X_3) = 0.278\) bits and \(I(X_1, X_2; X_3) = 0.278\) bits. The difference is \(I(X_1; X_3 \mid X_2) = 0\) (Theorem 20), as in Example 20.
Theorem 21 (Conditional mutual information is nonnegative) For discrete random variables \(X\), \(Y\) and \(Z\) with finite entropies,
\[I(X; Y \mid Z) \ge 0.\]
Proof. For each value \(z\) with \(\mathbb{P}(Z=z) > 0\), let \(I_z(X; Y)\) be the mutual information of \(X\) and \(Y\) computed from their joint probabilities given \(Z=z\), so that \(I_z(X; Y) = {\mathbb{H}\mathopen{}\left(Y \mid Z=z\right)\mathclose{}} - {\mathbb{H}\mathopen{}\left(Y \mid X, Z=z\right)\mathclose{}}\). Applying Definition 10 to \({\mathbb{H}\mathopen{}\left(Y \mid Z\right)\mathclose{}}\) and to \({\mathbb{H}\mathopen{}\left(Y \mid X, Z\right)\mathclose{}}\) expands each over the values \(z\) of \(Z\):
\[ \begin{aligned} I(X; Y \mid Z) &= {\mathbb{H}\mathopen{}\left(Y \mid Z\right)\mathclose{}} - {\mathbb{H}\mathopen{}\left(Y \mid X, Z\right)\mathclose{}} \\ &= \sum_z \mathbb{P}(Z=z) \mathopen{}\left[{\mathbb{H}\mathopen{}\left(Y \mid Z=z\right)\mathclose{}} - {\mathbb{H}\mathopen{}\left(Y \mid X, Z=z\right)\mathclose{}}\right]\mathclose{} \\ &= \sum_z \mathbb{P}(Z=z) \, I_z(X; Y). \end{aligned} \]
Each \(I_z(X; Y)\) is nonnegative by Theorem 17. Since \(\mathbb{P}(Z=z) \ge 0\) as well, every summand \(\mathbb{P}(Z=z) \, I_z(X; Y)\) is nonnegative, so \(I(X; Y \mid Z) \ge 0\).
Example 22 (Learning a third variable can create information)
Let \(X\) and \(Y\) be independent fair coins, coded \(0\) or \(1\), and let \(Z = X + Y \bmod 2\) record whether they differ. The two coins are independent, so \(I(X; Y) = 0\) (Theorem 17). Given \(Z\), each of \(X\) and \(Y\) determines the other. The chunk computes the conditional mutual information from the joint probability mass function, in bits.
entropy <- function(p) -sum(p[p > 0] * log2(p[p > 0]))
joint <- array(data = 0, dim = c(2, 2, 2))
for (x in 0:1) {
for (y in 0:1) {
z <- (x + y) %% 2
joint[x + 1, y + 1, z + 1] <- 0.25
}
}
h_xyz <- entropy(joint)
h_xz <- entropy(apply(X = joint, MARGIN = c(1, 3), FUN = sum))
h_yz <- entropy(apply(X = joint, MARGIN = c(2, 3), FUN = sum))
h_z <- entropy(apply(X = joint, MARGIN = 3, FUN = sum))
h_y_given_z <- h_yz - h_z
h_y_given_xz <- h_xyz - h_xz
h_y_given_z - h_y_given_xz
#> [1] 1So \(I(X; Y \mid Z) = 1\) bit, which is nonnegative (Theorem 21), although \(I(X; Y) = 0\).
Definition 16 (Markov chain of three random variables) Discrete random variables \(X\), \(Y\) and \(Z\) form a Markov chain \(X \to Y \to Z\) (Cover and Thomas 2006, sec. 2.8) if \(X\) and \(Z\) are conditionally independent given \(Y\): for every value \(y\) with \(\mathbb{P}(Y=y) > 0\) and all values \(x\) and \(z\),
\[\mathbb{P}(X=x, Z=z \mid Y=y) = \mathbb{P}(X=x \mid Y=y) \, \mathbb{P}(Z=z \mid Y=y).\]
Example 23 (A chain of noisy copies is a Markov chain)
In Example 19, each of \(X_2\) and \(X_3\) is a noisy copy of the variable before it. So \(X_3\) depends on \(X_1\) only through \(X_2\). The chunk builds the joint probability mass function of \((X_1, X_2, X_3)\) and checks the defining equation of the chain \(X_1 \to X_2 \to X_3\) for each value of \(X_2\).
flip <- 0.2
copy <- matrix(
data = c(1 - flip, flip, flip, 1 - flip),
nrow = 2
)
joint <- array(data = 0, dim = c(2, 2, 2))
for (x1 in 1:2) {
for (x2 in 1:2) {
for (x3 in 1:2) {
joint[x1, x2, x3] <- 0.5 * copy[x1, x2] * copy[x2, x3]
}
}
}
gaps <- numeric(2)
for (x2 in 1:2) {
slice <- joint[, x2, ]
given_x2 <- slice / sum(slice)
product <- outer(rowSums(given_x2), colSums(given_x2))
gaps[x2] <- max(abs(given_x2 - product))
}
gaps
#> [1] 1.110223e-16 1.110223e-16Both gaps are zero up to rounding, so \(X_1\) and \(X_3\) are conditionally independent given \(X_2\).
Lemma 2 (Conditional mutual information along a Markov chain) If \(X \to Y \to Z\) is a Markov chain and the entropies of \(X\), \(Y\) and \(Z\) are finite, then
\[I(Z; X \mid Y) = 0.\]
Proof. Fix values \(y\) and \(z\) with \(\mathbb{P}(Y=y, Z=z) > 0\). Dividing the defining equation of the chain by \(\mathbb{P}(Z=z \mid Y=y)\) gives
\[\mathbb{P}(X=x \mid Y=y, Z=z) = \mathbb{P}(X=x \mid Y=y)\]
for every \(x\). So the entropy given \((Y, Z) = (y, z)\) is the entropy given \(Y = y\). Averaging over \((Y, Z)\) and over \(Y\) gives
\[{\mathbb{H}\mathopen{}\left(X \mid Y, Z\right)\mathclose{}} = {\mathbb{H}\mathopen{}\left(X \mid Y\right)\mathclose{}}.\]
By Definition 15,
\[ \begin{aligned} I(Z; X \mid Y) &= {\mathbb{H}\mathopen{}\left(X \mid Y\right)\mathclose{}} - {\mathbb{H}\mathopen{}\left(X \mid Z, Y\right)\mathclose{}} \\ &= {\mathbb{H}\mathopen{}\left(X \mid Y\right)\mathclose{}} - {\mathbb{H}\mathopen{}\left(X \mid Y, Z\right)\mathclose{}} \\ &= 0. \end{aligned} \]
Theorem 22 (Data processing inequality) If \(X \to Y \to Z\) is a Markov chain and the entropies of \(X\), \(Y\) and \(Z\) are finite, then
\[I(X; Z) \le I(X; Y).\]
Proof. The chain rule for the pair \((Z, Y)\) and the pair \((Y, Z)\) gives
\[ \begin{aligned} I(Z, Y; X) &= I(Y; X) + I(Z; X \mid Y) \\ I(Y, Z; X) &= I(Z; X) + I(Y; X \mid Z). \end{aligned} \]
The pairs \((Z, Y)\) and \((Y, Z)\) contain the same two variables, so \(I(Z, Y; X) = I(Y, Z; X)\). By Lemma 2, \(I(Z; X \mid Y) = 0\). By Theorem 21, \(I(Y; X \mid Z) \ge 0\). Therefore
\[ \begin{aligned} I(Y; X) &= I(Z; X) + I(Y; X \mid Z) \\ &\ge I(Z; X). \end{aligned} \]
By Theorem 10, \(I(Y; X) = I(X; Y)\) and \(I(Z; X) = I(X; Z)\), so \(I(X; Z) \le I(X; Y)\).
Example 24 (Each extra noisy copy loses information)
For the chain \(X_1 \to X_2 \to X_3\) in Example 23, the chunk computes the mutual information of \(X_1\) with \(X_2\) and with \(X_3\), in bits. Each variable is a fair coin. The variable \(X_3\) differs from \(X_1\) when exactly one of the two copies flips, which has probability \(2 \times 0.2 \times 0.8 = 0.32\).
Here \(I(X_1; X_3) = 0.096\) bits is below \(I(X_1; X_2) = 0.278\) bits (Theorem 22).