Globally optimized constant-composition and Gallager functions agree

Put $\alpha =(1+\rho {)}^{-1}\in (0,1)$ and, for an output law $Q$, set $Z_x(Q)={\sum }_{y}W(y\mid x{)}^{\alpha }Q(y{)}^{1-\alpha }$. If $Z_x(Q)>0$, define $R_x(y)=W(y\mid x{)}^{\alpha }Q(y{)}^{1-\alpha }\mathrm{/}{Z}_x(Q)$. Expanding the finite sums gives for every $V_x\ll W_x$ with finite $D(V_x\mathrm{\parallel }Q)$ $D(V_x\mathrm{\parallel }{W}_x)+\rho D(V_x\mathrm{\parallel }Q)=(1+\rho )D(V_x\mathrm{\parallel }{R}_x)-(1+\rho )\ln Z_x(Q)\mathrm{.}$ By [F3], the minimum over $V_x$ is $-(1+\rho )\ln Z_x(Q)=-{\alpha }^{-1}\ln Z_x(Q)$. If $Z_x(Q)=0$, every such objective with positive $P(x)$ is infinite, matching the extended value of this expression.

Define $S_y(P)={\sum }_{x}P(x)W(y\mid x{)}^{\alpha }$ and $\mathrm{\Psi }(P)={\sum }_y{S}_y(P{)}^{1\mathrm{/}\alpha }$. Then [F1] gives $E_0(\rho ,P)=-\ln \mathrm{\Psi }(P)$. Since $1\mathrm{/}\alpha =1+\rho >1$, [F7] shows that each summand $S_y(P{)}^{1\mathrm{/}\alpha }$ is continuous and convex as a function of $P$; hence $\mathrm{\Psi }$ is continuous and convex on the input simplex. The simplex is nonempty because it contains a point mass, closed as the intersection of finitely many coordinate half-spaces with the affine equation ${\sum }_{x}P(x)=1$, and bounded because every coordinate lies in $[0,1]$. By [F4] it is compact, so $\mathrm{\Psi }$ attains a minimum at some $P^{\ast }$. For every input law at least one coordinate of $P$ is positive, and that row of $W$ has a positive entry; hence at least one $S_y(P)>0$ and $\mathrm{\Psi }(P)>0$. Also, for every $r>0$, $t^r\to 0$ as $t\downarrow 0$: given $\epsilon >0$, take $\delta ={\epsilon }^{1\mathrm{/}r}$; if $0<t<\delta$, strict monotonicity of $\ln$ and $\exp$ gives $t^r<\epsilon$. Write $S_y=S_y(P^{\ast })$, ${\mathrm{\Psi }}_{\ast }=\mathrm{\Psi }(P^{\ast })>0$, $T=\{y:S_y>0\}$, and $q^{\ast }(y)=S_y^{1\mathrm{/}\alpha }\mathrm{/}{\mathrm{\Psi }}_{\ast }$ on $T$, with $q^{\ast }(y)=0$ outside $T$.

For any $V$ and output law $Q$, expansion of finite KL gives ${\sum }_{x}P(x)D(V_x\mathrm{\parallel }Q)=I_P(V)+D(P{V}_Y\mathrm{\parallel }Q)\ge I_P(V),$ with equality at $Q=P{V}_Y$ by [F2–F3]. Taking the joint infimum over $V,Q$ and applying step 1.1 row by row therefore yields $E_{0,\mathrm{c}\mathrm{c}}(\rho ,P)={\inf }_Q{\sum }_{x:P(x)>0}P(x)f_x(Q),f_x(Q):=-{\alpha }^{-1}\ln Z_x(Q),$ with $f_x(Q)=+\mathrm{\infty }$ when $Z_x(Q)=0.$ Coordinates with $P(x)=0$ are omitted, so no $0\cdot \mathrm{\infty }$ term is used.

Put $T_x={\sum }_{y}W(y\mid x{)}^{\alpha }{S}_y^{\rho }$. For each $x$, move from $P^{\ast }$ toward the point mass ${\delta }_x$ along $P_t=(1-t)P^{\ast }+t{\delta }_x$, so $S_y(P_t)=S_y+t(W(y\mid x{)}^{\alpha }-S_y)$. If $S_y>0$, [F5]–[F6] give the derivative of $S_y(P_t{)}^{1\mathrm{/}\alpha }$ at $t=0$ as ${\alpha }^{-1}{S}_y^{\rho }(W(y\mid x{)}^{\alpha }-S_y)$. If $S_y=0$, the term equals $t^{1\mathrm{/}\alpha }W(y\mid x)$, whose right derivative at zero is zero because $1\mathrm{/}\alpha -1=\rho >0$ and the endpoint limit in step 1.2 applies. Therefore the right derivative of $\mathrm{\Psi }(P_t)$ at zero is ${\alpha }^{-1}(T_x-{\mathrm{\Psi }}_{\ast })$, using ${\sum }_y{S}_y^{1\mathrm{/}\alpha }={\mathrm{\Psi }}_{\ast }$. The minimum at $t=0$ makes this right derivative nonnegative, so $T_x\ge {\mathrm{\Psi }}_{\ast }$. Also ${\sum }_x{P}^{\ast }(x)T_x={\sum }_y{S}_y^{1+\rho }={\mathrm{\Psi }}_{\ast }$. Since every $T_x\ge {\mathrm{\Psi }}_{\ast }$ and this weighted average equals ${\mathrm{\Psi }}_{\ast }$, equality holds whenever $P^{\ast }(x)>0$. Substitution into $Z_x(q^{\ast })={\mathrm{\Psi }}_{\ast }^{-(1-\alpha )}{T}_x$ gives $Z_x(q^{\ast })\ge {\mathrm{\Psi }}_{\ast }^{\alpha }$, with equality for every active input. Thus $f_x(q^{\ast })\le -\ln {\mathrm{\Psi }}_{\ast }$ for all $x$, with equality on $\mathrm{supp}{P}^{\ast }$.

