Exercises

Since $Y = X$: $H(X|Y) = 0$, $H(Y|X) = 0$, $H(X,Y) = H(X) = 1$ bit.

$R_X \geq 0$, $R_Y \geq 0$, $R_X + R_Y \geq 1$. The minimum sum rate is 1 bit. One encoder can send 0 bits (be silent) while the other sends 1 bit — perfect correlation means one copy suffices.

$H(X|Y) = H(X) = 1$, $H(Y|X) = H(Y) = 1$, $H(X,Y) = 2$.

$R_X \geq 1$, $R_Y \geq 1$, $R_X + R_Y \geq 2$. The Slepian-Wolf region collapses to the single point $(R_X, R_Y) = (1, 1)$. Joint decoding provides no advantage when the sources are independent — as expected.

For continuous sources, the Slepian-Wolf rate region generalizes to the rate region where the excess rate over the joint differential entropy is minimized. The conditional differential entropies are:

$$h(X|Y) = \frac{1}{2}\log(2\pi e(1-\rho^2))$$

The rate region (in the differential entropy sense) is: $R_X \geq h(X|Y) = \frac{1}{2}\log(2\pi e(1-\rho^2))$, $R_Y \geq h(Y|X) = \frac{1}{2}\log(2\pi e(1-\rho^2))$, $R_X + R_Y \geq h(X,Y) = \frac{1}{2}\log((2\pi e)^2(1-\rho^2))$.

As $|\rho| \to 1$, $1-\rho^2 \to 0$ and the conditional rates decrease (more correlation means less to send). At $\rho = 0$, the conditional rate equals the marginal rate, and joint decoding provides no benefit.

Let $(R_X^{(1)}, R_Y^{(1)})$ and $(R_X^{(2)}, R_Y^{(2)})$ be two achievable rate pairs. A time-sharing strategy uses the first code for fraction $\alpha$ of the time and the second for fraction $1 - \alpha$:

$(R_X, R_Y) = (\alpha R_X^{(1)} + (1-\alpha) R_X^{(2)}, \alpha R_Y^{(1)} + (1-\alpha) R_Y^{(2)})$

Since both rate pairs satisfy $R_X^{(k)} + R_Y^{(k)} \geq H(X,Y)$:

$R_X + R_Y = \alpha(R_X^{(1)} + R_Y^{(1)}) + (1-\alpha)(R_X^{(2)} + R_Y^{(2)})$ $\geq \alpha H(X,Y) + (1-\alpha)H(X,Y) = H(X,Y)$.

Time-sharing preserves the sum-rate bound. The Slepian-Wolf region is already convex, so time-sharing does not enlarge it.

The achievable rate region is the set of $(R_X, R_Y, R_Z)$ satisfying:

$$R_X \geq H(X | Y, Z)$$ $$R_Y \geq H(Y | X, Z)$$ $$R_Z \geq H(Z | X, Y)$$ $$R_X + R_Y \geq H(X, Y | Z)$$ $$R_X + R_Z \geq H(X, Z | Y)$$ $$R_Y + R_Z \geq H(Y, Z | X)$$ $$R_X + R_Y + R_Z \geq H(X, Y, Z)$$

This follows from the same random binning argument, extended to three bins. There is one constraint for each non-empty subset $S \subseteq \{X, Y, Z\}$: $\sum_{V \in S} R_V \geq H(S | S^c)$.

From the Gaussian CEO sum-rate formula with symmetric agents, we need to solve $KR = R_{\text{sum}}(D)$ for $D$. For the standard case $\sigma_X^2 = 1$:

$$KR = \frac{K}{2}\log\frac{1/\sigma_N^2 + 1}{1/\sigma_N^2 + 1 - (1/D - 1)}$$

Simplifying: $2R = \log\frac{1/\sigma_N^2 + 1}{1/\sigma_N^2 + 1/D}$ (after algebraic manipulation).

$2^{2R} = \frac{1 + 1/\sigma_N^2}{1/D - 1 + K/\sigma_N^2 - (K-1)(1/D - 1)/(???)}KATEXPLACEHOLDER0ENDD(R, K) = \frac{1}{1 + K\sigma_N^{-2}(1 - 2^{-2R})}$$As$R \to \infty$:$D \to (1 + K/\sigma_N^2)^{-1}$, the MMSE. As$K \to \infty$:$D \to 0$ (infinite agents can reconstruct perfectly).

Since $P_e^{(n)} \to 0$, by Fano's inequality: $$H(X^n, Y^n | f_1(X^n), f_2(Y^n)) \leq 1 + P_e^{(n)} n\log(|\mathcal{X}||\mathcal{Y}|) \triangleq n\epsilon_n$$ where $\epsilon_n \to 0$.

