$$X \longrightarrow \fbox{$\phantom{\int}P\_{Y|X}\phantom{\int}$}\longrightarrow Y$$


The information capacity of this channel is $C=\max\_{P\_X} I(X;Y)$. Any rate $C-\varepsilon$ can be achieved by fixing a large-enough blocklength $n$ and associating each message $m\in \{1,\dots,2^{n(C-\varepsilon)}\}$ with a codeword $x^n\_m\in \mathcal{X}^n$, each component of $x^n\_m$ i.i.d. $\sim P^\ast\_X$ where $P^\ast\_X$ is the distribution that maximizes $I(X;Y)$. The distributions these codewords produce on the output alphabet $\mathcal{Y}^n$ are probably different enough from one another that any observed output $Y^n$ is only likely to have come from the true input $m$.


You can imagine choosing a codebook 'backwards' by instead building a collection of attainable output distributions: $$\{P\_m\}\_m\subset \{P: P = P\_{Y^n|X^n}P\_{X^n}\text{ for some }P\_{X^n}\text{ over }\mathcal{X}^n\}$$


When $m$ must be sent, input $X^n$ distributed so that the output $Y^n$ is distributed like $P\_m$


What are necessary and sufficient conditions on $\{P\_m\}\_m$ that ensure decoding error probability $\to 0$ as $n$ grows?



Backwards random codebook generation
"Decodable with error probability less than $\varepsilon$" is tautological to "max-a-posteriori decoder $\arg\max\_{\text{message}}P(\text{message}|\text{observation})$ fails with probability less than $\varepsilon$." By the problem's definition no decoder can have error probability less than this one. 


It is useful to notice from the Bayes rule formula that when all codewords are equally likely, the max-a-posteriori decoding is the same as the max likelihood decoding.


