Finite-DMC dependence-testing achievability bound

Draw codewords $X^n(1),\dots ,X^n(M)$ independently from $P_{X^n}$. Put $Q=P_{X^n}{W}^n$ and $\tau =\ln ((M-1)\mathrm{/}2)$. For decoder tests extend $\mathrm{ı}(x^n;y^n)$ to $-\mathrm{\infty }$ whenever $P_{X^n}(x^n)W^n(y^n\mid x^n)=0$; on its positive support $Q(y^n)>0$, so the stated logarithm is finite. The decoder selects the lowest index $j$ for which $\mathrm{ı}(X^n(j);y^n)>\tau$; if no index passes, it outputs message $1$. This defines a deterministic code decoder for each realized codebook.

If message $j$ is sent, an error can occur only if its own test fails or an earlier codeword passes. Thus its conditional error is at most $\mathrm{Pr}[\mathrm{ı}(X^n(j);Y^n)\le \tau \mid X^n(j)]+{\sum }_{k<j}\mathrm{Pr}[\mathrm{ı}(X^n(k);Y^n)>\tau \mid X^n(j)]\mathrm{.}$ The first probability averaged over the true codeword and output is ${\mathrm{Pr}}_{P_{X^n}{W}^n}[\mathrm{ı}\le \tau ]$. Each earlier independent codeword and the true output have law $P_{X^n}\otimes Q$, so its averaged term is ${\mathrm{Pr}}_{P_{X^n}\otimes Q}[\mathrm{ı}>\tau ]$.

Averaging over the uniform message index gives ensemble-average error at most ${\mathrm{Pr}}_{P_{X^n}{W}^n}[\mathrm{ı}\le \tau ]+\frac{M-1}{2}{\mathrm{Pr}}_{P_{X^n}\otimes Q}[\mathrm{ı}>\tau ],$ because $M^{-1}{\sum }_{j=1}^M(j-1)=(M-1)\mathrm{/}2$. On the event $\mathrm{ı}>\tau$, the likelihood ratio identity gives ${\mathrm{Pr}}_{P\otimes Q}[\mathrm{ı}>\tau ]={\mathbb{E}}_{PW}[e^{-\mathrm{ı}}{\mathbf{1}}_{\{\mathrm{ı}>\tau \}}]$. Therefore this bound equals ${\mathbb{E}}_{PW}[e^{-(\mathrm{ı}-\tau {)}_{+}}]$.

The finite random codebook ensemble has some realization whose average error is no larger than its expectation; otherwise every realization would exceed the ensemble average. With $\tau =\ln ((M-1)\mathrm{/}2)$, this realization proves the stated bound. A one-message code has no decoding error.