Cover-El Gamal-Salehi sufficient condition for correlated sources over a DM-MAC

Fix a law and a rate-independent public schedule $q^n$ whose empirical distribution tends to $P_Q$; choose symbol counts by rounding $n{P}_Q(q)$ and distributing the bounded remainder. For every $s_1^n$, independently draw a codeword with law ${\prod }_i{P}_{X_1\mathrm{\mid }{S}_1,Q}(\cdot \mid s_{1i},q_i)$, and for every $s_2^n$ independently draw a codeword with law ${\prod }_i{P}_{X_2\mathrm{\mid }{S}_2,Q}(\cdot \mid s_{2i},q_i)$. The two codebooks and all their indexed entries are independent.

Encoder $j$ observing $s_j^n$ sends the codeword indexed by that exact source sequence. Fix one default pair of source blocks from the nonempty finite source alphabets. The decoder returns the unique pair $({\widehat{s}}_1^n,{\widehat{s}}_2^n)$ for which $(q^n,{\widehat{s}}_1^n,{\widehat{s}}_2^n,x_1^n({\widehat{s}}_1^n),x_2^n({\widehat{s}}_2^n),y^n)$ is jointly strongly typical for the displayed law when exactly one pair passes; if zero or multiple pairs pass, it returns the fixed default pair. These maps have the interfaces in [F1] and the output law in [F2].

Conditional on $q^n$, the random tuples $(S_{1i},S_{2i},X_{1i}(S_1^n),X_{2i}(S_2^n),Y_i)$ are independent across $i$ in the codebook ensemble. For each fixed joint letter, the empirical frequency has variance at most $1\mathrm{/}(4n)$ and mean equal to the $q^n$-type average of its conditional probability. That mean tends to the target probability because the type of $q^n$ tends to $P_Q$. Chebyshev's inequality and a union bound over the finite alphabet show that the true tuple is support-restricted jointly typical with probability tending to one; target-zero letters never occur because every source, encoder and channel kernel is used only on its support.

On the event that the true tuple is typical, a decoding error can occur only if some wrong candidate differs in source 1 alone, source 2 alone, or both. The strict hypotheses are finite conditional-entropy and mutual-information inequalities by [F4]–[F7]; they let us choose the typicality tolerance so that each exponent in [F3] is positive. Therefore the conditional expected number of wrong typical candidates tends to zero; Markov's inequality makes the probability of any such candidate tend to zero. Combining with step 2.2 proves that the ensemble-average source-block error tends to zero.

At each $n$ the alphabets and source-indexed codebooks are finite, so the random ensemble has finite support. At least one deterministic codebook realization has error no larger than the ensemble mean. Fixing such realizations along increasing blocklengths gives the deterministic reliable codes required by [F1]. Taking the closure of the strict region completes the sufficient-condition proof; no converse or necessity claim is made.