Entropy, Joint Entropy, Conditional Entropy, and the Chain Rule

Intuition Beginner

Flip a fair coin. Before it lands, you are uncertain about the outcome. If I told you the result, I would remove that uncertainty. The amount of information in a single coin flip is one bit. That word already does the right thing: a "bit" is the information content of a binary choice between two equally likely outcomes.

Now flip a biased coin that lands heads 99 times out of 100. You are almost sure it will be heads. If I tell you it was heads, I barely told you anything — you already knew. If I tell you it was tails, you learned a lot, because that was genuinely surprising. Information content is large for surprising outcomes and small for expected ones.

Shannon entropy is the average information content. For the fair coin, the average surprise is one bit. For the 99/1 coin, the average surprise is much less — around 0.08 bits — because most of the time the unsurprising thing happens. Entropy measures how much uncertainty a random variable contains on average, before you observe it.

Why does this matter? Because entropy tells you how well you can compress data. If a coin is almost always heads, you can describe a long sequence of flips very compactly: "99 heads, then one tails" instead of writing out every flip. The entropy gives the compression limit — you cannot compress below it without losing information. This is Shannon's source coding theorem, and it makes entropy the central quantity of information theory.

The chain rule is the last piece. If you have two random variables $X$ and $Y$, the total uncertainty $H(X,Y)$ equals the uncertainty in $X$ plus the remaining uncertainty in $Y$ once you know $X$. Written as $H(X,Y)=H(X)+H(Y|X)$, it says: total surprise decomposes into the surprise of the first variable plus the surprise of the second given that you already saw the first. This decomposition is the workhorse of every proof in the subject.

Visual Beginner

Figure: a bar chart of the probability distribution of a loaded die. The die has faces 1 through 6 with probabilities $0.40,0.25,0.15,0.10,0.07,0.03$. Below the chart, a single number: the entropy $H\approx 2.14$ bits. A second bar chart next to it shows a uniform die (all faces $1/6$) with entropy $H={\log }_{2}6\approx 2.58$ bits. The more concentrated distribution has lower entropy.

Distribution	Entropy (bits)	Visual intuition
Fair coin (50/50)	1.00	Maximum uncertainty for 2 outcomes
Biased coin (99/1)	0.08	Almost no uncertainty
Fair die (1/6 each)	2.58	Maximum for 6 outcomes
Loaded die (40/25/15/10/7/3)	2.14	Less than fair — some outcomes are predictable
Deterministic (100/0)	0.00	No uncertainty at all

The pattern: spread-out distributions have high entropy; concentrated distributions have low entropy. The maximum is the uniform distribution; the minimum is zero, at a point mass.

Worked example Beginner

A weather station classifies each day as sunny, cloudy, or rainy with probabilities $p_{\text{sun}}=0.5$, $p_{\text{cloud}}=0.3$, $p_{\text{rain}}=0.2$. What is the entropy of tomorrow's weather?

Step 1. Compute the information content of each outcome: ${\log }_2(1/p)$.

• Sunny: ${\log }_2(1/0.5)={\log }_{2}2=1$ bit.
• Cloudy: ${\log }_2(1/0.3)={\log }_2(3.333)\approx 1.74$ bits.
• Rainy: ${\log }_2(1/0.2)={\log }_{2}5\approx 2.32$ bits.

Rain is the most surprising outcome (lowest probability, highest information). Sunny is the least surprising.

Step 2. Take the average, weighted by how likely each outcome is:

$$H=0.5\times 1+0.3\times 1.74+0.2\times 2.32=0.50+0.522+0.464=1.486\text{ bits}.$$

Step 3. Compare. The maximum entropy for three outcomes is ${\log }_{2}3\approx 1.585$ bits (uniform distribution). Our weather has $H=1.486$ bits, which is less — sunny days are somewhat predictable.

What this tells us. Each day's weather carries about 1.5 bits of information. Over a year of 365 days, the total information is roughly $365\times 1.486\approx 542$ bits. A compression scheme cannot describe a year of weather using fewer than about 542 bits on average; the entropy is the fundamental limit.

Check your understanding Beginner

Formal definition Intermediate+

Let $X$ be a discrete random variable taking values in a finite set $\mathcal{X}$ with probability mass function $p(x)=\mathrm{Pr}[X=x]$.

Definition (Shannon entropy). The entropy of $X$ is

$$H(X)=-\sum _{x\in \mathcal{X}}p(x){\log }_{2}p(x),$$

where $0\log 0$ is defined by its continuous extension to be $0$. The unit is bits (base-2 logarithm). Changing the base to $e$ gives entropy in nats; to 10, in dits.

The logarithm of $1/p(x)$ is the information content (or surprisal) of outcome $x$:

