Finite-Alphabet Entropy and Divergence

Every marginal coordinate is nonnegative because it is a finite sum of nonnegative entries of $p_{UV}$. By [F2], ${\sum }_u{p}_U(u)={\sum }_u{\sum }_v{p}_{UV}(u,v)={\sum }_{(u,v)}{p}_{UV}(u,v)=1$, and the same calculation with the order reversed gives ${\sum }_v{p}_V(v)=1$. Thus both marginals are probability vectors by [F1].

Fix $v$ with $p_V(v)>0$. Each ratio $p_{UV}(u,v)\mathrm{/}{p}_V(v)$ is nonnegative, and ${\sum }_u{p}_{U\mathrm{\mid }v}(u)=({\sum }_u{p}_{UV}(u,v))\mathrm{/}{p}_V(v)=p_V(v)\mathrm{/}{p}_V(v)=1$. Hence $p_{U\mathrm{\mid }v}$ is a probability vector by [F1]. The same argument with $u$ fixed gives $p_{V\mathrm{\mid }u}$. If $p_{UVW}$ is a joint pmf and $p_W(w)>0$, first apply this argument to the pair of finite alphabets $\mathcal{U}\times \mathcal{V}$ and $\mathcal{W}$; then apply step 1.1 to the resulting conditional pmf on $\mathcal{U}\times \mathcal{V}$. This gives the last assertion.

By [F9], the finite vectors define probability spaces on $(S,\mathcal{P}(S))$, with every singleton measurable; [F2] gives their event weights. If $p_i>0=q_i$, then $P(\{i\})>0=Q(\{i\})$, so [F3] gives $P\ll ̸Q$. The general definition [F6] and finite convention [F1] both give $+\mathrm{\infty }$.

Suppose $p_i=0$ whenever $q_i=0$. If $Q(A)=0$, the finite sum ${\sum }_{i\in A}{q}_i=0$ and nonnegativity force $q_i=0$ for every $i\in A$; hence $p_i=0$ for those $i$ and $P(A)=0$. Thus $P\ll Q$ by [F3]. Define $r_i=p_i\mathrm{/}{q}_i$ when $q_i>0$ and $r_i=0$ when $q_i=0$. Since every subset of $S$ is measurable, this finite function is measurable. For every $A\subseteq S$, [F5] gives ${\int }_{A}rdQ={\sum }_{i\in A}{r}_i{q}_i={\sum }_{i\in A}{p}_i=P(A)$, so [F4] identifies $r$ as a Radon–Nikodym derivative. It is explicitly constructed; no choice is used in this step.

Under the AC interface assumption [A1], substitute the density from step 1.2 into [F8], using the logarithm convention [F7]. Applying [F5] to $\mathrm{\ell }(i)=\ln r_i$ for $r_i>0$ and $\mathrm{\ell }(i)=0$ for $r_i=0$ gives $D(P\mathrm{\parallel }Q)={\sum }_{i:p_i>0}{p}_i\ln r_i={\sum }_{i:p_i>0}{p}_i\ln (p_i\mathrm{/}{q}_i)$; coordinates with $p_i=0$ contribute $0$ by [F1].

Step 1.1 handles support failure, while step 2.1 proves equality with the finite sum when $p$ is supported by $q$. These cases exhaust the finite vectors in the Statement.

Define $f(0)=0$ and $f(t)=t\ln t$ for $t>0$. On $(0,\mathrm{\infty })$, [F3] and [F4] give $f^{\mathrm{\prime }}(t)=\ln t+1$, which is strictly increasing by [F2]; [F2] and [F5] also give continuity of $f$ on every positive compact interval. If $0<u<v<w$, [F6] on $[u,v]$ and $[v,w]$ gives secant slopes $f^{\mathrm{\prime }}(c_1)$ and $f^{\mathrm{\prime }}(c_2)$ with $c_1<v<c_2$; strict increase makes the first slope smaller, which rearranges to the strict convexity inequality at $v$. For an endpoint $0<y$ and $0<\lambda <1$, $f(\lambda y)=\lambda f(y)+\lambda y\ln \lambda <\lambda f(y)+(1-\lambda )f(0)$ since $\ln \lambda <0$ by [F2]. Thus $f$ is strictly convex on $[0,\mathrm{\infty })$.

