Finite DMC resolvability by random codebooks

Write $Q_C$ for the mixture in the Statement. Any $z^n$ with $Q_C(z^n)>0$ has $P_Z^n(z^n)>0$, since each sampled codeword has letters in $\mathrm{supp}{P}_U$ and any output reachable from such a letter has positive $P_Z$ mass. Hence all divergences below are well-defined and finite.

For the total-variation bound, let $L_{\mathrm{\ell }}(z^n):=W^n(z^n\mid U^n(\mathrm{\ell }))\mathrm{/}{P}_Z^n(z^n)$ on the support, let $L_C=L_n^{-1}{\sum }_{\mathrm{\ell }}{L}_{\mathrm{\ell }}$, set $T=e^{n(I+\gamma )}$, and truncate to ${\tilde{L}}_{\mathrm{\ell }}=L_{\mathrm{\ell }}\mathbf{1}\{L_{\mathrm{\ell }}\le T\}$ and ${\tilde{L}}_C=L_n^{-1}{\sum }_{\mathrm{\ell }}{\tilde{L}}_{\mathrm{\ell }}$. If ${\alpha }_n:=\mathrm{Pr}[S_n>n(I+\gamma )]$, then the expected removed mass ${\sum }_{z^n}{P}_Z^n(z^n){\mathbb{E}}_C[L_C-{\tilde{L}}_C]$ is exactly ${\alpha }_n$, and the missing mass ${\sum }_{z^n}{P}_Z^n(z^n)(1-{\mathbb{E}}_C{\tilde{L}}_C)$ is also ${\alpha }_n$, because ${\sum }_{z^n}{P}_Z^n(z^n){\mathbb{E}}_C{L}_C=1$. Since $L_C\ge {\tilde{L}}_C$ and ${\mathbb{E}}_C{\tilde{L}}_C\le 1$, the triangle inequality gives $2\mathrm{TV}(Q_C,P_Z^n)\le {\sum }_{z^n}{P}_Z^n(z^n)((L_C-{\tilde{L}}_C)+\mathrm{\mid }{\tilde{L}}_C-{\mathbb{E}}_C{\tilde{L}}_C\mathrm{\mid }+(1-{\mathbb{E}}_C{\tilde{L}}_C))\mathrm{.}$ After expectation, the first and third terms together contribute ${\alpha }_n$ to total variation (the factor $1\mathrm{/}2$ in its definition is included).

For fixed $C$, expand $D(Q_C\mathrm{\parallel }{P}_Z^n)$ as an expectation over a uniform index $J$ and then $Z^n\sim W^n(\cdot \mid U^n(J))$. Averaging over codebooks and using symmetry lets us take $J=1$. The divergence and all rates use natural-log nats by [F6]. Conditional on $U^n(1),Z^n$, the remaining codewords are independent and ${\mathbb{E}}_{U^n(2),\dots ,U^n(L_n)}\left[\frac{Q_C(Z^n)}{P_Z^n(Z^n)}\right]=\frac{e^{S_n}+L_n-1}{L_n}\mathrm{.}$ For any finite positive random variable $A$ with law $p$ and mean $a$, the vector $q_i=p_i{A}_i\mathrm{/}a$ is a probability vector; [F4] gives $0\le D(p\mathrm{\parallel }q)=\ln a-\mathbb{E}[\ln A]$. Thus $\mathbb{E}\ln A\le \ln \mathbb{E}A$. Applying this finite Jensen inequality to the displayed likelihood ratio gives ${\mathbb{E}}_{C}D(Q_C\mathrm{\parallel }{P}_Z^n)\le \mathbb{E}\ln (1+e^{S_n}\mathrm{/}{L}_n)\mathrm{.}$

On $S_n\le n(I+\gamma )$, $L_n\ge e^{n{R}_0}$ and [F8] bound the logarithm by $e^{-n(R_0-I-\gamma )}$. On the complement, $S_n\le nB$ by the definition of $B$, so $\ln (1+e^{S_n}\mathrm{/}{L}_n)\le \ln 2+nB$. The complement has probability at most ${\rho }^n$ by [F5]. Splitting the expectation in step 2.1 across these two events proves the KL bound.

For fixed $z^n$, let $A={\tilde{L}}_C(z^n)-{\mathbb{E}}_C{\tilde{L}}_C(z^n)$. The finite inequality $\mathbb{E}\mathrm{\mid }A\mathrm{\mid }\le \sqrt{\mathbb{E}{A}^2}$ follows by expanding $0\le \mathbb{E}(\mathrm{\mid }A\mathrm{\mid }-\mathbb{E}\mathrm{\mid }A\mathrm{\mid }{)}^2$. Independence of the $L_n$ codewords makes the cross terms vanish, so $\mathbb{E}{A}^2=\frac{1}{L_n}({\mathbb{E}}_U[{\tilde{L}}_1(z^n{)}^2]-({\mathbb{E}}_U{\tilde{L}}_1(z^n){)}^2)\le \frac{{\mathbb{E}}_U[{\tilde{L}}_1(z^n{)}^2]}{L_n}\mathrm{.}$ Since $0\le {\tilde{L}}_1\le T$ and ${\mathbb{E}}_U{L}_1(z^n)={\sum }_{u^n}{P}_U^n(u^n)\frac{W^n(z^n\mid u^n)}{P_Z^n(z^n)}=1,$ the numerator is at most $T$. Finite Cauchy–Schwarz with weights $P_Z^n(z^n)$ then gives ${\sum }_{z^n}{P}_Z^n(z^n){\mathbb{E}}_C\mathrm{\mid }A\mathrm{\mid }\le {\sum }_{z^n}{P}_Z^n(z^n)\sqrt{{\mathbb{E}}_C{A}^2}\le {({\sum }_{z^n}{P}_Z^n(z^n))}^{1\mathrm{/}2}{({\sum }_{z^n}{P}_Z^n(z^n){\mathbb{E}}_C{A}^2)}^{1\mathrm{/}2}\le \sqrt{T\mathrm{/}{L}_n},$ where the middle inequality is finite Cauchy–Schwarz and ${\sum }_{z^n}{P}_Z^n(z^n)=1$. Together with step 1.2, this fluctuation contributes at most $\frac{1}{2}\sqrt{T\mathrm{/}{L}_n}$ to expected total variation. Using [F5], ${\alpha }_n\le {\rho }^n$, and $L_n\ge e^{n{R}_0}$ gives the stated bound.