Exercises

Let $X_k \sim \text{Bernoulli}(p_k)$ independently.

$I(X_1; Y | X_2 = 0) = 0$ since $Y = 0$ deterministically. $I(X_1; Y | X_2 = 1) = H(X_1) = h_b(p_1)$.

So $I(X_1; Y | X_2) = (1-p_2) \cdot 0 + p_2 \cdot h_b(p_1) = p_2 h_b(p_1)$. By symmetry, $I(X_2; Y | X_1) = p_1 h_b(p_2)$.

$I(X_1, X_2; Y) = H(Y)$ (since $Y$ is a deterministic function). $\Pr(Y=1) = p_1 p_2$, so $H(Y) = h_b(p_1 p_2)$.

We must optimize over $(p_1, p_2)$. For the sum rate, the maximum of $h_b(p_1 p_2)$ is 1 bit, achieved when $p_1 p_2 = 1/2$. But we also need $p_2 h_b(p_1) \geq R_{1}$ and $p_1 h_b(p_2) \geq R_{2}$.

The maximum sum rate is $\max h_b(p_1 p_2) = 1$ bit (e.g., $p_1 = 1, p_2 = 1/2$). At this point: $I(X_1;Y|X_2) = \frac{1}{2}h_b(1) = 0$, $I(X_2;Y|X_1) = h_b(1/2) = 1$. So user 1 cannot transmit!

The capacity region (convex hull over $(p_1,p_2)$) has sum rate at most 1 bit. One achievable extreme is $(R_{1}, R_{2}) = (0, 1)$ with $p_1 = 1$ (user 1 always sends 1, acting as a relay).

With $A = 3$, $B = 2$, $C = 4$:

$(0,0)$, $(3, 0)$, $(3, 1)$, $(2, 2)$, $(0, 2)$.

Rectangle area: $3 \times 2 = 6$. The sum-rate constraint cuts off a triangle with vertices $(3, 1)$, $(3, 2)$, $(2, 2)$. This triangle has base $1$ and height $1$, so area $1/2$.

Pentagon area: $6 - 1/2 = 5.5$ square bits.

Set $R_{1} = R_{2} = r$. We need $r \leq 3$, $r \leq 2$, and $2r \leq 4$, i.e., $r \leq \min(3, 2, 2) = 2$.

So the equal-rate point is $(R_{1}, R_{2}) = (2, 2)$, which is the corner point where both the $R_{2} \leq B$ and $R_{1} + R_{2} \leq C$ constraints are active.

By the chain rule for mutual information:

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

This uses: $I(X_1, X_2; Y) = H(Y) - H(Y|X_1, X_2)$ and $I(X_2; Y) + I(X_1; Y|X_2) = [H(Y) - H(Y|X_2)] + [H(Y|X_2) - H(Y|X_1,X_2)]$.

The second decomposition follows by symmetry (swapping user indices).

The decomposition $I(X_2; Y) + I(X_1; Y|X_2)$ corresponds to SIC with order $2 \to 1$: user 2 is decoded first at rate $I(X_2; Y)$ (treating user 1 as noise), then user 1 is decoded at rate $I(X_1; Y|X_2)$ (with user 2 removed). The total throughput equals $I(X_1, X_2; Y)$ regardless of the order.

$R_{1} \leq \frac{1}{2}\log(1 + 10) = \frac{1}{2}\log 11 \approx 1.730 \text{ bits},KATEXPLACEHOLDER0ENDR_{2} \leq \frac{1}{2}\log(1 + 1) = \frac{1}{2}\log 2 = 0.5 \text{ bits},KATEXPLACEHOLDER1ENDR_{1} + R_{2} \leq \frac{1}{2}\log(1 + 11) = \frac{1}{2}\log 12 \approx 1.792 \text{ bits}.$$

Order $2 \to 1$: $(R_{1}, R_{2}) = (\frac{1}{2}\log 11,\; \frac{1}{2}\log 12 - \frac{1}{2}\log 11) = (1.730,\; 0.062)$.

Order $1 \to 2$: $(R_{1}, R_{2}) = (\frac{1}{2}\log 12 - \frac{1}{2}\log 2,\; \frac{1}{2}\log 2) = (1.292,\; 0.500)$.

