Exercises

$nR \leq I(W; Y^n) + n\epsilon_n$.

$I(W; Y^n) = \sum_{i=1}^n I(W; Y_i | Y^{i-1}) \leq \sum_{i=1}^n I(W, Y^{i-1}; Y_i) = \sum_{i=1}^n I(X_i; Y_i)$ where the last step uses: (a) $X_i = f_i(W, Y^{i-1})$ is a function of $(W, Y^{i-1})$, and (b) memorylessness $p(y_i | x_i, w, y^{i-1}) = p(y_i | x_i)$, so $I(W, Y^{i-1}; Y_i | X_i) = 0$.

$\sum_i I(X_i; Y_i) \leq n \max_{p(x)} I(X; Y) = nC$. Since direct coding achieves $C$: $C_{\text{fb}} = C$.

With symmetric powers and correlation $\rho$: $R_{1} + R_{2} \leq \frac{1}{2}\log(1 + (P + P + 2\rho P)/N) = \frac{1}{2}\log(1 + 2P(1+\rho))$.

The sum-rate is maximized at $\rho = 1$: $\frac{1}{2}\log(1+4P)$. But at $\rho = 1$, individual rates are zero. For positive individual rates, the Kramer-Gastpar result gives sum-rate $= \frac{1}{2}\log(1+4P)$ achievable with a Schalkwijk-Kailath extension.

No-feedback: $\frac{1}{2}\log(1+2P)$. With feedback: $\frac{1}{2}\log(1+4P)$. For $P = 10$: no-feedback $= \frac{1}{2}\log 21 \approx 2.18$, feedback $= \frac{1}{2}\log 41 \approx 2.68$. Gain: 0.5 bits.

In a degraded BC with $X \to Y_1 \to Y_2$ (user 1 is stronger), user 1's output contains all the information about $X$ that user 2's output has, plus more.

The encoder already knows $X$, which determines $Y_1$ and $Y_2$ (up to noise). Feedback of $Y_1, Y_2$ provides no information beyond what the encoder already knows about the channel state (since the noise is independent of $X$). More formally: the capacity-achieving scheme (superposition coding) does not use feedback, and the converse does not improve with feedback because the degraded structure means $I(W_2; Y_2^n | W_1) \leq I(W_2; Y_1^n | W_1)$, which is already the no-feedback bound.

$Y_1 = X_2 + Z_1$. Notice that $Y_1$ does not depend on $X_1$ at all! User 1's own transmission does not appear in its received signal (additive model with separate channels in each direction).

Since $Y_1 = X_2 + Z_1$ is independent of $X_1$, there is nothing to cancel. The channel from user 2 to user 1 is simply an AWGN channel with capacity $\frac{1}{2}\log(1 + P_2/N)$.

Similarly, $Y_2 = X_1 + Z_2$ gives user 2 a clean AWGN channel. Both directions achieve full point-to-point capacity simultaneously. This is why the Gaussian additive two-way channel decomposes.

For the erasure MAC where $Y = X_1 + X_2$ when not erased (and $?$ when erased): $R_{1} \leq 1 - \epsilon_1$, $R_{2} \leq 1 - \epsilon_2$, $R_{1} + R_{2} \leq 1 - \epsilon_1\epsilon_2$.

With feedback, both encoders learn the erasure pattern. When user 1's symbol is erased but user 2's is received, both encoders know this. User 1 can retransmit its erased symbol while user 2 stays silent, avoiding collision. This scheduling is impossible without feedback because the encoders do not know the erasure pattern.

With perfect scheduling: $R_{k} = 1 - \epsilon_k$ for each user (full individual capacity). The sum-rate becomes $(1-\epsilon_1) + (1-\epsilon_2) = 2 - \epsilon_1 - \epsilon_2 > 1 - \epsilon_1\epsilon_2$ when $\epsilon_1 + \epsilon_2 < 1 + \epsilon_1\epsilon_2$, which holds for all $\epsilon_1, \epsilon_2 \in (0, 1)$.

