1. Entropy and Mutual Information

Information theory begins with a simple question: how much uncertainty is contained in a random variable? From that starting point, we can quantify how uncertainty changes when variables are observed, how different two probability distributions are, and how much information two variables share.

This note develops the core definitions and identities from Sections 2.1-2.5 of Cover and Thomas, using discrete random variables and base-2 logarithms throughout.

Notation convention

Uppercase letters such as $X$, $Y$, and $Z$ denote random variables. Lowercase letters such as $x$, $y$, and $z$ denote particular realized values. Calligraphic letters such as $\mathcal{X}$ denote alphabets, so $x\in \mathcal{X}$. We write $p_X(x)=\mathrm{Pr}(X=x)$, $p_{X,Y}(x,y)=\mathrm{Pr}(X=x,Y=y)$, and $p_{Y\mid X}(y\mid x)=\mathrm{Pr}(Y=y\mid X=x)$. When comparing two abstract distributions, we follow the book and use the shorter notation $p(x)$ and $q(x)$.

---

1. Entropy

Let $X$ be a discrete random variable with alphabet $\mathcal{X}$ and probability mass function $p_X(x)$. Before defining the average uncertainty of $X$, it helps to quantify the information associated with one outcome.

1.1 Surprise of an outcome

The self-information or surprise of observing $X=x$ is

$${ı}_X(x)={\log }_2\frac{1}{p_X(x)}=-{\log }_2{p}_X(x).$$

This definition captures three useful intuitions:

1. A likely event is not very surprising.
2. A rare event carries more information.
3. Independent events should contribute additive information.

The third property explains the logarithm. If $X$ and $Y$ are independent, then the joint probability of observing $X=x$ and $Y=y$ is $p_X(x)p_Y(y)$, while the information in that joint outcome is

$${\log }_2\frac{1}{p_X(x)p_Y(y)}={\log }_2\frac{1}{p_X(x)}+{\log }_2\frac{1}{p_Y(y)}.$$

Probability multiplies, but information adds.

1.2 Expected surprise

The entropy of $X$ is the expected surprise of its outcome:

$$\boxed{H(X)=-\sum _{x\in \mathcal{X}}{p}_X(x){\log }_2{p}_X(x)={\mathbb{E}}_{X\sim p_X}\left[{\log }_2\frac{1}{p_X(X)}\right]}$$

We use the convention $0\log 0=0$. Entropy depends only on the probabilities, not on the labels assigned to the outcomes.

Because $0\le p_X(x)\le 1$, every term ${\log }_2(1/p_X(x))$ is nonnegative, so

$$H(X)\ge 0.$$

If the logarithm uses base $2$, entropy is measured in bits. Natural logarithms give nats. See the notation reference for the probability notation used throughout this note.

1.3 Bernoulli entropy

For $X\sim \mathrm{Bernoulli}(p)$,

$$H(X)=H(p)=-p{\log }_{2}p-(1-p){\log }_2(1-p),$$

where $H(p)$ denotes the entropy of a Bernoulli random variable with parameter $p$.

• If $p=0$ or $p=1$, then $X$ is deterministic and $H(X)=0$.
• If $p=1/2$, both outcomes are equally likely and $H(X)=1$ bit.

Figure 1: The binary entropy is symmetric around $p=1/2$, where uncertainty is maximized.

Entropy therefore measures uncertainty rather than the numerical size of an outcome.

Unequal probabilities

Suppose $X$ has four possible outcomes with probabilities

$$\left(\frac{1}{2},\frac{1}{4},\frac{1}{8},\frac{1}{8}\right).$$

Then

$$H(X)=\frac{1}{2}(1)+\frac{1}{4}(2)+\frac{1}{8}(3)+\frac{1}{8}(3)=\frac{7}{4}\text{ bits}.$$

The terms $1$, $2$, and $3$ are the surprises of outcomes having probabilities $1/2$, $1/4$, and $1/8$.

1.4 Entropy as description length

Entropy is closely connected to compression. If outcomes are encoded efficiently, common outcomes receive short binary descriptions and rare outcomes receive longer descriptions. The entropy is the fundamental target for the average number of bits required to describe the outcome.

---

2. Joint Entropy and Conditional Entropy