If $A=0$, nonnegativity forces all $a_i=0$, so both sides are $0$. If $A>0=B$, all $b_i=0$ and at least one $a_i>0$, so both sides are $+\mathrm{\infty }$. If $A,B>0$ but some $a_i>0=b_i$, the left side is $+\mathrm{\infty }$ while the right side is finite. It remains to handle $A,B>0$ with $a_i=0$ whenever $b_i=0$.

For the remaining case set $J=\{i:b_i>0\}$, ${\lambda }_i=b_i\mathrm{/}B$, and $x_i=a_i\mathrm{/}{b}_i$ for $i\in J$. These weights are positive and sum to one, and ${\sum }_{i\in J}{\lambda }_i{x}_i=A\mathrm{/}B$. By [F8] and the convexity proved in step 1.1, $Bf(A\mathrm{/}B)\le {\sum }_{i\in J}{b}_{i}f(a_i\mathrm{/}{b}_i)$. Expanding $f$ turns this into the desired inequality, including coordinates with $a_i=0<b_i$ because $f(0)=0$.

If all $x_i$ are equal, their weighted mean is $A\mathrm{/}B$ and Jensen is an equality; together with $a_i=0$ when $b_i=0$, this is exactly $a_i=(A\mathrm{/}B)b_i$ for every coordinate. Conversely, suppose they are not all equal, so $\mathrm{\mid }J\mathrm{\mid }\ge 2$ and $0<{\lambda }_j<1$ for every $j$. For each $j\in J$, let ${\mu }_i={\lambda }_i\mathrm{/}(1-{\lambda }_j)$ for $i\mathrm{\ne }j$ and $y_j={\sum }_{i\mathrm{\ne }j}{\mu }_i{x}_i$. Some $j$ has $x_j\mathrm{\ne }{y}_j$: otherwise $x_j=(A\mathrm{/}B-{\lambda }_j{x}_j)\mathrm{/}(1-{\lambda }_j)$ for every $j$, forcing each $x_j=A\mathrm{/}B$. Fix such a $j$. Then $A\mathrm{/}B={\lambda }_j{x}_j+(1-{\lambda }_j)y_j$; strict convexity from step 1.1 gives $f(A\mathrm{/}B)<{\lambda }_{j}f(x_j)+(1-{\lambda }_j)f(y_j)$. By [F8] on the normalized remaining weights, $f(y_j)\le {\sum }_{i\mathrm{\ne }j}{\mu }_{i}f(x_i)$, making the total Jensen inequality strict.

Steps 1.2–2.2 prove the inequality in every extended-real support case and, when $A,B>0$, prove equality exactly at proportional vectors.

If $p_i>0=q_i$ for some $i$, [F1] gives $D(p\mathrm{\parallel }q)=+\mathrm{\infty }$, so nonnegativity holds and equality to zero is impossible. Otherwise $p_i=0$ whenever $q_i=0$; apply [F2] to $a_i=p_i$, $b_i=q_i$. Both sums equal $1$, and its left side is $D(p\mathrm{\parallel }q)$, so $D(p\mathrm{\parallel }q)\ge 0$.

In the absolutely continuous case, [F2] says equality holds exactly when $p_i=(1\mathrm{/}1)q_i=q_i$ for every coordinate. Conversely, if $p=q$, every positive-support term in [F1] is $p_i\ln 1=0$, so $D(p\mathrm{\parallel }q)=0$. Together with step 1.1 this proves the iff statement, including zero coordinates.

By [F1], $\ln b>0$, so division by $\ln b$ preserves order and sends $+\mathrm{\infty }$ to $+\mathrm{\infty }$. For entropy, replacing each $\ln p_i$ by ${\log }_b{p}_i=\ln p_i\mathrm{/}\ln b$ factors the same positive scalar out of the finite sum; zero terms remain zero by [F1]. The identical termwise calculation applies to every finite KL sum when $p$ is supported by $q$.

