Finite-DMC information deficit controls squared distance to the CAID set

Fix a CAID and let $Q^{\ast }$ be its output. For every input law $P$, expanding the finite sums using [F2]–[F3] gives $C-I(P,W)={\sum }_{x}P(x)(C-d_x)+D(PW\mathrm{\parallel }{Q}^{\ast })\mathrm{.}$ Indeed, ${\sum }_{x}P(x)d_x-I(P,W)={\sum }_y(PW)(y)\ln [(PW)(y)\mathrm{/}{Q}^{\ast }(y)]$.

Put $E=\{x:d_x=C\}$. By [F2] and [F4], the right side of step 1.1 vanishes exactly when $P(x)=0$ for $x\mathrm{\notin }E$ and $PW=Q^{\ast }$. Thus $\mathrm{\Pi }=\{P\in {\mathrm{\Delta }}_{\mathcal{X}}:P{\mathrm{\mid }}_{E^c}=0,PW=Q^{\ast }\}$, a nonempty affine slice of the input simplex.

If $E^c\mathrm{\ne }\mathrm{\varnothing }$, let $\eta ={\min }_{x\mathrm{\notin }E}(C-d_x)>0$. The first term in step 1.1 is at least $\eta \mathrm{\parallel }P{\mathrm{\mid }}_{E^c}{\mathrm{\parallel }}_2^2$, since $P(x)\in [0,1]$ and ${\sum }_{E^c}P(x)\ge \mathrm{\parallel }P{\mathrm{\mid }}_{E^c}{\mathrm{\parallel }}_2\ge \mathrm{\parallel }P{\mathrm{\mid }}_{E^c}{\mathrm{\parallel }}_2^2$. By [F5], the second term is at least $\frac{1}{2}\mathrm{\parallel }PW-Q^{\ast }{\mathrm{\parallel }}_2^2$. Hence the gap is at least $a$ times the squared norm of the concatenated residual $(P{\mathrm{\mid }}_{E^c},PW-Q^{\ast })$, with $a=\min (\eta ,1\mathrm{/}2)$. If $E^c=\mathrm{\varnothing }$, omit that block and take $a=1\mathrm{/}2$.

Apply [F6] to the slice in step 2.1 with linear map $P\mapsto (P{\mathrm{\mid }}_{E^c},PW)$ and target $(0,Q^{\ast })$, omitting the first component when $E^c=\mathrm{\varnothing }$. For its finite constant $H$, step 2.2 gives $C-I(P,W)\ge a{H}^{-2}{\mathrm{dist}}_2(P,\mathrm{\Pi }{)}^2$. If $\mathrm{\Pi }$ is the whole simplex, the distance is identically zero and any positive $\alpha$ works; otherwise take $\alpha =a{H}^{-2}>0$.