Applying step 2.1 with the particular output law $q^{\ast }$ gives, for every $P$, $E_{0,\mathrm{c}\mathrm{c}}(\rho ,P)\le {\sum }_{x}P(x)f_x(q^{\ast })\le -\ln {\mathrm{\Psi }}_{\ast }={\max }_{P^{\mathrm{\prime }}}{E}_0(\rho ,P^{\mathrm{\prime }})\mathrm{.}$ Therefore ${\max }_P{E}_{0,\mathrm{c}\mathrm{c}}(\rho ,P)\le {\max }_P{E}_0(\rho ,P)$.

On $[0,\mathrm{\infty })$, the power $t^{1-\alpha }$ is continuous by the endpoint estimate in step 1.2 and concave: on $(0,\mathrm{\infty })$ the second derivative of $-t^{1-\alpha }$ is $(1-\alpha )\alpha t^{-1-\alpha }>0$, so [F5], [F6], and [F8] make $-t^{1-\alpha }$ convex there; continuity extends the concavity inequality to zero. Thus each $Z_x(Q)$ is concave. The function $-\ln z$ is decreasing and convex on $(0,\mathrm{\infty })$, since $\ln$ is increasing by [F9] and $(-\ln z{)}^{\mathrm{\prime }\mathrm{\prime }}=z^{-2}>0$ by [F5], [F6], [F8], and [F10]. Consequently $f_x(Q)=-{\alpha }^{-1}\ln Z_x(Q)$ is convex wherever $Z_x(Q)>0$: concavity of $Z_x$, monotonicity of $-\ln$, and convexity of $-\ln$ give the convex-combination inequality directly. Hence $F(Q)={\sum }_{x:P^{\ast }(x)>0}{P}^{\ast }(x)f_x(Q)$ is convex on its finite domain. For $y\in T$, differentiating at the positive point $q^{\ast }$ and using $Z_x(q^{\ast })={\mathrm{\Psi }}_{\ast }^{\alpha }$ for active $x$ from step 2.2 gives $\frac{\mathrm{\partial }F}{\mathrm{\partial }Q(y)}(q^{\ast })=-\frac{1-\alpha }{\alpha }\frac{{\mathrm{\Psi }}_{\ast }^{\alpha }}{S_y}\frac{{\sum }_{x:P^{\ast }(x)>0}{P}^{\ast }(x)W(y\mid x{)}^{\alpha }}{{\mathrm{\Psi }}_{\ast }^{\alpha }}=-\rho \mathrm{.}$ For any strictly positive probability vector $Q$ on $T$, let $g(t)=F((1-t)q^{\ast }+tQ)$. It is convex, and $g_{+}^{\mathrm{\prime }}(0)={\sum }_{y\in T}(-\rho )(Q(y)-q^{\ast }(y))=0$. Convexity gives $(g(t)-g(0))\mathrm{/}t\le g(1)-g(0)$ for $0<t<1$; letting $t\downarrow 0$ yields $F(Q)\ge F(q^{\ast })$. If $Q$ has zero coordinates on $T$ but $F(Q)<\mathrm{\infty }$, then every active $Z_x(Q)>0$; apply the result to $Q_t=(1-t)Q+t{q}^{\ast }$ and let $t\downarrow 0$, using continuity of the finite sums and logarithms on positive $Z_x(Q)$. If $F(Q)=+\mathrm{\infty }$, the inequality is immediate. Thus $F(Q)\ge F(q^{\ast })$ for every probability vector supported on $T$.

For a general output law $Q$, let $c=Q(T)$. If $c=0$, every active row has $Z_x(Q)=0$ and $F(Q)=+\mathrm{\infty }$. If $c>0$, normalize $Q_T=Q(\cdot \mid T)$. Every active row is supported on $T$, so $Z_x(Q)=c^{1-\alpha }{Z}_x(Q_T)$ and $f_x(Q)=f_x(Q_T)-\rho \ln c\ge f_x(Q_T)$. Step 3.2 then gives $F(Q)\ge F(q^{\ast })$. Since active inputs satisfy $f_x(q^{\ast })=-\ln {\mathrm{\Psi }}_{\ast }$, step 2.1 yields $E_{0,\mathrm{c}\mathrm{c}}(\rho ,P^{\ast })=F(q^{\ast })=-\ln {\mathrm{\Psi }}_{\ast }={\max }_P{E}_0(\rho ,P)$.

Step 4.1 gives ${\max }_P{E}_{0,\mathrm{c}\mathrm{c}}(\rho ,P)\ge E_{0,\mathrm{c}\mathrm{c}}(\rho ,P^{\ast })={\max }_P{E}_0(\rho ,P)$, while step 3.1 gives the reverse inequality. This proves the globally optimized identity and establishes no pointwise-in-$P$ equality.