Entropy extends naturally from one random variable to several. For background on joint and conditional distributions, see Joint Probability Distributions.

2.1 Joint entropy

The pair $(X,Y)$ can be treated as one vector-valued random variable. Its joint entropy is

$$\boxed{H(X,Y)=-\sum _{x\in \mathcal{X}}\sum _{y\in \mathcal{Y}}{p}_{X,Y}(x,y){\log }_2{p}_{X,Y}(x,y)}$$

Joint entropy measures how much uncertainty is present in the pair before either variable is observed.

2.2 Conditional entropy

After observing $X=x$, our remaining uncertainty about $Y$ is

$$H(Y\mid X=x)=-\sum _{y\in \mathcal{Y}}{p}_{Y\mid X}(y\mid x){\log }_2{p}_{Y\mid X}(y\mid x).$$

The conditional entropy averages this quantity over $X$:

$$\boxed{H(Y\mid X)=\sum _{x\in \mathcal{X}}{p}_X(x)H(Y\mid X=x)=-\sum _{x\in \mathcal{X}}\sum _{y\in \mathcal{Y}}{p}_{X,Y}(x,y){\log }_2{p}_{Y\mid X}(y\mid x)}$$

The distinction is important:

• $H(Y\mid X=x)$ is the uncertainty after one particular observation.
• $H(Y\mid X)$ is the remaining uncertainty averaged over all possible observations of $X$.

2.3 The two-variable entropy chain rule

Using the probability factorization

$$p_{X,Y}(x,y)=p_X(x)p_{Y\mid X}(y\mid x),$$

we obtain

$$\begin{array}{rl}H(X,Y)& =-\sum _{x,y}{p}_{X,Y}(x,y){\log }_2(p_X(x)p_{Y\mid X}(y\mid x))\\ & =-\sum _{x,y}{p}_{X,Y}(x,y){\log }_2{p}_X(x)-\sum _{x,y}{p}_{X,Y}(x,y){\log }_2{p}_{Y\mid X}(y\mid x)\\ & =H(X)+H(Y\mid X).\end{array}$$

Therefore,

$$\boxed{H(X,Y)=H(X)+H(Y\mid X)}.$$

The interpretation is sequential: first describe $X$, then describe what remains unknown about $Y$ once $X$ is available.

Reversing the order gives

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

In general, $H(Y\mid X)$ and $H(X\mid Y)$ are not equal. What is equal is the total joint uncertainty obtained after adding the appropriate marginal entropy.

Main properties of joint and conditional entropy

These properties hold for discrete random variables.

Joint entropy

1. Symmetry

   $$H(X,Y)=H(Y,X).$$

2. Chain rule

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

3. Bounds

   $$\max \{H(X),H(Y)\}\le H(X,Y)\le H(X)+H(Y).$$

   The upper bound is attained if and only if $X$ and $Y$ are independent.

4. Repeating a variable adds no uncertainty

   $$H(X,X)=H(X).$$

Conditional entropy

1. Average remaining uncertainty

   $$H(X\mid Y)=\sum _{y\in \mathcal{Y}}{p}_Y(y)H(X\mid Y=y).$$

2. Nonnegativity

   $$H(X\mid Y)\ge 0.$$

3. Conditioning reduces entropy on average

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

   with equality if and only if $X$ and $Y$ are independent. A proof appears in the inequalities note.

4. Zero conditional entropy

   $$H(X\mid Y)=0$$

   if and only if $X$ is determined by $Y$ with probability one.

Conditional entropy is generally not symmetric: $H(X\mid Y)$ need not equal $H(Y\mid X)$.

---

3. Relative Entropy (KL Divergence)

Entropy describes uncertainty within one distribution. Relative entropy instead compares two distributions over the same alphabet $\mathcal{X}$:

• $p$ is the distribution that actually generates the outcomes.
• $q$ is the distribution used by our model, approximation, or code.

The question is: how costly is it to use $q$ when the data really follow $p$?

3.1 From the likelihood ratio to KL divergence

For one realized outcome $x$, compare the probability assigned by the two distributions through the log-likelihood ratio

$${\log }_2\frac{p(x)}{q(x)}.$$