Let $\mathbf{r}' = (1.730, 0.062)$ and $\mathbf{r}'' = (1.292, 0.500)$. The time-shared rate is $\lambda \mathbf{r}' + (1-\lambda)\mathbf{r}''$. Setting $R_{1} = R_{2}$:

$$\lambda \cdot 1.730 + (1-\lambda) \cdot 1.292 = \lambda \cdot 0.062 + (1-\lambda) \cdot 0.500.$$

$$1.292 + 0.438\lambda = 0.500 - 0.438\lambda.$$

$$0.876\lambda = -0.792 \implies \lambda < 0.$$

Since $\lambda < 0$, the equal-rate point is not on the dominant face. It must lie on the $R_{2} = 0.5$ edge. Setting $R_{1} = 0.5$: we check $0.5 + 0.5 = 1.0 \leq 1.792$. Yes. So the equal-rate point is $(0.5, 0.5)$.

$C_{\text{MAC}} = \frac{1}{2}\log(1 + 2P), \quad C_{\text{TDMA}} = \frac{1}{2}\log(1 + 2P),KATEXPLACEHOLDER0ENDR_{1}^{\text{TDMA}} = \frac{1}{2}\cdot\frac{1}{2}\log(1+2P).$$Sum:$C_{\text{TDMA}} = 2\cdot\frac{1}{4}\log(1+2P) = \frac{1}{2}\log(1+2P) = C_{\text{MAC}}$.

Indeed, for the symmetric Gaussian MAC, the optimal TDMA sum rate equals the MAC sum rate. The MAC advantage is in the rate region shape, not the sum rate.

For asymmetric powers $P_1 \neq P_2$, the gap appears. With $P_1 = 2P$ and $P_2 = 0.5P$ (fixed total $2.5P$):

$C_{\text{MAC}} = \frac{1}{2}\log(1+2.5P)$.

For TDMA, the optimal split gives a strictly smaller sum rate. The ratio depends on the power asymmetry.

For any fixed power asymmetry:

As $\text{SNR} \to 0$: $\log(1+x) \approx x/\ln 2$, so both MAC and TDMA sum rates are approximately linear in total power, and the ratio approaches 1.

As $\text{SNR} \to \infty$: $\log(1+x) \approx \log x$, and the ratio also approaches 1 (logarithmic compression). The gap is largest at moderate SNR.

The messages $(W_1, W_2)$ are uniform over $\{1,\ldots,2^{nR_{1}}\} \times \{1,\ldots,2^{nR_{2}}\}$, so $H(W_1, W_2) = n(R_{1} + R_{2})$.

By Fano's inequality (applied to the pair $(W_1, W_2)$ as a single random variable over $2^{n(R_{1}+R_{2})}$ values):

$$H(W_1, W_2 | Y^n) \leq 1 + P_e^{(n)} \cdot n(R_{1}+R_{2}) \triangleq n\epsilon_n.$$

$n(R_{1}+R_{2}) = H(W_1,W_2) = I(W_1,W_2; Y^n) + H(W_1,W_2|Y^n)KATEXPLACEHOLDER0END\leq I(W_1,W_2; Y^n) + n\epsilon_n.KATEXPLACEHOLDER1ENDI(W_1,W_2; Y^n) \leq I(X_1^n, X_2^n; Y^n).$$Combining:$n(R_{1}+R_{2}) \leq I(X_1^n, X_2^n; Y^n) + n\epsilon_n$.$\blacksquare$

Let $\mathbf{A} = \mathbf{I} + \mathbf{H}_{1}\mathbf{K}_1\mathbf{H}_{1}^{H}$ and $\mathbf{B} = \mathbf{H}_{2}\mathbf{K}_2\mathbf{H}_{2}^{H}$. Then:

$$\mathbf{I} + \mathbf{B}\mathbf{A}^{-1} = \mathbf{A}^{-1}(\mathbf{A} + \mathbf{B}) = \mathbf{A}^{-1}(\mathbf{I} + \mathbf{H}_{1}\mathbf{K}_1\mathbf{H}_{1}^{H} + \mathbf{H}_{2}\mathbf{K}_2\mathbf{H}_{2}^{H}).$$