$$i(x)={\log }_2\frac{1}{p(x)}.$$

Entropy is the expected information content: $H(X)=\mathbb{E}[{\log }_2(1/p(X))]$.

Definition (Joint entropy). For a pair $(X,Y)$ with joint pmf $p(x,y)$ on $\mathcal{X}\times \mathcal{Y}$:

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

Definition (Conditional entropy). The conditional entropy of $X$ given $Y$ is

$$H(X|Y)=-\sum _{y\in \mathcal{Y}}p(y)\sum _{x\in \mathcal{X}}p(x|y){\log }_{2}p(x|y)={\mathbb{E}}_Y[H(X|Y=y)].$$

Equivalently, $H(X|Y)=H(X,Y)-H(Y)$.

Counterexamples to common slips

• Entropy depends on the distribution, not the values. $H(X)$ is determined entirely by the probability vector $(p_1,\dots ,p_n)$, not by the labels of the outcomes. A die labelled $\{1,2,3,4,5,6\}$ and one labelled $\{a,b,c,d,e,f\}$ have the same entropy if their probability vectors match.

• Conditional entropy is not $H(X|Y=y)$. The quantity $H(X|Y)$ is the average of $H(X|Y=y)$ over all values of $y$ weighted by $p(y)$. It is a single number, not a function of $y$.

• Entropy can be zero but not negative. $H(X)=0$ if and only if $X$ is deterministic. Since each term $-p\log p\ge 0$ and the sum is non-negative, entropy is always at least zero.

Key theorem with proof Intermediate+

Theorem (Chain rule for entropy). For any collection of discrete random variables $X_1,X_2,\dots ,X_n$ with joint pmf $p(x_1,\dots ,x_n)$:

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

Proof. By induction on $n$. The base case $n=1$ is $H(X_1)=H(X_1)$. For the inductive step, write the joint entropy of $n$ variables as the joint entropy of the first $n-1$ plus the conditional entropy of the $n$-th given the first $n-1$:

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

This is the two-variable identity $H(A,B)=H(A)+H(B|A)$ with $A=(X_1,\dots ,X_{n-1})$ and $B=X_n$, which follows directly from the definition:

$$\begin{array}{rl}H(A,B)& =-\sum _{a,b}p(a,b)\log p(a,b)\\ & =-\sum _{a,b}p(a,b)\log (p(a)\cdot p(b|a))\\ & =-\sum _{a}p(a)\log p(a)\sum _{b}p(b|a)-\sum _{a}p(a)\sum _{b}p(b|a)\log p(b|a)\\ & =H(A)+H(B|A).\square \end{array}$$

Bridge. The chain rule is the structural identity that organises the entire subject. It builds toward the asymptotic equipartition property in 46.02.01 by letting us decompose the entropy of a sequence $X^n=(X_1,\dots ,X_n)$ into a sum of conditional entropies that, for stationary ergodic sources, converges to the entropy rate $H(\mathcal{X})$. It appears again in the Fano inequality 46.03.03 as $H(X|Y)=H(X,Y)-H(Y)$, the foundational reason why conditional entropy controls the probability of guessing $X$ from $Y$. The decomposition is exactly the mechanism by which source coding, channel coding, and rate-distortion theorems extract their operational quantities from the entropy function.

Exercises Intermediate+

Lean formalization Intermediate+

