Cover-Leung inner bound for the two-user DM-MAC with feedback

Fix a finite law $P_U{P}_{X_1\mathrm{\mid }U}{P}_{X_2\mathrm{\mid }U}$. Use $b$ blocks of length $n$ and $b-1$ independent message chunks $M_{1j},M_{2j}$, $1\le j<b$, with sizes $\lceil e^{n{R}_1}\rceil ,\lceil e^{n{R}_2}\rceil$; set $M_{10}=M_{1b}=M_{2b}=1$. In each block independently generate clouds $u^n(\mathrm{\ell })\sim P_U^n$ for $\mathrm{\ell }\in [M_2]$, and, conditionally on every cloud, independent satellite words $x_1^n(m_1,\mathrm{\ell })$ and $x_2^n(m_2,\mathrm{\ell })$ with coordinate laws $P_{X_1\mathrm{\mid }U}$ and $P_{X_2\mathrm{\mid }U}$.

In block $j$, sender 2 sends $x_2^n(M_{2j},M_{2,j-1})$. Sender 1 sends $x_1^n(M_{1j},{\tilde{M}}_{2,j-1})$, where it sets ${\tilde{M}}_{20}=1$ and after block $j-1$ estimates $M_{2,j-1}$ from its own $M_{1,j-1}$, its already known previous state, and the feedback output of that block. If $R_2=0$, the $M_2$ chunks are singletons and sender 1 sets ${\tilde{M}}_{2,j-1}=1$ without a test. If $R_2>0$, then $I(X_2;Y\mid X_1,U)>0$; choose $R_2<{\tau }_2<I(X_2;Y\mid X_1,U)$ and test each candidate $m_2$ using ${\mathrm{ı}}_2={\sum }_i\ln \frac{W(Y_i\mid X_{1i},X_{2i})}{P_{Y\mathrm{\mid }{X}_1,U}(Y_i\mid X_{1i},U_i)},$ with a summand defined as $-\mathrm{\infty }$ whenever its numerator is zero. Set ${\tilde{M}}_{2,j-1}$ to the unique candidate with ${\mathrm{ı}}_2>n{\tau }_2$, or to the fixed default $1$ if zero or multiple candidates pass.

The receiver decodes backward. In the last block it knows the dummy current message $M_{2b}=1$ and searches for the preceding state $M_{2,b-1}$; in each earlier block $j$, it knows $M_{2j}$ from the already decoded next block and searches for the unique pair $(M_{1j},M_{2,j-1})$. It uses a single test for each positive-rate error class: the user-1 test is ${\sum }_i\ln \frac{W(Y_i\mid X_{1i},X_{2i})}{P_{Y\mathrm{\mid }{X}_2,U}(Y_i\mid X_{2i},U_i)}>n{\tau }_1,$ and the pair/state test is ${\sum }_i\ln \frac{W(Y_i\mid X_{1i},X_{2i})}{P_Y(Y_i)}>n{\tau }_{\mathrm{\Sigma }}\mathrm{.}$ A test for a zero-rate user is omitted because its message set is a singleton; if both rates are zero, there is only one message pair. A summand with zero numerator is $-\mathrm{\infty }$, and the decoder returns the sole candidate passing all retained tests, or the fixed default $1$ or $(1,1)$ if zero or multiple candidates pass. Choose $R_1<{\tau }_1<I(X_1;Y\mid X_2,U)$ when $R_1>0$ and $R_1+R_2<{\tau }_{\mathrm{\Sigma }}<I(X_1,X_2;Y)$ when $R_1+R_2>0$. The latter is the mean of the second test because $Y$ is conditionally independent of $U$ given $(X_1,X_2)$.

For fixed $b$ and $R_2>0$, the true ${\mathrm{ı}}_2\mathrm{/}n$ in each data block converges in probability to $I(X_2;Y\mid X_1,U)$ by the weak law for IID finite-valued information-density terms. A wrong $X_2$ satellite is independent of the output conditional on the known $(U,X_1)$, and its likelihood ratio in step 2.1 has expectation one. Markov's inequality and the union bound over $e^{n{R}_2+o(n)}$ candidates show sender 1 decodes each $M_{2j}$ correctly with probability tending to one. If $R_2=0$, there is no sender-decoding error because every $M_2$ chunk is fixed.

For the true tuple, each retained receiver information density converges in probability to its mean. When $R_1>0$, a wrong satellite with the true cloud has likelihood-ratio expectation one under the conditional product law and is bounded by $e^{-n{\tau }_1}$; there are at most $e^{n{R}_1+o(n)}$ such candidates. When $R_1+R_2>0$, a candidate with a wrong preceding state changes the cloud and both satellite codebook groups; each candidate is independent of the output and has product law $P_U{P}_{X_1\mathrm{\mid }U}{P}_{X_2\mathrm{\mid }U}$, so the second likelihood ratio has expectation one and threshold probability at most $e^{-n{\tau }_{\mathrm{\Sigma }}}$. There are at most $e^{n(R_1+R_2)+o(n)}$ such candidates. The strict gaps make all extant error classes vanish; absent zero-rate candidate classes require no test. In the terminal dummy block, the preceding state has $e^{n{R}_2+o(n)}$ candidates when $R_2>0$, and is fixed when $R_2=0$.

With $b$ fixed, the finitely many sender-decoding and receiver backward-decoding errors vanish as $n\to \mathrm{\infty }$ by steps 3.1 and 3.2; blockwise dependence causes no issue because a union bound is used and a correct prior decode makes the next encoder state correct. The random codebook ensemble is finite, so one deterministic codebook has no greater average error than its ensemble mean. The achieved rates are $(b-1)R_j\mathrm{/}b$.

Letting $b\to \mathrm{\infty }$ after the blocklength limit makes $(b-1)R_j\mathrm{/}b\to R_j$. A diagonal sequence of blocklengths gives vanishing error and rates tending to each strict pair; a zero-rate coordinate uses a singleton message and omits its tests. For each fixed law, scaling the positive coordinates of a point in $\mathcal{R}(P)$ by $1-\epsilon$ gives strict gaps for every nonempty error class, and the origin is achieved with one message pair. Letting $\epsilon \downarrow 0$ and taking the union over laws proves the stated closed inner bound. Only sender 1's causal estimate from the shared output is used, which is permitted by [F1].