Random coding achieves every rate below finite DMC capacity

If $R=0$, one message gives zero error. Otherwise choose $\delta :=(C(W)-R)\mathrm{/}3>0$ and $M_n:=\lfloor e^{nR}\rfloor$. Then $\ln M_n\mathrm{/}n\to R$, so for all sufficiently large $n$, $(\ln M_n+n\delta )\mathrm{/}n<C(W)-\delta$. By [F3], the probability that the transmitted IID pair fails the threshold ${\mathrm{ı}}_{P_X^{\ast }}(X^n;Y^n)>\ln M_n+n\delta$ tends to zero.

Draw $M_n$ codewords independently from $P_X^{\ast n}$. Decode to the unique codeword with information density greater than $\ln M_n+n\delta$, using a fixed default output if there is not exactly one. Conditional on the transmitted message, an error is contained in the union of the true-codeword miss event from step 1.1 and the event that some independent competing word passes the threshold. For one competitor $X^{\mathrm{\prime }n}\sim P_X^{\ast n}$ independent of $Y^n\sim Q_{P_X^{\ast }}^n$, [F2] gives $\mathbb{E}{e}^{{\mathrm{ı}}_{P_X^{\ast }}(X^{\mathrm{\prime }n};Y^n)}={\sum }_{x^n}{P}_X^{\ast n}(x^n){\sum }_{y^n:Q_{P_X^{\ast }}^n(y^n)>0}{W}^n(y^n\mid x^n)=1$ by [F4], since every output reachable from a positive-probability input has positive $Q_{P_X^{\ast }}$ mass. On a false pass, the nonnegative variable $Z=e^{{\mathrm{ı}}_{P_X^{\ast }}(X^{\mathrm{\prime }n};Y^n)}$ exceeds $e^{\ln M_n+n\delta }$, so $1=\mathbb{E}Z\ge e^{\ln M_n+n\delta }\mathrm{Pr}[Z>e^{\ln M_n+n\delta }]$, and the false-pass probability is at most $e^{-\ln M_n-n\delta }$. A union bound over at most $M_n-1$ competitors makes this term at most $e^{-n\delta }$.

The ensemble-averaged average error is at most the miss probability plus $e^{-n\delta }$, so it tends to zero by step 1.1 and step 2.1. The ensemble has finite support; therefore at each $n$ some deterministic codebook has average error no greater than the ensemble mean. Its rate tends to $R$, proving the claim.