$\log\det(\mathbf{I} + \mathbf{B}\mathbf{A}^{-1}) = \log\det(\mathbf{A} + \mathbf{B}) - \log\det(\mathbf{A}).$$Adding the first term:$\log\det(\mathbf{A}) + \log\det(\mathbf{A}+\mathbf{B}) - \log\det(\mathbf{A}) = \log\det(\mathbf{A}+\mathbf{B})$$= \log\det(\mathbf{I} + \mathbf{H}{1}\mathbf{K}1\mathbf{H}{1}^{H} + \mathbf{H}{2}\mathbf{K}2\mathbf{H}{2}^{H})$.$\blacksquare$

For $K = 3$ users with equal power $P$ and noise 1:

$$g(s) = \frac{1}{2}\log\!\left(1 + \frac{sP}{(3-s)P + 1}\right) = \frac{1}{2}\log\frac{3P + 1}{(3-s)P + 1}.$$

With $P = 10$: $3P + 1 = 31$.

$g(1) = \frac{1}{2}\log\frac{31}{21} \approx 0.281$ bits. $g(2) = \frac{1}{2}\log\frac{31}{11} \approx 0.746$ bits. $g(3) = \frac{1}{2}\log\frac{31}{1} \approx 2.474$ bits.

$g(1) - g(0) = 0.281 - 0 = 0.281$. $g(2) - g(1) = 0.746 - 0.281 = 0.465$. $g(3) - g(2) = 2.474 - 0.746 = 1.728$.

Wait, the marginals are increasing, not decreasing! This seems to violate submodularity. Let us recheck.

Actually, $f(\mathcal{S}) = I(X(\mathcal{S}); Y | X(\mathcal{S}^c))$. For the symmetric Gaussian MAC:

$$f(\mathcal{S}) = \frac{1}{2}\log\!\left(1 + \frac{sP}{1}\right) = \frac{1}{2}\log(1+sP),$$

where the noise after canceling $\mathcal{S}^c$ users is just $N = 1$ (not $(3-s)P + 1$). Given $X(\mathcal{S}^c)$, the remaining channel is $Y - \sum_{k \notin \mathcal{S}} X_k = \sum_{k \in \mathcal{S}} X_k + Z$.

So: $g(1) = \frac{1}{2}\log(1+10) = 1.730$, $g(2) = \frac{1}{2}\log(1+20) = 2.197$, $g(3) = \frac{1}{2}\log(1+30) = 2.474$.

Marginals: $g(1) = 1.730$, $g(2)-g(1) = 0.467$, $g(3)-g(2) = 0.277$. These are decreasing: $1.730 > 0.467 > 0.277$. Submodularity holds.

$f(\{1,2\}) + f(\{2,3\}) = 2g(2) = 4.394$. $f(\{1,2,3\}) + f(\{2\}) = g(3) + g(1) = 2.474 + 1.730 = 4.204$.

Indeed $4.394 \geq 4.204$. Submodularity is verified. $\blacksquare$

$C_{\text{sum}}^{\text{CSIR}} = \mathbb{E}[\log(1 + P(|h_1|^2 + |h_2|^2))] = \mathbb{E}[\log(1 + PG)]$$where$G = |h_1|^2 + |h_2|^2 \sim \text{Gamma}(2, 1)$with PDF$f_G(g) = g e^{-g}$for$g \geq 0$.

For $P \gg 1$: $\log(1 + PG) \approx \log(PG) = \log P + \log G$.

$$C_{\text{sum}} \approx \log P + \mathbb{E}[\log G] = \log P + \frac{\mathbb{E}[\ln G]}{\ln 2}.$$

For $G \sim \text{Gamma}(2,1)$: $\mathbb{E}[\ln G] = \psi(2) = 1 - \gamma$.

$$C_{\text{sum}} \approx \log P + \frac{1 - \gamma}{\ln 2} = \log P + \log e \cdot (1 - \gamma).$$

Since $\log e \approx 1.443$: the offset is approximately $1.443 \times (1 - 0.577) = 0.610$ bits above $\log P$.

With opportunistic scheduling, only the best user transmits at each time. The effective channel gain is $G^* = \max_{k=1,\ldots,K} |h_k|^2$. The total transmit power is $KP$ (shared among users, but only one transmits at each time with the pooled power).

Actually, with individual power constraints $P$ per user, the active user transmits at power $P$ (not $KP$). The sum rate is:

$$C_{\text{sum}}^{\text{opp}} = \mathbb{E}[\log(1 + P \cdot G^*)].$$

For $K$ i.i.d. $\text{Exp}(1)$ random variables:

$$\mathbb{E}[G^*] = \mathbb{E}[\max_k |h_k|^2] = \sum_{j=1}^K \frac{1}{j} = H_K.$$

This is a well-known result: the expected maximum of $K$ i.i.d. exponentials with mean 1 is the harmonic number $H_K$.

By Jensen's inequality (concavity of log):

$$C_{\text{sum}}^{\text{opp}} = \mathbb{E}[\log(1+PG^*)] \leq \log(1 + P\mathbb{E}[G^*]) = \log(1 + PH_K).$$

At high SNR, $C_{\text{sum}}^{\text{opp}} \approx \log(PH_K) \approx \log P + \log\ln K$ (using $H_K \approx \ln K$ for large $K$).

Compare with CSIR: $C_{\text{sum}}^{\text{CSIR}} = \mathbb{E}[\log(1+P\sum_k |h_k|^2)]$. At high SNR, $\approx \log(PK) = \log P + \log K$.

The CSIR sum rate grows as $\log K$ with the number of users (because power adds linearly), while the opportunistic scheduling sum rate with individual power constraints grows as $\log\ln K$ (only multiuser diversity gain, not power pooling).

At corner point $A$: $R_{1} + R_{2} = 2 + 0.5 = 2.5$. At corner point $B$: $R_{1} + R_{2} = 1.5 + 1.2 = 2.7$.

These should be equal (both on the dominant face)! Since they are not equal, these are not both on the dominant face of the same pentagon. This means they come from different input distributions.

If they come from the same input distribution, then the sum rate at both corners equals $C = I(X_1,X_2;Y)$. Since $2.5 \neq 2.7$, these must be from different pentagons. The capacity region is the convex hull.

With $\lambda = 0.4$:

$$(R_{1}, R_{2}) = 0.4(2, 0.5) + 0.6(1.5, 1.2) = (0.8 + 0.9, 0.2 + 0.72) = (1.7, 0.92).$$

Time-sharing between points from different pentagons is just one way to convexify. In principle, coding schemes that use the channel differently in different time slots (with shared randomness/time-sharing variable $Q$) can achieve any point in the convex hull. But for the MAC, time-sharing is sufficient — no more sophisticated technique is needed because the capacity region is the closure of the convex hull. So no point strictly outside the convex hull of the union of pentagons can be achieved.

With $\mathbf{H}_{k} = \mathbf{I}_m$:

$$C_{\text{sum}} = \max_{\substack{\mathbf{K}_1 \succeq 0,\; \text{tr}(\mathbf{K}_1) \leq P \\ \mathbf{K}_2 \succeq 0,\; \text{tr}(\mathbf{K}_2) \leq P}} \log\det(\mathbf{I}_m + \mathbf{K}_1 + \mathbf{K}_2).$$

By water-filling: the optimal $\mathbf{K}_1 = (P/m)\mathbf{I}_m$, $\mathbf{K}_2 = (P/m)\mathbf{I}_m$ (isotropic, since the channel has no preferred direction). So:

$$C_{\text{sum}} = \log\det\!\left((1 + 2P/m)\mathbf{I}_m\right) = m\log(1 + 2P/m).$$

(b): A single user with $2m$ antennas, channel $\tilde{\mathbf{H}} = [\mathbf{I}_m \; \mathbf{I}_m]$, and power $2P$ has capacity:

$C = \max_{\tilde{\mathbf{K}} \succeq 0,\; \text{tr}(\tilde{\mathbf{K}}) \leq 2P} \log\det(\mathbf{I}_m + \tilde{\mathbf{H}}\tilde{\mathbf{K}}\tilde{\mathbf{H}}^H)$.

The constraint is on a general $2m \times 2m$ matrix $\tilde{\mathbf{K}}$, not block-diagonal. This has more freedom than the MAC constraint, so the single-user capacity is at least as large. With the block-diagonal constraint (MAC), the two are equal only if the optimal single-user $\tilde{\mathbf{K}}$ happens to be block-diagonal.

(c): Single-user with $\mathbf{H} = \mathbf{I}_m$ and power $2P$: $C = m\log(1+2P/m)$. This equals the MAC sum capacity! Because both users see the same channel $\mathbf{I}_m$, their combined effect is equivalent to a single user with power $2P$.

By the converse argument (Section 14.1), any achievable rate satisfies:

$$R_{1} \leq \frac{1}{n}\sum_{i=1}^n I(X_{1,i}; Y_i | X_{2,i}) + \epsilon_n.$$