This quantity is positive when $p(x)>q(x)$ and negative when $p(x)<q(x)$. However it is not a true distance between distributions since it is not symmetric and does not satisfy the triangle inequality. Nonetheless, it is often useful to think of relative entropy as a “distance” between distributions. Because outcomes are generated according to $p$, we average the log-likelihood ratio under $p$:

$$\boxed{D(p\parallel q)=\sum _{x\in \mathcal{X}}p(x){\log }_2\frac{p(x)}{q(x)}={\mathbb{E}}_{X\sim p}\left[{\log }_2\frac{p(X)}{q(X)}\right]}$$

This expectation is the relative entropy or Kullback-Leibler divergence of $p$ relative to $q$. With base-2 logarithms, it is measured in bits.

The order has meaning

In $D(p\parallel q)$, samples come from $p$, so $p$ determines how each log-ratio is weighted. Reversing the arguments changes both the ratios and the averaging distribution. The symbol $\parallel$ is deliberately directional.

3.2 Coding interpretation: the cost of the wrong model

If we know the true distribution $p$, the ideal description length assigned to outcome $x$ is

$${\ell }_p(x)=-{\log }_{2}p(x).$$

If we instead construct the code using $q$, the same outcome receives length

$${\ell }_q(x)=-{\log }_{2}q(x).$$

Since outcomes still occur according to $p$, the average length of the code based on $q$ is the cross-entropy

$$H_{\mathrm{cross}}(p,q)=-\sum _{x}p(x){\log }_{2}q(x).$$

Adding and subtracting ${\log }_{2}p(x)$ gives

$$\begin{array}{rl}{H}_{\mathrm{cross}}(p,q)& =-\sum _{x}p(x){\log }_{2}p(x)+\sum _{x}p(x){\log }_2\frac{p(x)}{q(x)}\\ & =H(p)+D(p\parallel q).\end{array}$$

Here $H(p)=-{\sum }_{x}p(x){\log }_{2}p(x)$ is the entropy of the distribution $p$. Therefore,

$$\boxed{D(p\parallel q)=H_{\mathrm{cross}}(p,q)-H(p)}$$

KL divergence is the extra average description length caused by using $q$ instead of the true distribution $p$. If $q=p$, there is no mismatch and the extra cost is zero.

Connection to cross-entropy loss

The same decomposition explains the cross-entropy loss used to train classifiers. Let $X$ be an input random variable and let $Y$ be its class-label random variable with alphabet $\mathcal{Y}=\{1,\dots ,K\}$. Suppose

• $p_{\mathrm{data}}(x,y)$ is the true joint data distribution,
• $p_{\mathrm{data}}(y\mid x)$ is its conditional label distribution, and
• $q_{\theta }(y\mid x)$ is the distribution predicted by a model with parameters $\theta$.

For a fixed input realization $x$, the population cross-entropy is

$$H_{\mathrm{cross}}\left(p_{\mathrm{data}}(\cdot \mid x),q_{\theta }(\cdot \mid x)\right)=-\sum _{y=1}^K{p}_{\mathrm{data}}(y\mid x){\log }_2{q}_{\theta }(y\mid x).$$

Averaging over inputs and applying the KL decomposition gives

$$\begin{array}{rl}\sum _{x\in \mathcal{X}}{p}_{\mathrm{data}}(x)H_{\mathrm{cross}}\left(p_{\mathrm{data}}(\cdot \mid x),q_{\theta }(\cdot \mid x)\right)& =H(Y\mid X)\\ & +\sum _{x\in \mathcal{X}}{p}_{\mathrm{data}}(x)D\left(p_{\mathrm{data}}(\cdot \mid x)\parallel q_{\theta }(\cdot \mid x)\right).\end{array}$$

The conditional entropy $H(Y\mid X)$ is determined by the data-generating distribution and does not depend on $\theta$. Therefore, minimizing cross-entropy with respect to $\theta$ is equivalent to minimizing the expected KL divergence from the true conditional distribution to the model distribution.

In a labeled dataset, we observe one class realization $y$ for each input realization $x$. Its one-hot target is $t_k=1\{y=k\}$. Machine-learning libraries normally use natural logarithms, so the per-example loss becomes