$n(R_X + R_Y) \geq H(f_1(X^n)) + H(f_2(Y^n))KATEXPLACEHOLDER0END\geq H(f_1(X^n), f_2(Y^n))KATEXPLACEHOLDER1END= I(f_1(X^n), f_2(Y^n); X^n, Y^n) + H(f_1(X^n), f_2(Y^n) | X^n, Y^n)KATEXPLACEHOLDER2END\geq I(f_1(X^n), f_2(Y^n); X^n, Y^n)KATEXPLACEHOLDER3END= H(X^n, Y^n) - H(X^n, Y^n | f_1(X^n), f_2(Y^n))KATEXPLACEHOLDER4END\geq nH(X,Y) - n\epsilon_n$$Dividing by$n$and letting$n \to \infty$:$R_X + R_Y \geq H(X,Y)$.

Let $\mathbf{H}$ be the $(n-k) \times n$ parity-check matrix of an LDPC code with rate $k/n = 1 - \mathcal{H}_2(p) - \epsilon$. The syndrome has $n - k = n(\mathcal{H}_2(p) + \epsilon)$ bits.

Encoder: Computes $s = \mathbf{H}x^n$ and sends $s$ (rate $R_X = \mathcal{H}_2(p) + \epsilon$).

Decoder: Has $y^n$ and $s$. Computes $s' = s \oplus \mathbf{H}y^n = \mathbf{H}(x^n \oplus y^n) = \mathbf{H}z^n$. Since $z^n$ has i.i.d. $\text{Bernoulli}(p)$ entries, decoding $z^n$ from syndrome $s'$ is equivalent to decoding a BSC($p$) channel with the LDPC code.

The BSC($p$) has capacity $1 - \mathcal{H}_2(p)$, and our LDPC code has rate $1 - \mathcal{H}_2(p) - \epsilon < 1 - \mathcal{H}_2(p) = C_{\text{BSC}}$. Since capacity-approaching LDPC codes exist, the decoder can recover $z^n$ reliably, and hence $x^n = y^n \oplus z^n$. The Slepian-Wolf rate is $R_X = \mathcal{H}_2(p) + \epsilon \to H(X|Y) = \mathcal{H}_2(p)$.

$I(X; U_1, U_2) = I(X; U_1) + I(X; U_2 | U_1)KATEXPLACEHOLDER0ENDI(U_1; U_2) = I(U_1; U_2 | X) + I(U_1; U_2; X)$$Wait — let us use the identity:$I(U_1; U_2) = I(U_1; U_2 | X) + I(X; U_2 | U_1) - I(X; U_2 | U_1)$. Actually, more carefully:

By the Markov chain $U_1 - X - U_2$: $I(U_1; U_2 | X) = 0$.

Therefore: $I(U_1; U_2) = I(U_1; U_2) - I(U_1; U_2 | X)$ $= I(X; U_1; U_2) = I(X; U_2) - I(X; U_2 | U_1)$ (by the mutual information chain rule on three variables).

So: $I(X; U_1, U_2) + I(U_1; U_2)$ $= I(X; U_1) + I(X; U_2 | U_1) + I(X; U_2) - I(X; U_2 | U_1)$ $= I(X; U_1) + I(X; U_2)$.

But with the Markov chain, $I(U_1; U_2 | X) = 0$, so: $R_1 + R_2 \geq I(X; U_1) + I(X; U_2)$.

$C = 1 - \mathcal{H}_2(0.1) = 1 - (-0.1\log 0.1 - 0.9\log 0.9) \approx 1 - 0.469 = 0.531 \text{ bits}$$

$\tau > \frac{H(V)}{C} = \frac{2}{0.531} \approx 3.77$$We need at least$\lceil 3.77 \rceil = 4$channel uses per source symbol for reliable transmission. With$\tau = 4$, the effective channel rate budget is$4 \times 0.531 = 2.124 > 2 = H(V)$.

Let $X = \alpha V$ with $\alpha = \sqrt{P/\sigma^2}$. Then $Y = \alpha V + Z$ where $Z \sim \mathcal{N}(0, N)$.

The MMSE estimate is $\hat{V} = \mathbb{E}[V|Y] = \frac{\alpha\sigma^2}{\alpha^2\sigma^2 + N}Y$.

The MMSE is: $$D = \sigma^2 - \frac{\alpha^2\sigma^4}{\alpha^2\sigma^2 + N} = \frac{\sigma^2 N}{\alpha^2\sigma^2 + N} = \frac{\sigma^2 N}{P + N} = \frac{\sigma^2}{1 + P/N}$$

From $R(D) = C$: $$\frac{1}{2}\log\frac{\sigma^2}{D} = \frac{1}{2}\log\left(1 + \frac{P}{N}\right)$$

Solving: $D = \frac{\sigma^2}{1 + P/N}$. This matches the uncoded distortion exactly! Uncoded transmission is optimal for $\tau = 1$.

