Achievability: Joint Typicality Decoding and Successive Cancellation

Fix a product distribution $p(x_1)p(x_2)$. Generate codebooks independently:

• For user 1: generate $2^{nR_{1}}$ codewords $x_1^n(w_1)$, each i.i.d. according to $\prod_{i=1}^n p(x_{1,i})$.
• For user 2: generate $2^{nR_{2}}$ codewords $x_2^n(w_2)$, each i.i.d. according to $\prod_{i=1}^n p(x_{2,i})$.

The codebooks are revealed to all parties (encoders and decoder).

Assume $(W_1, W_2) = (1, 1)$ was sent (by symmetry of the random code construction). Define the error events:

• $\mathcal{E}_0$: the sent pair is not jointly typical: $(x_1^n(1), x_2^n(1), y^n) \notin \mathcal{T}_\epsilon^{(n)}$.
• $\mathcal{E}_1$: there exists $w_1 \neq 1$ such that $(x_1^n(w_1), x_2^n(1), y^n) \in \mathcal{T}_\epsilon^{(n)}$ (wrong user 1, correct user 2).
• $\mathcal{E}_2$: there exists $w_2 \neq 1$ such that $(x_1^n(1), x_2^n(w_2), y^n) \in \mathcal{T}_\epsilon^{(n)}$ (correct user 1, wrong user 2).
• $\mathcal{E}_{12}$: there exist $w_1 \neq 1$ and $w_2 \neq 1$ such that $(x_1^n(w_1), x_2^n(w_2), y^n) \in \mathcal{T}_\epsilon^{(n)}$ (both wrong).

The total error probability satisfies $P_e^{(n)} \leq \Pr(\mathcal{E}_0) + \Pr(\mathcal{E}_1) + \Pr(\mathcal{E}_2) + \Pr(\mathcal{E}_{12})$.

$\Pr(\mathcal{E}_0)$: By the joint AEP, this tends to 0 as $n \to \infty$.

$\Pr(\mathcal{E}_1)$: For any $w_1 \neq 1$, the codeword $x_1^n(w_1)$ is generated independently of $(x_2^n(1), y^n)$. By the joint typicality lemma:

$$\Pr\!\big((x_1^n(w_1), x_2^n(1), y^n) \in \mathcal{T}_\epsilon^{(n)}\big) \leq 2^{-n(I(X_1; X_2, Y) - 3\epsilon)}.$$

Since $X_1$ and $X_2$ are independent, $I(X_1; X_2, Y) = I(X_1; Y | X_2)$. By the union bound over $2^{nR_{1}} - 1$ wrong codewords:

$$\Pr(\mathcal{E}_1) \leq 2^{nR_{1}} \cdot 2^{-n(I(X_1; Y|X_2) - 3\epsilon)} = 2^{-n(I(X_1; Y|X_2) - R_{1} - 3\epsilon)},$$

which tends to 0 if $R_{1} < I(X_1; Y | X_2) - 3\epsilon$.

$\Pr(\mathcal{E}_2)$: By symmetry, this tends to 0 if $R_{2} < I(X_2; Y | X_1) - 3\epsilon$.

$\Pr(\mathcal{E}_{12})$: For $w_1 \neq 1$ and $w_2 \neq 1$, both codewords are independent of $y^n$. By the joint typicality lemma:

$$\Pr(\mathcal{E}_{12}) \leq 2^{n(R_{1} + R_{2})} \cdot 2^{-n(I(X_1, X_2; Y) - 3\epsilon)},$$

which tends to 0 if $R_{1} + R_{2} < I(X_1, X_2; Y) - 3\epsilon$.

Since $\epsilon > 0$ is arbitrary, we conclude that for any $(R_{1}, R_{2})$ strictly inside the pentagon, the average error probability $P_e^{(n)} \to 0$. By the random coding argument, there exists at least one deterministic code achieving this performance. The closure of the region gives the MAC capacity region. $\blacksquare$

We verify that the sum rate at the corner point equals $C$. By the chain rule:

$$I(X_1, X_2; Y) = I(X_2; Y) + I(X_1; Y | X_2),$$

where we used the independence of $X_1$ and $X_2$. Therefore:

$$I(X_1; Y|X_2) + I(X_2; Y) = I(X_1, X_2; Y) = C.$$

Similarly, for the other order:

$$I(X_1; Y) + I(X_2; Y|X_1) = I(X_1, X_2; Y) = C.$$

Stage 1 (decode user 2): The effective channel is $p(y | x_2) = \sum_{x_1} p(x_1) p(y|x_1, x_2)$. By the single-user channel coding theorem, any rate $R_{2} < I(X_2; Y)$ is achievable.

Stage 2 (decode user 1, given $X_2^n$): Conditioned on the correctly decoded $x_2^n$, the effective channel for user 1 is $p(y|x_1, x_2)$ with $x_2$ known. By the single-user theorem, any rate $R_{1} < I(X_1; Y | X_2)$ is achievable.

If stage 1 makes an error (decodes $\hat{w}_2 \neq w_2$), then stage 2 will subtract the wrong signal, likely causing an error in user 1's decoding as well. However, since $\Pr(\hat{W}_2 \neq W_2) \to 0$ as $n \to \infty$ when $R_{2} < I(X_2; Y)$, the probability of error propagation also vanishes. Formally, the total error probability is bounded by the sum of the stage 1 and stage 2 error probabilities:

$$P_e^{(n)} \leq \Pr(\hat{W}_2 \neq W_2) + \Pr(\hat{W}_1 \neq W_1 | \hat{W}_2 = W_2) \to 0.$$

$\blacksquare$