$$\begin{array}{rl}{\mathcal{L}}_{\mathrm{CE}}(x,y;\theta )& =-\sum _{k=1}^K{t}_k\ln q_{\theta }(Y=k\mid X=x)\\ & =-\ln q_{\theta }(Y=y\mid X=x).\end{array}$$

For binary classification, with $\mathcal{Y}=\{0,1\}$ and ${\hat{p}}_{\theta }(x)=q_{\theta }(Y=1\mid X=x)$, this reduces to binary cross-entropy:

$${\mathcal{L}}_{\mathrm{BCE}}(x,y;\theta )=-y\ln {\hat{p}}_{\theta }(x)-(1-y)\ln (1-{\hat{p}}_{\theta }(x)).$$

These empirical losses are measured in nats rather than bits. Changing the log base only rescales the objective by a positive constant and does not change its minimizer.

Worked example: Bernoulli distributions

Let $p$ and $q$ be Bernoulli PMFs with $p(1)=0.9$ and $q(1)=0.5$, where the realization $x=1$ denotes success.

Figure 2: The bars show where $p$ and $q$ disagree. The curve shows the resulting $D(p\parallel q)$: it reaches zero only when the model matches the true distribution, $q=p$, and grows as the mismatch increases.

$x$	$p(x)$	$q(x)$	${\log }_2\frac{p(x)}{q(x)}$	Contribution to $D(p\parallel q)$
$1$	$0.9$	$0.5$	${\log }_2(1.8)\approx 0.848$	$0.9(0.848)\approx 0.763$
$0$	$0.1$	$0.5$	${\log }_2(0.2)\approx -2.322$	$0.1(-2.322)\approx -0.232$

Summing the two weighted contributions,

$$D(p\parallel q)\approx 0.763-0.232=0.531\text{ bits}.$$

One outcome contributes a negative value, but the average is nonnegative. If we reverse the arguments,

$$D(q\parallel p)\approx 0.737\text{ bits},$$

because the expectation is now taken under $q$. The two directions describe different modeling mistakes.

3.3 Conditional relative entropy

For joint PMFs $p(x,y)$ and $q(x,y)$, the conditional relative entropy between $p(y\mid x)$ and $q(y\mid x)$, averaged over $p(x)$, is

$$\boxed{\begin{array}{rl}D(p(y\mid x)\parallel q(y\mid x))& :=\sum _{x\in \mathcal{X}}p(x)\sum _{y\in \mathcal{Y}}p(y\mid x){\log }_2\frac{p(y\mid x)}{q(y\mid x)}\\ & ={\mathbb{E}}_{(X,Y)\sim p}\left[{\log }_2\frac{p(Y\mid X)}{q(Y\mid X)}\right].\end{array}}$$

The notation does not explicitly mention the averaging distribution $p(x)$; as in the book, it is understood from context.

3.4 What KL divergence does and does not guarantee

KL divergence satisfies

$$D(p\parallel q)\ge 0,$$

with equality if and only if $p(x)=q(x)$ for every $x\in \mathcal{X}$. This nonnegativity is not obvious from the individual terms, as the example above shows; it is a property of their expectation.

Proof: KL divergence is nonnegative

Let $S=\{x\in \mathcal{X}:p(x)>0\}$. If $q(x)=0$ for any $x\in S$, then $D(p\parallel q)=\infty$, so the claim holds immediately. Otherwise, $q(x)/p(x)>0$ for every $x\in S$.

The elementary inequality

$$\ln u\le u-1,u>0,$$

gives

$$\begin{array}{rl}-(\ln 2)D(p\parallel q)& =\sum _{x\in S}p(x)\ln \frac{q(x)}{p(x)}\\ & \le \sum _{x\in S}p(x)\left(\frac{q(x)}{p(x)}-1\right)\\ & =\sum _{x\in S}q(x)-\sum _{x\in S}p(x)\\ & =1-1=0\end{array}$$

Since $\ln 2>0$, this implies

$$D(p\parallel q)\ge 0.$$

Equality in $\ln u\le u-1$ occurs only at $u=1$. Therefore equality requires $q(x)/p(x)=1$ for every $x\in S$. Normalization then leaves no probability mass for $q$ outside $S$, so $q(x)=p(x)$ for every $x\in \mathcal{X}$. Hence