The modulo-2 adder MAC has capacity region $R_X + R_Y \leq 1$ (and the individual constraints $R_X \leq 1, R_Y \leq 1$). With separated coding, we need $R_X \geq H(X)$ and $R_Y \geq H(Y)$ for lossless source coding, plus $R_X + R_Y \leq 1$ for channel coding.

If $X, Y \sim \text{Bernoulli}(1/2)$, then $H(X) = H(Y) = 1$, requiring $R_X + R_Y \geq 2 > 1$. Separated coding fails!

With joint source-channel coding, User 1 sends $X^n$ directly (uncoded) and User 2 sends $Y^n$ directly. The receiver observes $Z^n = X^n \oplus Y^n$.

If $X$ and $Y$ are correlated with $\Pr(X \neq Y) = p < 1/2$, then $Z = X \oplus Y \sim \text{Bernoulli}(p)$, so $H(Z) = \mathcal{H}_2(p) < 1$. The receiver can recover $Z^n$ (the "difference" between $X$ and $Y$) and, combined with the MAC structure, reconstruct both sources.

This is a case where joint source-channel coding strictly outperforms separated coding by exploiting the correlation structure at the physical layer.

By the covering lemma, to find $U^n$ jointly typical with $X^n$ in a codebook of size $2^{n\tilde{R}_X}$ drawn i.i.d. $\sim P_U$:

$$\tilde{R}_X > I(X; U) + \delta(\epsilon)$$

The $2^{n\tilde{R}_X}$ sequences are partitioned into $2^{nR_X}$ bins. By the Slepian-Wolf argument, the decoder can recover $U^n$ from the bin index and $V^n$ if the number of sequences per bin is less than the conditional typical set size:

$$2^{n(\tilde{R}_X - R_X)} < 2^{n(H(U|V) - \delta(\epsilon))}$$ $$\implies \tilde{R}_X - R_X < H(U|V) - \delta(\epsilon)$$

From covering: $\tilde{R}_X > I(X; U) + \delta(\epsilon)$. From binning: $R_X > \tilde{R}_X - H(U|V) + \delta(\epsilon)$.

Therefore: $R_X > I(X; U) - H(U|V) + 2\delta(\epsilon)$.

Now $I(X; U) - H(U|V) = H(U) - H(U|X) - H(U|V)$. Using $I(U;V) = H(U) - H(U|V)$: $= I(U;V) - H(U|X) = I(U;V) - [H(U) - I(X;U)]$ $= I(X;U) - H(U) + I(U;V)$.

Alternatively: $I(X;U) - H(U|V) = I(X;U|V)$ since $I(X;U|V) = H(U|V) - H(U|X,V) = H(U|V) - H(U|X)$ and $I(X;U) = H(U) - H(U|X)$. So $I(X;U) - H(U|V) = H(U) - H(U|V) - [H(U) - I(X;U|V) - H(U|V)]$...

More directly: $R_X > I(X; U | V) + 2\delta(\epsilon)$. Letting $\epsilon \to 0$: $R_X \geq I(X; U | V)$.

No excess rate means $R_1 + R_2 = R(D_0) = \min I(X; U_1, U_2)$ where the minimum is over $(U_1, U_2)$ achieving distortion $D_0$.

From the El Gamal-Cover sum-rate constraint: $R_1 + R_2 \geq I(X; U_1, U_2) + I(U_1; U_2)$

For this to equal $I(X; U_1, U_2)$ (no excess), we need $I(U_1; U_2) = 0$.

Since $U_1 - X - U_2$ is a Markov chain, $I(U_1; U_2 | X) = 0$. And $I(U_1; U_2) = I(U_1; U_2 | X) + I(X; U_1; U_2)$ (not quite...).

Actually: $I(U_1; U_2) = 0$ means $U_1 \perp U_2$ — the two descriptions are independent. Combined with the Markov chain $U_1 - X - U_2$, this means the descriptions carry completely complementary information about $X$ with zero redundancy. No excess rate is achievable only when the descriptions can be made independent while still jointly achieving distortion $D_0$.

Both $X$ and $Y$ are uniform on $\{0, 1, 2\}$: $P_X(x) = P_Y(y) = 1/3$. So $H(X) = H(Y) = \log 3 \approx 1.585$ bits.

$H(X, Y) = \log 6 \approx 2.585$ bits (6 equally likely pairs).

$H(X|Y) = H(X,Y) - H(Y) = \log 6 - \log 3 = \log 2 = 1$ bit. Similarly $H(Y|X) = 1$ bit.

The Slepian-Wolf region is: $R_X \geq 1$, $R_Y \geq 1$, $R_X + R_Y \geq \log 6 \approx 2.585$.

The sum-rate constraint is binding: $\log 6 > 1 + 1 = 2$, so the sum-rate is the active constraint for rate pairs near $R_X = R_Y$. The corner points are $(1, \log 3)$ and $(\log 3, 1)$.