The Cover-Leung region becomes: $R_{1} \leq I(X_1; Y | X_2)$, $R_{2} \leq I(X_2; Y | X_1)$, $R_{1} + R_{2} \leq I(X_1, X_2; Y)$. With the distributions $p(x_1 | u) = p(x_1)$ and $p(x_2 | u) = p(x_2)$ (independent of $U$).

With $U = \emptyset$, the inputs are independent ($p(x_1, x_2) = p(x_1)p(x_2)$), and the rate constraints are exactly the no-feedback MAC capacity region. The Cover-Leung bound generalizes the standard result by allowing correlated inputs through a non-trivial $U$.

$R_{k} \leq \frac{1}{2}\log(1 + P_k(1-\rho^2)/N)$. Since $1 - \rho^2$ decreases as $|\rho|$ increases (from 1 at $\rho = 0$ to 0 at $|\rho| = 1$), the individual rate constraints become more restrictive with increasing $|\rho|$. At $\rho = \pm 1$: $R_{k} \leq 0$.

$R_{1} + R_{2} \leq \frac{1}{2}\log(1 + (P_1 + P_2 + 2\rho\sqrt{P_1 P_2})/N)$. For $\rho > 0$: $2\rho\sqrt{P_1 P_2} > 0$, so the argument of the log increases. The sum-rate constraint relaxes with increasing $\rho$.

The optimal $\rho$ trades off individual rates (which decrease with $|\rho|$) against sum-rate (which increases with $\rho > 0$). The capacity region is the union over all $\rho \in [-1, 1]$, capturing both extremes.

$R_{1} \leq 1 - 0.2 = 0.8$, $R_{2} \leq 1 - 0.4 = 0.6$. Sum-rate: $R_{1} + R_{2} \leq 1 - 0.2 \times 0.4 = 0.92$.

Bits in set $A$ (user 1 received, user 2 erased): $(1-0.2) \times 0.4 = 0.32$. Bits in set $B$ (user 2 received, user 1 erased): $0.2 \times (1-0.4) = 0.12$. XOR gain: $\min\{0.32, 0.12\} = 0.12$. Sum-rate with feedback: $0.92 + 0.12 = 1.04$.

The XOR trick improves the sum-rate from 0.92 to 1.04 — a 13% gain. The gain is limited by $\min\{|A|, |B|\}$, the smaller of the two "XOR-able" sets.

$\Delta R = \frac{1}{2}\log(1+4P/N) - \frac{1}{2}\log(1+2P/N) = \frac{1}{2}\log\frac{1+4P/N}{1+2P/N}$.

As $P/N \to \infty$: $\DeltaR \to \frac{1}{2}\log\frac{4P/N}{2P/N} = \frac{1}{2}\log 2 = 0.5$ bits. The feedback gain saturates at 0.5 bits — the beamforming gain from coherent combining.

1. Map the message $W$ to a real number $\theta \in [0, 1]$.
2. Round 1: transmit $X_1 = \sqrt{P} \cdot \theta$. Receiver estimates $\hat{\theta}_1 = Y_1/\sqrt{P}$.
3. Round $i$: encoder computes the estimation error $\theta - \hat{\theta}_{i-1}$ (known via feedback) and transmits $X_i = \sqrt{P/\sigma_{i-1}^2} \cdot (\theta - \hat{\theta}_{i-1})$, where $\sigma_{i-1}^2 = \text{Var}(\theta - \hat{\theta}_{i-1})$.
4. Receiver updates: $\hat{\theta}_i = \hat{\theta}_{i-1} + (\sigma_{i-1}^2/P) Y_i$.

After each round, $\sigma_i^2 = \sigma_{i-1}^2 / (1 + P/N) = \sigma_0^2 / (1+P/N)^i$. After $n$ rounds: $\sigma_n^2 = 1 / (1+\text{SNR})^n$. The error probability is $P_e \sim \exp(-c / \sigma_n^2) = \exp(-c(1+\text{SNR})^n) \sim 2^{-2^{n\log(1+\text{SNR})}}$.

Without feedback, the encoder cannot adapt to the specific noise realization. With feedback, the encoder "zooms in" on the receiver's current estimate, transmitting increasingly refined corrections. Each round squares the effective SNR, leading to doubly exponential error decay.