If $p_i>0=q_i$, both base conventions set the KL value to $+\mathrm{\infty }$, agreeing with the extended-real equation. Conditional entropy is a finite weighted sum of the entropy terms from step 1.1 by [F3]; mutual information is a finite KL sum by [F4]; conditional mutual information is a finite weighted sum of conditional KL sums by [F5]. Factoring $1\mathrm{/}\ln b$ from each of these finite sums proves all remaining conversions.

Fix $z$ with $p_Z(z)>0$. By [F5], $p_{XY\mathrm{\mid }z}$ and its marginals are pmfs. If $p_{XY\mathrm{\mid }z}(x,y)>0$, then both marginals are positive at $x,y$. Expanding [F1] and collecting terms using [F3] gives $D(p_{XY\mathrm{\mid }z}\mathrm{\parallel }{p}_{X\mathrm{\mid }z}\otimes p_{Y\mathrm{\mid }z})=H(p_{X\mathrm{\mid }z})+H(p_{Y\mathrm{\mid }z})-H(p_{XY\mathrm{\mid }z})$; zero coordinates contribute $0$, so no logarithm of zero is taken.

Multiply the identity in step 1.1 by $p_Z(z)$ and sum over positive-mass $z$. By [F1] and [F2], this gives the stated entropy identity. Each conditional KL is nonnegative by [F4], and every weight in the sum is positive. Hence the total is zero exactly when each conditional KL is zero, which by [F4] is exactly $p_{XY\mathrm{\mid }z}=p_{X\mathrm{\mid }z}\otimes p_{Y\mathrm{\mid }z}$ for every positive-mass $z$.

Fix $z$ with $p_Z(z)>0$ and write $q_{xy}=p_{XY\mathrm{\mid }z}(x,y)$, $q_x={\sum }_y{q}_{xy}$; for $q_x>0$ define $q_{y\mathrm{\mid }x}=q_{xy}\mathrm{/}{q}_x$. By [F4], these are pmfs and $q_{xy}=q_x{q}_{y\mathrm{\mid }x}$ on positive support. On that support both factors are positive, so the product law [F6] gives $-{\sum }_{q_{xy}>0}{q}_{xy}\ln q_{xy}=-{\sum }_{q_x>0}{\sum }_{y:q_{y\mathrm{\mid }x}>0}{q}_x{q}_{y\mathrm{\mid }x}(\ln q_x+\ln q_{y\mathrm{\mid }x})$. For every $q_x>0$, ${\sum }_{y:q_{y\mathrm{\mid }x}>0}{q}_{y\mathrm{\mid }x}=1$. Thus the terms involving $\ln q_x$ sum to $-{\sum }_{q_x>0}{q}_x\ln q_x$, and the remaining terms are ${\sum }_{q_x>0}{q}_x(-{\sum }_{q_{y\mathrm{\mid }x}>0}{q}_{y\mathrm{\mid }x}\ln q_{y\mathrm{\mid }x})$, exactly $H(q_X)+{\sum }_x{q}_{x}H(q_{Y\mathrm{\mid }x})$ by [F5]. Weighting this equality by $p_Z(z)$ and summing over positive-mass $z$ using [F1] proves $H(X,Y\mathrm{\mid }Z)=H(X\mathrm{\mid }Z)+H(Y\mathrm{\mid }X,Z)$. Zero atoms are omitted from the displayed logarithmic sums.

Every positive joint atom has positive marginals by [F4]; applying the quotient and product laws [F6] to [F2] gives $I(U;V)={\sum }_{p_{uv}>0}{p}_{uv}(\ln p_{uv}-\ln p_U(u)-\ln p_V(v))$. Grouping the finite sums by $u,v$, using [F4] to know the marginals, and applying [F5] yields $I(U;V)=H(U)+H(V)-H(U,V)$. Also, [F1] and $p_{U\mathrm{\mid }v}=p_{UV}\mathrm{/}{p}_V$ on positive support give $H(U\mathrm{\mid }V)=-{\sum }_{p_{uv}>0}{p}_{uv}\ln (p_{uv}\mathrm{/}{p}_V(v))=H(U,V)-H(V)$. Thus $I(U;V)=H(U)-H(U\mathrm{\mid }V)$, and exchanging $U,V$ gives the other form. All sums are finite.