For each $i$: $$I(X_{1,i}; Y_i | X_{2,i}) = h(X_{1,i} + Z_i) - h(Z_i).$$

Since $\mathbb{E}[X_{1,i}^2] \leq P_1$ and $Z_i \sim \mathcal{N}(0, N)$ independently, $X_{1,i} + Z_i$ has variance at most $P_1 + N$. By the maximum entropy property:

$$h(X_{1,i} + Z_i) \leq \frac{1}{2}\log(2\pi e(P_1 + N)),$$

with equality iff $X_{1,i} \sim \mathcal{N}(0, P_1)$.

$I(X_{1,i}; Y_i | X_{2,i}) \leq \frac{1}{2}\log\frac{P_1 + N}{N} = \frac{1}{2}\log\!\left(1 + \frac{P_1}{N}\right).KATEXPLACEHOLDER0ENDR_{1} \leq \frac{1}{2}\log\!\left(1 + \frac{P_1}{N}\right). \quad \blacksquare$$

User $\pi(k)$ is decoded $k$-th. After removing the first $k-1$ users, the remaining channel is $Y' = X_{\pi(k)} + \sum_{j=k+1}^K X_{\pi(j)} + Z$. The interference power is $(K-k)P$ and noise power is 1:

$$R_{\pi(k)} = \frac{1}{2}\log\!\left(1 + \frac{P}{(K-k)P + 1}\right).$$

User $\pi(K)$ (decoded last) achieves $R_{\pi(K)} = \frac{1}{2}\log(1 + P)$.

User $\pi(1)$ (decoded first) achieves $R_{\pi(1)} = \frac{1}{2}\log(1 + P/((K-1)P+1))$.

Since $(K-1)P + 1 > 1$ for $K \geq 2$, we have $R_{\pi(K)} > R_{\pi(1)}$. More generally, $R_{\pi(k)}$ is increasing in $k$ (later = cleaner channel).

$R_{\pi(1)} = \frac{1}{2}\log(1 + 10/41) \approx 0.165$ bits.

$R_{\pi(5)} = \frac{1}{2}\log(1 + 10) \approx 1.730$ bits.

The ratio is $1.730/0.165 \approx 10.5$. The last-decoded user gets more than 10 times the rate of the first-decoded user!

$\mathbb{E}[\max_k G_k] = \int_0^\infty \Pr(\max_k G_k > g)\,dg = \int_0^\infty [1 - (1-e^{-g})^K]\,dg.$$

Expand $(1-e^{-g})^K$ using the binomial theorem:

$$(1-e^{-g})^K = \sum_{j=0}^K \binom{K}{j}(-1)^j e^{-jg}.$$

So:

$$1 - (1-e^{-g})^K = -\sum_{j=1}^K \binom{K}{j}(-1)^j e^{-jg} = \sum_{j=1}^K \binom{K}{j}(-1)^{j+1} e^{-jg}.$$

Integrating:

$$\mathbb{E}[\max_k G_k] = \sum_{j=1}^K \binom{K}{j}\frac{(-1)^{j+1}}{j}.$$

We use the identity: $\sum_{j=1}^K \binom{K}{j}\frac{(-1)^{j+1}}{j} = H_K$.

This can be proven by noting that $\int_0^1 (1-t^K)/(1-t)\,dt = H_K$ and $\frac{1-t^K}{1-t} = \sum_{j=0}^{K-1} t^j$, or equivalently by the identity $\sum_{j=1}^K \binom{K}{j}\frac{(-1)^{j+1}}{j} = \int_0^1 \frac{1-(1-x)^K}{x}\,dx$ (substitute $x = 1-e^{-g}$).

The substitution $x = 1 - e^{-g}$, $dx = e^{-g}dg$, transforms our integral:

$$\int_0^\infty [1-(1-e^{-g})^K]\,dg = \int_0^1 \frac{1-x^K}{1-x} \cdot \frac{dx}{1-x}$$

Hmm, that does not simplify cleanly. Instead, directly:

$$\sum_{j=1}^K \binom{K}{j}\frac{(-1)^{j+1}}{j} = \int_0^1 \sum_{j=1}^K \binom{K}{j}(-1)^{j+1} t^{j-1}\,dt = \int_0^1 \frac{1-(1-t)^K}{t}\,dt.$$