Mathlib does not define Shannon entropy on discrete distributions. The PMF type for probability mass functions exists (ProbabilityTheory.PMF), but there is no functional $H:\text{PMF}\alpha \to \mathbb{R}$, no joint-entropy definition for product distributions, no conditional entropy, and no chain-rule proof. The elementary inequalities (non-negativity, maximality at the uniform, conditioning reduces entropy) are absent. The uniqueness theorem (Khinchin's axioms) is unformalised. A Codex.InformationTheory.Entropy module defining $H$ on PMF and proving the chain rule from the product expansion would be the load-bearing first step; this unit ships without it.

Advanced results Master

Shannon's axiomatic characterisation

Shannon's 1948 paper introduced entropy not by definition alone but by a set of axioms that pin it down uniquely. For a function $H(p_1,\dots ,p_n)$ on finite probability distributions, the four axioms are:

1. Continuity: $H$ is continuous in each $p_i$.
2. Symmetry: $H$ is invariant under permutation of $(p_1,\dots ,p_n)$.
3. Maximality: $H(p_1,\dots ,p_n)\le H(1/n,\dots ,1/n)=\log n$.
4. Grouping: If $p_n=q_1+q_2$ for a partition of the $n$-th outcome into two sub-outcomes, then

$$H(p_1,\dots ,p_{n-1},q_1,q_2)=H(p_1,\dots ,p_n)+p_{n}H\left(\frac{q_1}{p_n},\frac{q_2}{p_n}\right).$$

The grouping axiom is the load-bearing requirement. It says: if you refine an outcome into two sub-outcomes, the entropy increases by the entropy of the refinement weighted by the probability of the refined event. Shannon proved that the unique (up to a multiplicative constant, fixed by the log base) function satisfying all four axioms is $H=-\sum p_i\log p_i$.

Khinchin (1953) independently gave a cleaner set: continuity, symmetry, maximality at the uniform, and additivity ($H(p\ast q)=H(p)+H(q)$ for independent distributions). Either set characterises entropy, and the uniqueness theorem tells you that no other functional can play the same role.

The Han inequality and Shearer-style bounds

The chain rule implies a family of inequalities that constrain the joint entropy of collections of variables. The most useful is the Han inequality: for any $n$ random variables $X_1,\dots ,X_n$,

$$H(X_1,\dots ,X_n)\le \frac{1}{n-1}\sum _{i=1}^{n}H(X_1,\dots ,X_{i-1},X_{i+1},\dots ,X_n).$$

This follows from subadditivity: each $H(X_{-i})\ge H(X_{1:n})-H(X_i)$ (where $X_{-i}$ denotes all variables except $X_i$), and summing over $i$ gives $n\cdot H(X_{1:n})\le \sum H(X_i)+\sum H(X_{-i})$. Combined with $\sum H(X_i)\ge H(X_{1:n})$ (subadditivity), the result follows.

A more general form, Shearer's lemma, states: if $\mathcal{S}$ is a collection of subsets of $[n]$ such that each element $i\in [n]$ appears in at least $k$ members of $\mathcal{S}$, then $k\cdot H(X_1,\dots ,X_n)\le {\sum }_{S\in \mathcal{S}}H(X_S)$. This is a workhorse in combinatorial applications of entropy and cross-refers the probabilistic method in 40.07.01.

Strong concavity and the entropy metric

The function $p\mapsto H(p)$ is strictly concave on the simplex ${\Delta }_n$. This means that for any two distributions $p,q$ and any $\lambda \in (0,1)$:

$$H(\lambda p+(1-\lambda )q)\ge \lambda H(p)+(1-\lambda )H(q),$$

with equality iff $p=q$. The concavity has a direct operational meaning: mixing two sources (drawing from $p$ with probability $\lambda$ and from $q$ with probability $1-\lambda$) creates more uncertainty than either source alone, weighted by the mixing proportions.

Synthesis. Entropy is the unique functional on probability distributions satisfying Shannon's four axioms; the chain rule $H(X_{1:n})=\sum H(X_i|X_{<i})$ decomposes joint uncertainty into a telescoping sum of conditional uncertainties; subadditivity $H(X_{1:n})\le \sum H(X_i)$ is the shadow of independence, with equality iff the variables are independent; and the Han and Shearer inequalities provide combinatorial leverage by constraining how entropy distributes across subsets. The central insight builds toward the AEP 46.02.01, where entropy becomes the exponent governing the size of the typical set, and generalises to the relative entropy $D(p\Vert q)$ 46.01.02, where the asymmetry between two distributions is measured by the same logarithmic structure.

Full proof set Master

Proposition (Entropy of a function). Let $Y=f(X)$ for a deterministic function $f$. Then $H(Y)\le H(X)$, with equality iff $f$ is injective on the support of $X$.

Proof. Since $Y=f(X)$, the value of $X$ determines $Y$, so $H(Y|X)=0$. By the chain rule, $H(X,Y)=H(X)+H(Y|X)=H(X)$. Also $H(X,Y)=H(Y)+H(X|Y)\ge H(Y)$, since $H(X|Y)\ge 0$. Therefore $H(X)=H(X,Y)\ge H(Y)$.

Equality holds iff $H(X|Y)=0$, meaning $X$ is a function of $Y$. But $Y=f(X)$, so this says $X$ is a function of $f(X)$, which holds iff $f$ is injective on the support. $\square$

Proposition (Fano's inequality, preliminary form). If $X$ takes values in $\mathcal{X}$ and $\hat{X}$ is an estimator of $X$ with error probability $P_e=\mathrm{Pr}[\hat{X}\ne X]$, then

$$H(X|\hat{X})\le H_b(P_e)+P_e{\log }_2(|\mathcal{X}|-1),$$

where $H_b(p)=-p\log p-(1-p)\log (1-p)$ is the binary entropy.

Proof. Define the error indicator $E=1[\hat{X}\ne X]$. By the chain rule,

$$H(X|\hat{X})=H(E,X|\hat{X})=H(E|\hat{X})+H(X|E,\hat{X}).$$

Since $E$ is binary, $H(E|\hat{X})\le H(E)=H_b(P_e)$. For $H(X|E,\hat{X})$: when $E=0$ (correct guess), $X=\hat{X}$ is determined, contributing $0$. When $E=1$ (wrong guess), $X$ is among the $|\mathcal{X}|-1$ remaining values, contributing at most $\log (|\mathcal{X}|-1)$. Weighted by $P_e$:

$$H(X|E,\hat{X})\le (1-P_e)\cdot 0+P_e\cdot \log (|\mathcal{X}|-1)=P_e\log (|\mathcal{X}|-1).\square$$

Connections Master

• 37.01.01 — The probability-space formalism on which entropy is built; entropy is a functional on distributions, which are defined on measurable spaces.
• 46.01.02 — Mutual information and KL divergence are constructed from entropy and conditional entropy; the chain rule proved here is the algebraic engine for their calculus.
• 46.02.01 — The AEP uses the chain rule to decompose $H(X_1,\dots ,X_n)$ and shows that i.i.d. draws concentrate in a typical set of size $2^{nH}$.
• 46.02.02 — Shannon's source coding theorem proves the operational meaning of entropy: the minimum achievable compression rate equals $H(X)$.
• 37.07.05 — Sanov's theorem in large deviations measures the rarity of empirical distributions by the KL divergence from the true distribution; entropy is the zero point of this landscape.
• 40.07.01 — The probabilistic method uses entropy-based counting arguments (Shearer's lemma, the Loomis-Whitney inequality) to bound the size of combinatorial objects.

Historical & philosophical context Master

Claude Shannon introduced entropy in his 1948 paper "A Mathematical Theory of Communication" (Bell System Technical Journal 27, 379-423 and 623-656). The paper's title was expanded to "The Mathematical Theory of Communication" when republished as a book with Warren Weaver in 1949. Shannon was working at Bell Labs on the fundamental limits of signal transmission; his insight was that information could be quantified independently of its meaning, purely in terms of the statistics of the source.

The formula $H=-\sum p\log p$ was not new — it had appeared in statistical mechanics as Boltzmann's $H$-theorem (1872) and in Gibbs' entropy $S=-k_B\sum p\log p$ for thermodynamic ensembles. Shannon's contribution was the axiomatic derivation (the four axioms above), the operational interpretation (compression limit), and the channel coding theorem that gives entropy a second operational meaning as the maximum reliable communication rate. John von Neumann, upon seeing the formula, reportedly told Shannon to call it "entropy" because "nobody knows what entropy really is, so in a debate you will always have the advantage" (an anecdote relayed by McIrvine and Tribus in their 1971 Energy and Information).

Aleksandr Khinchin gave a cleaner axiomatic treatment in 1953 (Uspekhi Mat. Nauk 8, translated by Silverman as Mathematical Foundations of Information Theory, Dover 1957), establishing the uniqueness theorem under the symmetry-maximality-additivity axioms. Imre Csiszár extended the framework to an I-measure representation in the 1970s, showing that information quantities for collections of random variables satisfy the same inclusion-exclusion identities as signed measures on an abstract space, making the Venn diagram for entropy, conditional entropy, and mutual information not merely an analogy but a theorem.

Bibliography Master

@article{shannon1948,
  author  = {Shannon, C. E.},
  title   = {A Mathematical Theory of Communication},
  journal = {Bell System Technical Journal},
  volume  = {27},
  pages   = {379--423 and 623--656},
  year    = {1948},
}
@book{cover-thomas2006,
  author    = {Cover, T. M. and Thomas, J. A.},
  title     = {Elements of Information Theory},
  edition   = {2nd},
  publisher = {Wiley},
  year      = {2006},
}
@book{csiszar-korner2011,
  author    = {Csisz{\'a}r, I. and K{\"o}rner, J.},
  title     = {Information Theory: Coding Theorems for Discrete Memoryless Systems},
  edition   = {2nd},
  publisher = {Cambridge University Press},
  year      = {2011},
}
@book{khinchin1957,
  author    = {Khinchin, A. I.},
  title     = {Mathematical Foundations of Information Theory},
  publisher = {Dover},
  year      = {1957},
  note      = {Translated by R. A. Silverman from the 1953 Russian edition},
}
@article{han1975,
  author  = {Han, T. S.},
  title   = {Nonnegative Entropy Measures of Multivariate Symmetric Correlations},
  journal = {Information and Control},
  volume  = {36},
  pages   = {133--156},
  year    = {1975},
}
@article{chung-graham-wilson-1989,
  author  = {Chung, F. R. K. and Graham, R. L. and Wilson, R. M.},
  title   = {Quasi-Random Graphs},
  journal = {Combinatorica},
  volume  = {9},
  pages   = {345--362},
  year    = {1989},
  note    = {Contains the entropy-based quasi-random characterisations},
}