$$D(p\parallel q)=0⟺p=q.$$

If some outcome satisfies $p(x)>0$ but $q(x)=0$, then

$$D(p\parallel q)=\infty .$$

The model declares an outcome impossible even though it can occur under the data-generating distribution, producing an infinite log-loss.

Finally, KL divergence is not a geometric distance. In general,

$$D(p\parallel q)\ne D(q\parallel p),$$

and KL divergence does not satisfy the triangle inequality.

This expected log-ratio viewpoint connects directly to maximum likelihood estimation and appears as a regularization term in variational autoencoders.

---

4. Mutual Information

Entropy measures uncertainty in one distribution, while KL divergence compares two distributions. Mutual information uses KL divergence to measure dependence between two variables:

$$\boxed{I(X;Y)=D(p_{X,Y}\parallel p_X{p}_Y)}$$

Expanding the definition,

$$I(X;Y)=\sum _{x\in \mathcal{X}}\sum _{y\in \mathcal{Y}}{p}_{X,Y}(x,y){\log }_2\frac{p_{X,Y}(x,y)}{p_X(x)p_Y(y)}.$$

The product $p_X(x)p_Y(y)$ is the joint probability mass function we would have if $X$ and $Y$ were independent. Mutual information therefore quantifies how distinguishable the actual joint distribution is from an independent one.

• If $X$ and $Y$ are independent, $p_{X,Y}(x,y)=p_X(x)p_Y(y)$ and $I(X;Y)=0$.
• If knowing $Y$ reduces uncertainty about $X$, then $I(X;Y)>0$.

4.1 Mutual information as uncertainty reduction

Since $p_{X,Y}(x,y)=p_{X\mid Y}(x\mid y)p_Y(y)$,

$$\begin{array}{rl}I(X;Y)& =\sum _{x,y}{p}_{X,Y}(x,y){\log }_2\frac{p_{X\mid Y}(x\mid y)}{p_X(x)}\\ & =H(X)-H(X\mid Y).\end{array}$$

By symmetry,

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

Combining these expressions with the entropy chain rule gives the fundamental identities

$$\boxed{\begin{array}{rl}I(X;Y)& =H(X)-H(X\mid Y)\\ & =H(Y)-H(Y\mid X)\\ & =H(X)+H(Y)-H(X,Y).\end{array}}$$

Figure 3: A mnemonic for the relationships among marginal entropy, conditional entropy, joint entropy, and mutual information.

Consequently,

$$I(X;Y)=I(Y;X),$$

and a variable contains all of its own uncertainty:

$$I(X;X)=H(X).$$

The venn diagram is a useful illustration: $I(X;Y)$ is drawn as the overlap between $H(X)$ and $H(Y)$, while $H(X\mid Y)$ and $H(Y\mid X)$ are the non-overlapping parts. The algebraic identities above are the actual definitions; the diagram should not replace them.

Main properties of mutual information

For discrete random variables $X$ and $Y$,

1. Equivalent entropy forms

   $$I(X;Y)=H(X)-H(X\mid Y)=H(Y)-H(Y\mid X)=H(X)+H(Y)-H(X,Y).$$

2. Symmetry

   $$I(X;Y)=I(Y;X).$$

3. Nonnegativity and independence

   $$I(X;Y)\ge 0,$$

   with equality if and only if $X$ and $Y$ are independent.

4. Entropy bound

   $$I(X;Y)\le \min \{H(X),H(Y)\}.$$

   Thus, two variables cannot share more information than either variable contains.

   Proof. Since discrete conditional entropy is nonnegative,

   $$H(X\mid Y)\ge 0.$$

   Therefore,

   $$I(X;Y)=H(X)-H(X\mid Y)\le H(X).$$

   By symmetry,

   $$I(X;Y)=H(Y)-H(Y\mid X)\le H(Y).$$

   Combining the two inequalities proves the bound. Equality with $H(X)$ holds exactly when $H(X\mid Y)=0$, so $X$ is determined by $Y$ with probability one; the analogous condition holds for equality with $H(Y)$. This argument is for discrete entropy, since conditional differential entropy need not be nonnegative.

5. Self-information

   $$I(X;X)=H(X).$$

4.2 Conditional mutual information

