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. – enthdegree 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

A sufficient condition for $\{P_1,\dots, P_{M_n}\}\subset \operatorname{Hull}\{P_{Y^n|X^n=x^n}| x^n\in \mathcal{X}^n\}$ to be a working codebook is that it has some $c>0$ where taking $Y_m\sim P_m$ for each $m$, then for any $\ell\!\neq\! m$ we have: $$\mathbb{P}(P_m(Y_m) \leq c\cdot P_{\ell}(Y_m))=\mathcal{o}(1/M_n).$$
Then the following will be a working decoder: "Decide $m$ was sent if $\mathbb{P}(P_m(Y_m)>c\cdot P_{\ell}(Y_m))$ for each $\ell\neq m$." For $c=1$ this is just a maximum likelihood decoder.