Lossy separation for finite IID sources and finite DMCs

Suppose $R(D)=0$. By [F1] choose a minimizing test channel; its mutual information is zero in bits and hence in nats by [F9]. By [F8], source and reproduction under that test channel are independent. If $q(\widehat{s})$ is its reproduction marginal, then ${\sum }_{\widehat{s}}q(\widehat{s})\mathbb{E}d(S,\widehat{s})\le D$. This finite weighted average implies some ${\widehat{s}}_0$ has $\mathbb{E}d(S,{\widehat{s}}_0)\le D$. Use one message, a fixed channel input word, and the constant reproduction ${\widehat{s}}_0^k$. Its expected distortion is at most $D$. For each $\epsilon >0$, the IID bounded variables $Z_i=d(S_i,{\widehat{s}}_0)$ have mean at most $D$, finite variance, and variance of their average equal to $\mathrm{Var}(Z_1)\mathrm{/}k$; the pointwise bound ${\mathbf{1}}_{\{\mathrm{\mid }\bar{Z}-\mathbb{E}{Z}_1\mathrm{\mid }\ge \epsilon \}}\le (\bar{Z}-\mathbb{E}{Z}_1{)}^2\mathrm{/}{\epsilon }^2$ gives $\mathrm{Pr}[k^{-1}{\sum }_i{Z}_i>D+\epsilon ]\le \mathrm{Var}(Z_1)\mathrm{/}(k{\epsilon }^2)\to 0$.

Now assume $R(D)>0$ and $r(D)<\rho C(W)$. Choose $R_c$ with $r(D)\mathrm{/}\rho <R_c<C(W)$, then choose $\eta >0$ so that $(\ln 2)(R(D)+\eta )\mathrm{/}\rho <R_c$. For either chosen source performance criterion, [F2] gives deterministic source codes with message counts $M_k$, that criterion, and ${\mathrm{lim\hspace{0.17em}sup}}_k{k}^{-1}{\log }_2{M}_k\le R(D)+\eta$. Therefore ${\mathrm{lim\hspace{0.17em}sup}}_k{n}_k^{-1}\ln M_k\le (\ln 2)(R(D)+\eta )\mathrm{/}\rho <R_c$.

For any joint code, [F7] gives $I(S^k;{\widehat{S}}^k)\le I(S^k;Y^{n_k})$. Given $S^k=s^k$, the DMC output has law $W^{n_k}(\cdot \mid f_k(s^k))$; averaging conditional entropies over source words and grouping them by $X^{n_k}=f_k(S^k)$ gives $H(Y^{n_k}\mid S^k)=H(Y^{n_k}\mid X^{n_k})$. Therefore [F10] yields $I(S^k;Y^{n_k})=I(X^{n_k};Y^{n_k})$, and [F6] bounds this by $n_{k}C(W)$. The rate-distortion bound [F4] at the actual expected distortion $D_k=\mathbb{E}{d}_k$ then gives $r(D_k)\le (n_k\mathrm{/}k)C(W)$.

Since $R_c<C(W)$, [F3] and the supremum definition of maximal-error capacity give a maximal-error achievable rate strictly greater than $R_c$. Its channel code sequence has enough messages to include $M_k$ for all sufficiently large $n_k$; restrict to those messages, mapping discarded decoder outputs to a retained message. Correct-decoding regions for retained messages are preserved, so maximal error does not increase. The source-code index may be nonuniform, but its channel error is the weighted average of per-message errors and is bounded by the maximal error.

If the expected-distortion criterion holds, then for every $\epsilon >0$, eventually $D_k\le D+\epsilon$. Monotonicity in [F5] and step 1.3 imply $r(D+\epsilon )\le (n_k\mathrm{/}k)C(W)$; taking $k\to \mathrm{\infty }$, then $\epsilon \downarrow 0$, and using right-continuity in [F5] yields $r(D)\le \rho C(W)$.

Compose the source and channel codes. On channel success the reproduction equals the source-code reproduction, while on channel error the normalized distortion is at most $d_{\max }$. Hence expected distortion is at most the source-code expected distortion plus $d_{\max }$ times the maximal channel error, so its limsup is at most $D$. For the excess criterion, for every $\epsilon >0$, the event $\{d_k^{\mathrm{j}\mathrm{o}\mathrm{i}\mathrm{n}\mathrm{t}}>D+\epsilon \}$ is contained in the union of the source excess event $\{d_k^{\mathrm{s}\mathrm{o}\mathrm{u}\mathrm{r}\mathrm{c}\mathrm{e}}>D+\epsilon \}$ and the channel error event. Both probabilities tend to zero.

If the positive-slack excess criterion holds, fix $\epsilon >0$. Splitting expected distortion at $D+\epsilon \mathrm{/}2$, boundedness gives $D_k\le D+\epsilon \mathrm{/}2+d_{\max }\mathrm{Pr}[d_k>D+\epsilon \mathrm{/}2]$, which is at most $D+\epsilon$ for all sufficiently large $k$. Step 2.2's monotonicity, information bound, and right-continuity argument therefore also gives $r(D)\le \rho C(W)$.

The zero-rate construction in step 1.1, the strict-rate construction in steps 1.2, 2.1 and 3.1, and the two converse cases in steps 2.2 and 3.2 prove the stated conclusions; no positive-rate equality case is used.