The transmitter sends $X_{\text{retx}} = \alpha_1 E_1 + \alpha_2 E_2$, where $E_k$ is receiver $k$'s estimation error (known to the transmitter via feedback).

From receiver 1's perspective: it wants to decode $E_2$ (to use as side information). The component $\alpha_1 E_1$ is interference — but $E_1$ is known at the transmitter! By DPC (Costa's writing on dirty paper), the transmitter can pre-subtract $\alpha_1 E_1$ without rate loss, so receiver 1 sees an effective channel with only $E_2$ plus noise.

Similarly, receiver 2 gets DPC-cleaned access to $E_1$. Each receiver decodes the other's error and uses it to refine its own message estimate. DPC is essential because without it, the interference from the other user's error would reduce the effective rate.

Let $U \sim \mathcal{N}(0, Q)$ and $X_k = U + V_k$ with $V_k \sim \mathcal{N}(0, P-Q)$ independent of $U$ and each other. Then $\text{Cov}(X_1, X_2) = Q$, so $\rho = Q/P$.

$I(X_1; Y | X_2, U) = I(V_1; V_1 + Z) = \frac{1}{2}\log(1 + (P-Q)/1) = \frac{1}{2}\log(1 + P(1-\rho^2))$ (using $Q = \rho^2 P$ for the correlation structure). Actually: $\text{Var}(V_k) = P - Q$ and $Y | X_2, U = (U + V_1) + (U + V_2) + Z | U, X_2 = V_1 + Z'$ for effective noise $Z'$, giving $I(X_1; Y | X_2, U) = \frac{1}{2}\log(1 + P(1-\rho^2))$.

$I(X_1, X_2; Y | U) = I(V_1 + V_2; V_1 + V_2 + Z) = \frac{1}{2}\log(1 + 2(P-Q))$. The total sum-rate (including the common part) is: $R_{1} + R_{2} \leq \frac{1}{2}\log(1 + 2P + 2\rho P) = \frac{1}{2}\log(1 + 2P(1+\rho))$.

Taking the union over $\rho \in [0, 1]$ (by symmetry, $\rho \geq 0$ suffices for the symmetric case) and verifying that Gaussian is optimal completes the derivation.

$Y = X_1 \oplus X_2$: $I(X_1, X_2; Y) = H(Y) \leq 1$ bit. So $R_{1} + R_{2} \leq 1$ (both users share a single output bit).

Round 1: User 1 sends $X_1 = W_{1,1}$ (first message bit). User 2 sends $X_2 = 0$. $Y = W_{1,1} \oplus 0 = W_{1,1}$. Receiver decodes $W_{1,1}$. With feedback, encoder 2 also learns $Y = W_{1,1}$.

Round 2: User 2 sends $X_2 = W_{2,1}$. User 1 sends $X_1 = 0$. $Y = 0 \oplus W_{2,1} = W_{2,1}$. Receiver decodes $W_{2,1}$.

By alternating: each user sends 1 bit per 2 channel uses, giving $R_{1} = R_{2} = 0.5$. But with a more clever scheme: User 1 sends $W_{1,1}$ in round 1, both learn it via feedback. User 2 XORs $W_{2,1}$ with $W_{1,1}$ (known from feedback) to "piggyback" on user 1's message. With $n$ rounds, both users achieve rate 1 bit per channel use. The full rectangle $R_{k} \leq 1$ is achievable.

With $X_1 \sim \text{Bern}(1/2)$ and $X_2 = 1$ (deterministic): $Y = X_1$, and $I(X_1; Y | X_2) = 1$, $I(X_2; Y | X_1) = 0$. By time-sharing, $R_{1} + R_{2} \leq 1$.

$n(R_{1} + R_{2}) \leq I(W_1; Y_2^n) + I(W_2; Y_1^n) \leq H(Y_2^n) + H(Y_1^n)$. Since $Y_1 = Y_2$: $\leq 2H(Y^n) \leq 2n$. But more tightly: $I(W_1; Y^n | W_2) + I(W_2; Y^n | W_1) \leq H(Y^n) \leq n$. (Because $Y^n$ has at most $n$ bits of entropy.)