Apply step 1.1 and [F3] to get $I(X;Y\mathrm{\mid }Z)=H(Y\mathrm{\mid }Z)-H(Y\mathrm{\mid }X,Z)$. By step 1.2, $H(Y,Z)=H(Z)+H(Y\mathrm{\mid }Z)$ and $H(X,Y,Z)=H(Z)+H(X,Y\mathrm{\mid }Z)=H(X,Z)+H(Y\mathrm{\mid }X,Z)$. Therefore $I(X;Y,Z)=H(X)+H(Y,Z)-H(X,Y,Z)=I(X;Z)+I(X;Y\mathrm{\mid }Z)$. Every entropy is a finite sum, so no extended-real subtraction occurs.

For each $y$ with $p_Y(y)>0$, the hypothesis makes $p_{XZ\mathrm{\mid }y}=p_{X\mathrm{\mid }y}\otimes p_{Z\mathrm{\mid }y}$. The corresponding conditional KL term in the definition of $I(X;Z\mathrm{\mid }Y)$ is therefore $D(p_{XZ\mathrm{\mid }y}\mathrm{\parallel }{p}_{X\mathrm{\mid }y}\otimes p_{Z\mathrm{\mid }y})=0$, so the finite weighted sum gives $I(X;Z\mathrm{\mid }Y)=0$.

Equating the two expansions in [F1] and using step 1.1 gives $I(X;Y)-I(X;Z)=I(X;Y\mathrm{\mid }Z)$. This is nonnegative by [F2], proving data processing. The difference vanishes exactly when $I(X;Y\mathrm{\mid }Z)=0$, and [F2] identifies that equality case with conditional independence of $X,Y$ given each positive-mass $z$.

If $m=1$, then $X$ is constant and $H(X\mathrm{\mid }Y)=0$. Hence assume $m\ge 2$. The factorization in the hypotheses is the Markov condition $X\to Y\to \widehat{X}$. By [F1], $I(X;\widehat{X})\le I(X;Y)$; subtracting from the finite value $H(X)$ and using [F2] gives $H(X\mathrm{\mid }Y)\le H(X\mathrm{\mid }\widehat{X})$.

Set $E=\mathbf{1}\{X\mathrm{\ne }\widehat{X}\}$. Since $E$ is determined by $(X,\widehat{X})$, [F2] gives $H(X\mathrm{\mid }\widehat{X})=H(E\mathrm{\mid }\widehat{X})+H(X\mathrm{\mid }E,\widehat{X})$. The law of $E$ is Bernoulli with mass $P_e$ at $1$, so [F5] gives $H(E)=h_2(P_e)$.

The finite MI identity in [F2] gives $H(E)-H(E\mathrm{\mid }\widehat{X})=I(E;\widehat{X})$. By [F3], this MI, which is KL between the joint law and product marginals, is nonnegative. Thus $H(E\mathrm{\mid }\widehat{X})\le h_2(P_e)$.

On $E=0$, $X=\widehat{X}$, so the conditional entropy of $X$ given $(E,\widehat{X})$ is zero. On $E=1$ and a fixed value of $\widehat{X}$, at most $m-1$ values of $X$ remain. For any pmf $r$ on at most $k=m-1$ points, pad by zeros to a $k$-vector and compare with the uniform vector $u_k$: [F3] gives $0\le D(r\mathrm{\parallel }{u}_k)=\ln k-H(r)$, so $H(r)\le \ln (m-1)$. Averaging these conditional entropies yields $H(X\mathrm{\mid }E,\widehat{X})\le P_e\ln (m-1)$.

Combining steps 1.2, 2.1, and 2.2 gives $H(X\mathrm{\mid }\widehat{X})\le h_2(P_e)+P_e\ln (m-1)$; step 1.1 then gives the stated sharp bound.

Since $D((P_e,1-P_e)\mathrm{\parallel }(1\mathrm{/}2,1\mathrm{/}2))=\ln 2-h_2(P_e)\ge 0$ by [F3], $h_2(P_e)\le \ln 2$. Also $m-1\le m$ and [F4] makes $\ln (m-1)\le \ln m$, so step 3.1 implies the weaker bound. If $P_e=0$ or $1$, zero-probability conditional branches above are omitted and $h_2(P_e)=0$ by convention.