The conditional mutual information between $X$ and $Y$ given $Z$ is

$$\boxed{\begin{array}{rl}I(X;Y\mid Z)& =H(X\mid Z)-H(X\mid Y,Z)\\ & ={\mathbb{E}}_{(X,Y,Z)\sim p_{X,Y,Z}}\left[{\log }_2\frac{p_{X,Y\mid Z}(X,Y\mid Z)}{p_{X\mid Z}(X\mid Z)p_{Y\mid Z}(Y\mid Z)}\right].\end{array}}$$

It measures how much observing $Y$ reduces uncertainty about $X$ when $Z$ is already known. In the expectation, uppercase $X$, $Y$, and $Z$ are random variables drawn jointly according to $p_{X,Y,Z}$.

---

5. Chain Rules

Chain rules turn one complicated information quantity into a sequence of simpler contributions. The guiding question is:

If the variables are revealed one at a time, how much new uncertainty, information, or model mismatch appears at each step?

No independence assumption is required. Following Section 2.5 of Cover and Thomas, each rule below uses conditioning to avoid counting information that earlier variables have already explained.

5.1 Chain rule for entropy

Suppose we want to describe the entire tuple $(X_1,\dots ,X_n)$. We can describe $X_1$ first, then describe only the part of $X_2$ that remains uncertain after $X_1$ is known, and continue in this way. This gives

$$\boxed{H(X_1,\dots ,X_n)=H(X_1)+\sum _{i=2}^{n}H(X_i\mid X_1,\dots ,X_{i-1})}$$

The first term is written separately because nothing has been revealed before $X_1$. Every later term is conditional on all earlier variables.

For three variables, the rule reads

$$\underset{\text{uncertainty in the whole tuple}}{\underbrace{H(X_1,X_2,X_3)}}=\underset{\text{describe }{X}_1}{\underbrace{H(X_1)}}+\underset{\text{then describe }{X}_2}{\underbrace{H(X_2\mid X_1)}}+\underset{\text{then describe }{X}_3}{\underbrace{H(X_3\mid X_1,X_2)}}.$$

Why does this work? The joint PMF has the probability chain rule

$$p_{X_1,\dots ,X_n}(x_1,\dots ,x_n)=p_{X_1}(x_1)\prod _{i=2}^n{p}_{X_i\mid X_1,\dots ,X_{i-1}}(x_i\mid x_1,\dots ,x_{i-1}).$$

Entropy averages the negative logarithm of this probability. The logarithm converts the product into a sum, so the probability factorization becomes an entropy decomposition.

The variables may be revealed in any order. The total joint entropy stays the same, although the individual conditional terms generally change with the order.

5.2 Chain rule for conditional entropy

Now suppose some side information $Z$ is available before either $X$ or $Y$ is revealed. We first measure the uncertainty left in $X$ given $Z$, and then the uncertainty left in $Y$ after both $Z$ and $X$ are known:

$$\boxed{H(X,Y\mid Z)=H(X\mid Z)+H(Y\mid X,Z)}.$$

The identity can be checked by expressing conditional entropy as a difference of joint entropies:

$$\begin{array}{rl}H(X,Y\mid Z)& =H(X,Y,Z)-H(Z)\\ & =H(X,Z)+H(Y\mid X,Z)-H(Z)\\ & =H(X\mid Z)+H(Y\mid X,Z).\end{array}$$

For a longer sequence, keep $Z$ in the conditioning set at every step:

$$\boxed{H(X_1,\dots ,X_n\mid Z)=H(X_1\mid Z)+\sum _{i=2}^{n}H(X_i\mid X_1,\dots ,X_{i-1},Z)}.$$

The important point is that $Z$ is known throughout the entire process. The conditioning set grows from $Z$ to $(X_1,Z)$, then to $(X_1,X_2,Z)$, and so on. We are not repeatedly learning $Z$; it is background information available from the beginning.

5.3 Chain rule for mutual information

Suppose several variables $(X_1,\dots ,X_n)$ jointly tell us something about $Y$. The mutual-information chain rule attributes that information one variable at a time:

$$\boxed{I(X_1,\dots ,X_n;Y)=I(X_1;Y)+\sum _{i=2}^{n}I(X_i;Y\mid X_1,\dots ,X_{i-1})}$$