Inner bound = outer bound = 1 bit sum-rate. Interaction cannot help because the output has only 1 bit per channel use regardless of the input distribution.

$I(X_1, X_2; Y) = H(Y) - H(Z) = H(X_1 + X_2 + Z) - \frac{1}{2}\log(2\pi e N)$. By the EPI: $2^{2H(X_1+X_2+Z)} \leq 2^{2H(X_1+X_2)} + 2^{2H(Z)}$. But we need an upper bound on $H(X_1+X_2+Z)$.

$\text{Var}(X_1 + X_2) = P_1 + P_2 + 2\text{Cov}(X_1, X_2) \leq P_1 + P_2 + 2\sqrt{P_1 P_2} = (\sqrt{P_1}+\sqrt{P_2})^2$. The inequality follows from Cauchy-Schwarz: $|\text{Cov}(X_1,X_2)| \leq \sqrt{P_1 P_2}$. Maximum entropy under this variance constraint: Gaussian with variance $(\sqrt{P_1}+\sqrt{P_2})^2$.

$I(X_1, X_2; Y) \leq \frac{1}{2}\log(1 + (\sqrt{P_1}+\sqrt{P_2})^2/N)$. This matches the Kramer-Gastpar achievable rate, proving tightness.

Since user 2 uses non-adaptive encoding: $X_{2,i} = f_{2,i}(W_2)$ does not depend on $Y_2^{i-1}$. The rate is limited to $R_{2} \leq I(X_2; Y_1 | X_1)$ for some fixed $p(x_2)$.

User 1 can adapt: $X_{1,i} = f_{1,i}(W_1, Y_1^{i-1})$. Since $Y_{1,i}$ depends on $X_{2,i}$ (which is fixed by user 2's one-shot code), user 1 can learn about $W_2$ through $Y_1^{i-1}$ and adapt its encoding to create useful correlation.

User 1's rate can exceed the Shannon inner bound because it can create input correlation through adaptation. But user 2 cannot do the same. The resulting region is asymmetric: user 1's achievable rate is larger than in the one-shot case, while user 2's rate is unchanged. This is strictly between the one-shot and fully interactive regions for channels where both directions benefit from interaction.

With feedback capacity $C_{\text{fb}}$, the encoders can exchange at most $C_{\text{fb}}$ bits per channel use of common information through the feedback. The maximum correlation coefficient scales as $\rho_{\max} \sim 1 - 2^{-2C_{\text{fb}}}$ (since $C_{\text{fb}}$ bits of feedback allow refining the common observation to $C_{\text{fb}}$ bits of precision).

The sum-rate is at least: $\frac{1}{2}\log(1 + (P_1 + P_2 + 2\rho_{\max}\sqrt{P_1P_2})/N)$. As $C_{\text{fb}} \to \infty$: $\rho_{\max} \to 1$, recovering Ozarow. As $C_{\text{fb}} \to 0$: $\rho_{\max} \to 0$, recovering no-feedback.

Even limited feedback provides a significant fraction of the full feedback gain. With $C_{\text{fb}} = 1$ bit per channel use, $\rho_{\max} \approx 0.75$, capturing most of the coherent combining gain. This justifies the use of low-rate feedback in practical wireless systems.

User 1 observes $Y_1 = X_1 \oplus X_2$ and knows $X_1$. It computes $X_2 = Y_1 \oplus X_1 = X_2$. User 1 perfectly recovers $X_2$ in one channel use. Similarly, user 2 perfectly recovers $X_1$.

Each user can transmit 1 bit per channel use and the other user decodes perfectly. The capacity region is $\{(R_{1}, R_{2}): R_{1} \leq 1, R_{2} \leq 1\}$.

$R_{1} \leq I(X_1; Y_2 | X_2) = I(X_1; X_1 \oplus X_2 | X_2) = H(X_1 | X_2) \leq 1$. Similarly for $R_{2}$. This matches the inner bound.

The capacity region is already a full rectangle $[0,1]^2$, achieved without interaction. Interaction cannot improve beyond 1 bit per user per channel use (the alphabet size constraint). The modular additive two-way channel is one of the rare cases where the capacity is known exactly and equals the Shannon inner bound.