# Backwards random codebook generation

$$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?

• interesting problem I think.. what is the underlying motivation? – user94040 Dec 20 '16 at 2:26
• It came up when trying to find the information capacity of a situation where one transmitter is broadcasting to a collection of receivers that can't see each other's receptions directly, but can only conference a certain amount of information to all the others. – Christian Chapman Dec 20 '16 at 21:13
• I think standard the word you want for searching the information theory literature is "broadcast" a certain amount of information to all the others. The issue with the question's wording is that it omits motivating and background information meaning one doesn't know the full context. Other key phrases would be multiuser information theory or network information theory. – kodlu Dec 21 '16 at 4:34
• While I am not an expert in this area, the book by Csizsar and Korner, namely "Information Theory:Discrete Memoryless Channels", 2nd Edition, Cambridge, is a good place to start. In particular, there is a taxonomy of network problems in the beginning of Part III, Multi-terminal systems. – kodlu Dec 21 '16 at 4:39

"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.