For two variables,

$$I(X_1,X_2;Y)=I(X_1;Y)+I(X_2;Y\mid X_1).$$

The first term measures what $X_1$ tells us about $Y$. The second does not count all information in $X_2$ again; it counts only what $X_2$ adds after $X_1$ is already known.

To see the decomposition algebraically, insert and subtract $H(Y\mid X_1)$:

$$\begin{array}{rl}I(X_1,X_2;Y)& =H(Y)-H(Y\mid X_1,X_2)\\ & =[H(Y)-H(Y\mid X_1)]+[H(Y\mid X_1)-H(Y\mid X_1,X_2)]\\ & =I(X_1;Y)+I(X_2;Y\mid X_1).\end{array}$$

Repeating the same step yields the $n$-variable formula. As with entropy, the individual contributions depend on the order of the $X_i$, but their sum is always the total information $I(X_1,\dots ,X_n;Y)$.

5.4 Chain rule for relative entropy

Here we compare two joint models, $p(x,y)$ and $q(x,y)$. Their total mismatch has two sources:

1. The models may assign different probabilities to $X$.
2. Even after the same value of $X$ is given, their conditional models for $Y$ may disagree.

Factor both joint PMFs into these two stages:

$$p(x,y)=p(x)p(y\mid x),q(x,y)=q(x)q(y\mid x).$$

Substituting the factorizations into the log-ratio separates the two sources of mismatch:

$$\begin{array}{rl}D(p(x,y)\parallel q(x,y))& =\sum _{x,y}p(x,y){\log }_2\frac{p(x)p(y\mid x)}{q(x)q(y\mid x)}\\ & =\sum _{x,y}p(x,y){\log }_2\frac{p(x)}{q(x)}+\sum _{x,y}p(x,y){\log }_2\frac{p(y\mid x)}{q(y\mid x)}.\end{array}$$

Therefore,

$$\boxed{D(p(x,y)\parallel q(x,y))=D(p(x)\parallel q(x))+D(p(y\mid x)\parallel q(y\mid x))}$$

The first term measures disagreement about the marginal distribution of $X$. The second is the conditional relative entropy

$$D(p(y\mid x)\parallel q(y\mid x))=\sum _{x}p(x)D(p(\cdot \mid x)\parallel q(\cdot \mid x)),$$

so it averages the conditional mismatch over $x\sim p(x)$. In other words: first pay for using the wrong model of $X$; then, for each observed $X=x$, pay the average additional cost of using the wrong conditional model of $Y$.

---

6. Summary

Quantity	Definition	Interpretation
Entropy	$H(X)=-{\sum }_x{p}_X(x){\log }_2{p}_X(x)$	Uncertainty in $X$
Joint entropy	$H(X,Y)=-{\sum }_{x,y}{p}_{X,Y}(x,y){\log }_2{p}_{X,Y}(x,y)$	Uncertainty in the pair $(X,Y)$
Conditional entropy	$H(Y\mid X)=-{\sum }_{x,y}{p}_{X,Y}(x,y){\log }_2{p}_{Y\mid X}(y\mid x)$	Uncertainty left in $Y$ after observing $X$
KL divergence	$D(p\parallel q)={\sum }_{x}p(x){\log }_2\frac{p(x)}{q(x)}$	Penalty for using $q$ when reality follows $p$
Mutual information	$I(X;Y)=D(p_{X,Y}\parallel p_X{p}_Y)$	Dependence, or shared information, between $X$ and $Y$

The most important identities are

$$H(X,Y)=H(X)+H(Y\mid X),$$ $$I(X;Y)=H(X)-H(X\mid Y)=H(Y)-H(Y\mid X),$$

and

$$I(X;Y)=H(X)+H(Y)-H(X,Y).$$

Together, these definitions provide the basic language used throughout information theory, coding, statistics, and machine learning.

In the next blog I will continue with very important Information Inequalities, Data Processing, and Fano’s Inequality, including Jensen’s inequality, the log-sum inequality, sufficient statistics, and limits on estimation error.

---

Reference

Thomas M. Cover and Joy A. Thomas. Elements of Information Theory, 2nd ed., Sections 2.1-2.5. Wiley, 2006.