[proofplan] We rewrite $H(X \mid Y)$ using the chain rule $H(X \mid Y) = H(X, Y) - H(Y)$, reducing the claim to the subadditivity of joint entropy $H(X, Y) \leq H(X) + H(Y)$. Subadditivity and its equality case both follow from the non-negativity of the Kullback–Leibler divergence (Gibbs' inequality), applied to the joint distribution and the product of the marginals. Rearranging gives the desired inequality and the independence characterisation. [/proofplan]

[step:Apply the chain rule to express $H(X \mid Y)$ via the joint entropy] Let $p_{X,Y}$ denote the joint probability mass function of $(X, Y)$ on $\mathcal{X} \times \mathcal{Y}$, and let $p_X$, $p_Y$ denote the marginal mass functions. By the [Chain Rule for Entropy](/theorems/???), \begin{align*} H(X, Y) = H(Y) + H(X \mid Y). \end{align*} Rearranging, \begin{align*} H(X \mid Y) = H(X, Y) - H(Y). \end{align*} The inequality $H(X \mid Y) \leq H(X)$ is therefore equivalent to \begin{align*} H(X, Y) \leq H(X) + H(Y), \end{align*} which is the statement of subadditivity. [/step]

[step:Prove subadditivity $H(X, Y) \leq H(X) + H(Y)$ via non-negativity of KL divergence]Let $q: \mathcal{X} \times \mathcal{Y} \to [0, 1]$ be the product distribution $q(x, y) := p_X(x) p_Y(y)$. Both $p_{X,Y}$ and $q$ are probability mass functions on the finite set $\mathcal{X} \times \mathcal{Y}$, and $q(x, y) = 0$ implies $p_{X,Y}(x, y) = 0$ (because if $p_X(x) = 0$ then $p_{X,Y}(x, y) = 0$ for all $y$ by marginalisation, and symmetrically for $p_Y(y) = 0$). Hence $p_{X,Y} \ll q$, and the Kullback–Leibler divergence is well defined: \begin{align*} D(p_{X,Y} \,\|\, q) := \sum_{(x, y): p_{X,Y}(x, y) > 0} p_{X,Y}(x, y) \log \frac{p_{X,Y}(x, y)}{p_X(x) p_Y(y)}. \end{align*} Expanding the logarithm of the quotient and using the conventions $0 \log 0 := 0$ and $\sum_{(x, y): p_{X,Y}(x,y) > 0} p_{X,Y}(x, y) \log p_{X,Y}(x, y) = -H(X, Y)$, \begin{align*} D(p_{X,Y} \,\|\, q) &= -H(X, Y) - \sum_{x, y} p_{X,Y}(x, y) \log\bigl(p_X(x) p_Y(y)\bigr) \\ &= -H(X, Y) - \sum_{x} p_X(x) \log p_X(x) - \sum_y p_Y(y) \log p_Y(y) \\ &= -H(X, Y) + H(X) + H(Y), \end{align*} where the second equality uses $\sum_y p_{X,Y}(x, y) = p_X(x)$ and $\sum_x p_{X,Y}(x, y) = p_Y(y)$. By [Gibbs' Inequality](/theorems/???), $D(p_{X,Y} \,\|\, q) \geq 0$, with equality if and only if $p_{X,Y} = q$ pointwise. Therefore \begin{align*} H(X) + H(Y) - H(X, Y) \geq 0, \end{align*} i.e. $H(X, Y) \leq H(X) + H(Y)$.[/step]

[guided]The strategy is to exhibit the deficit $H(X) + H(Y) - H(X, Y)$ as a Kullback–Leibler divergence and invoke Gibbs' inequality. The natural candidate for a reference distribution is $q(x, y) := p_X(x) p_Y(y)$: the product of the marginals, which is the joint distribution that $(X, Y)$ would have if they were independent. First we verify the prerequisites for defining $D(p_{X,Y} \,\|\, q)$. Both are probability mass functions on the finite set $\mathcal{X} \times \mathcal{Y}$: $q$ sums to $\sum_{x,y} p_X(x) p_Y(y) = (\sum_x p_X(x))(\sum_y p_Y(y)) = 1$. We need absolute continuity, $p_{X,Y} \ll q$ — that is, whenever $q(x, y) = 0$ we must have $p_{X,Y}(x, y) = 0$. Suppose $q(x_0, y_0) = 0$. Then $p_X(x_0) = 0$ or $p_Y(y_0) = 0$. If $p_X(x_0) = 0$, then by marginalisation $\sum_y p_{X,Y}(x_0, y) = 0$, and non-negativity of the summands forces $p_{X,Y}(x_0, y) = 0$ for every $y$, in particular $p_{X,Y}(x_0, y_0) = 0$. The case $p_Y(y_0) = 0$ is symmetric. Hence $p_{X,Y} \ll q$. Now we compute: \begin{align*} D(p_{X,Y} \,\|\, q) &= \sum_{x, y} p_{X,Y}(x, y) \log \frac{p_{X,Y}(x, y)}{p_X(x) p_Y(y)} \\ &= \sum_{x, y} p_{X,Y}(x, y) \log p_{X,Y}(x, y) - \sum_{x, y} p_{X,Y}(x, y) \log p_X(x) - \sum_{x, y} p_{X,Y}(x, y) \log p_Y(y) \\ &= -H(X, Y) - \sum_x \log p_X(x) \sum_y p_{X,Y}(x, y) - \sum_y \log p_Y(y) \sum_x p_{X,Y}(x, y) \\ &= -H(X, Y) - \sum_x p_X(x) \log p_X(x) - \sum_y p_Y(y) \log p_Y(y) \\ &= -H(X, Y) + H(X) + H(Y). \end{align*} The term-by-term splitting of the logarithm, the switch in summation order, and the marginalisations are all legitimate because the sums are finite. (Where $p_{X,Y}(x, y) = 0$ we use the convention $0 \log 0 := 0$, consistent with $\lim_{t \downarrow 0} t \log t = 0$; where $p_X(x) = 0$ or $p_Y(y) = 0$ but $p_{X,Y}(x, y) = 0$, the entire term vanishes so no $\log 0$ issue arises.) [Gibbs' Inequality](/theorems/???) states: if $p$ and $q$ are probability mass functions on a countable set with $p \ll q$, then $D(p \,\|\, q) \geq 0$, with equality if and only if $p = q$. Its hypotheses are met ($p_{X,Y} \ll q$ was just verified), so \begin{align*} H(X) + H(Y) - H(X, Y) = D(p_{X,Y} \,\|\, q) \geq 0, \end{align*} i.e. $H(X, Y) \leq H(X) + H(Y)$. Why start from KL divergence rather than directly convexifying with Jensen? Both work; KL packages the computation more cleanly and simultaneously delivers the equality case for free via the Gibbs equality condition, which is exactly what we need next.[/guided]

[step:Combine the chain rule with subadditivity] Substituting subadditivity into the chain-rule identity from the first step, \begin{align*} H(X \mid Y) = H(X, Y) - H(Y) \leq \bigl(H(X) + H(Y)\bigr) - H(Y) = H(X). \end{align*} This proves the inequality. [/step]

[step:Characterise the equality case via independence] Equality $H(X \mid Y) = H(X)$ holds if and only if subadditivity is tight, i.e. \begin{align*} H(X, Y) = H(X) + H(Y), \end{align*} which by the computation in the second step is equivalent to $D(p_{X,Y} \,\|\, q) = 0$. By the equality clause of [Gibbs' Inequality](/theorems/???), this holds if and only if $p_{X,Y}(x, y) = p_X(x) p_Y(y)$ for all $(x, y) \in \mathcal{X} \times \mathcal{Y}$, which is the definition of $X$ and $Y$ being independent. This completes the proof of both the inequality and the equality characterisation. [/step]