Independent-private-message DM-MAC capacity region

Fix a finite law $P_Q{P}_{X_1\mathrm{\mid }Q}{P}_{X_2\mathrm{\mid }Q}$ and a nonnegative rate pair satisfying each subset information bound strictly whenever that subset has positive total rate. Use a singleton message set for every zero-rate user. Choose a deterministic sequence $q^n$ whose empirical distribution tends to $P_Q$. Independently for each user and message, generate input coordinates with law $P_{X_j\mathrm{\mid }Q=q_i}$. The two codebooks are independent.

For a converse code and nonempty $S$, Fano [F6] applied to the decoded subtuple, with the complementary messages supplied as side information, gives $nR(S)\le I(M_S;Y^n\mid M_{S^c})+\ln 2+P_{e}nR(S)\mathrm{.}$ The subtuple error is at most the joint error.

For each nonempty $S\subseteq \{1,2\}$ define $i_S(x_1^n,x_2^n;y^n)={\sum }_i\ln \frac{W(y_i\mid x_{1i},x_{2i})}{P_{Y\mid X_{S^c},Q}(y_i\mid x_{S^c,i},q_i)},$ where the denominator averages over the product input laws for users in $S$ and a summand is $-\mathrm{\infty }$ whenever its numerator is zero. For each subset with $R(S)>0$, choose a threshold $n{\tau }_S$ with $R(S)<{\tau }_S<I(X_S;Y\mid X_{S^c},Q)$. Decode the unique pair passing all these tests; a subset of zero total rate has no wrong-message candidates and its test is omitted; if no pair or more than one pair passes all the retained tests, output the fixed default pair $(1,1)$.

By the chain rule [F5] and the memoryless law [F2], for $S=\{1\}$, $I(M_1;Y_i\mid Y^{i-1},M_2)=H(Y_i\mid Y^{i-1},M_2)-H(Y_i\mid X_{1i},X_{2i})\le H(Y_i\mid X_{2i})-H(Y_i\mid X_{1i},X_{2i})=I(X_{1i};Y_i\mid X_{2i})\mathrm{.}$ The inequality holds because $X_{2i}$ is determined by $M_2$, so conditioning on $Y^{i-1}$ cannot increase the first entropy. Interchanging users proves the other individual bound. For $S=\{1,2\}$, $H(Y_i\mid Y^{i-1})\le H(Y_i)$ and the same channel-law identity give $I(M_1,M_2;Y_i\mid Y^{i-1})\le I(X_{1i},X_{2i};Y_i)$.

For the true pair and every tested subset, the information-density summands are independent across coordinates, uniformly bounded on their finite positive supports, and their mean average tends to $I(X_S;Y\mid X_{S^c},Q)$. Their sum variance is $O(n)$, so Chebyshev's inequality makes all tested true tests pass with probability tending to one.

Fix a wrong-message set $S$ and condition on the true complementary codewords and output. The candidate codewords indexed by $S$ are independent of the output with the product input law used in the denominator of $i_S$; hence the likelihood ratio $e^{i_S}$ has conditional expectation one. Markov's inequality bounds a false threshold pass by $e^{-n{\tau }_S}$. There are at most $e^{nR(S)+o(n)}$ candidates of this error type, so ${\tau }_S>R(S)$ makes the union of the three error classes vanish. The ensemble-average error tends to zero, and a deterministic codebook with error no larger than that average exists. A wrong-message set necessarily has positive total rate, since the zero-rate message sets are singletons. If both rates are zero, the unique message pair is always returned with zero error. Scaling any nonnegative pair in the displayed closed region by $1-\epsilon$, with $0<\epsilon <1$, makes every positive-total-rate subset inequality strict; letting $\epsilon$ decrease to zero therefore gives all closed faces, including cases where a zero-rate subset has zero information.

Let $Q$ be uniform on $\{1,\dots ,n\}$, independent of the messages, and set $(X_1,X_2,Y)=(X_{1Q},X_{2Q},Y_Q)$. Since each input is a function of its own independent message, $P_{X_1{X}_2\mathrm{\mid }Q}=P_{X_1\mathrm{\mid }Q}{P}_{X_2\mathrm{\mid }Q}$. Averaging step 2.2 over $i$ gives the three stated conditional mutual-information bounds with this finite $Q$. Because $Y$ has a finite alphabet, $I(M_S;Y^n\mid M_{S^c})\le n\ln \mathrm{\mid }\mathcal{Y}\mathrm{\mid }$; step 1.2 then bounds each rate for $P_e<1\mathrm{/}2$, so its normalized Fano remainder vanishes along a reliable sequence. Divide step 1.2 by $n$, let $P_e\to 0$, then take closure.