Exercises

$C = 1 - 0.3 = 0.7$ bits/use. $V = 0.3 \times 0.7 \times (\log_2 e)^2 = 0.21 \times 2.081 = 0.437$ bits$^2$.

$0.5 = 0.7 - \sqrt{0.437/n} \times 3.09$. $\sqrt{0.437/n} = 0.2/3.09 = 0.0647$. $n = 0.437/0.0647^2 = 0.437/0.00419 = 104$.

With $p_X(0) = p_X(1) = 1/2$: $p_Y(0) = (1-p)/2 + p/2 = 1/2$. Similarly $p_Y(1) = 1/2$.

When $Y = X$: $\iota = \log_2\frac{1-p}{1/2} = 1 + \log_2(1-p)$. When $Y \ne X$: $\iota = \log_2\frac{p}{1/2} = 1 + \log_2 p$.

$\mathbb{E}[\iota] = (1-p)(1+\log_2(1-p)) + p(1+\log_2 p) = 1 - h(p) = C$. Correct.

$C = \frac{1}{2}\log_2(1 + 100) = \frac{1}{2}\log_2(101) \approx 3.33$ bits/use.

$V_{\text{nat}} = 100 \times 102 / (2 \times 101^2) = 10200/20402 = 0.4999$ nats$^2$. $V_{\text{bit}} = 0.4999 \times (\log_2 e)^2 = 0.4999 \times 2.081 = 1.040$ bits$^2$.

$R^* = 3.33 - \sqrt{1.040/1000} \times 4.26 = 3.33 - 0.0322 \times 4.26 = 3.33 - 0.137 = 3.19$ bits/use. This is $3.19/3.33 = 95.8\%$ of capacity. At high SNR with $n = 1000$, the gap is modest.

As $\text{SNR} \to 0$: $V = \text{SNR}(\text{SNR}+2)/(2(1+\text{SNR})^2) \approx 2\text{SNR}/2 = \text{SNR} \to 0$.

As $\text{SNR} \to \infty$: $V = \text{SNR}^{2}(1+2/\text{SNR})/(2\text{SNR}^{2}(1+1/\text{SNR})^2) \to 1/2$.

At low SNR, the channel is nearly deterministic (almost all noise, very little signal), so the information density has small variance. At high SNR, the variance saturates at 1/2, which is the variance of $\frac{1}{2}\log(1 + Z^2/\sigma^2)$ when $Z \sim \mathcal{N}(0, \sigma^2)$.

$C = 1 - h(0.05) = 1 - (-0.05\log_2 0.05 - 0.95\log_2 0.95) = 1 - 0.286 = 0.714$ bits/use. $V = 0.05 \times 0.95 \times (\log_2(0.95/0.05))^2 = 0.0475 \times (4.248)^2 \times (\log_2 e)^{-2} \times (\log_2 e)^2$. Actually: $V = 0.0475 \times (\log_2(19))^2 = 0.0475 \times 17.96 = 0.853$ bits$^2$.

$R^*(n, 10^{-6}) = 0.714 - \sqrt{0.853/n} \times 4.75$. Need $n \times R^*(n) \ge 256$.

Try $n = 500$: $R^* = 0.714 - \sqrt{0.00171} \times 4.75 = 0.714 - 0.196 = 0.518$. Bits: $500 \times 0.518 = 259 > 256$. Works.

Try $n = 450$: $R^* = 0.714 - \sqrt{0.00190} \times 4.75 = 0.714 - 0.207 = 0.507$. Bits: $450 \times 0.507 = 228 < 256$. Too short.

Approximately $n \approx 500$ channel uses.

With base-2 logarithm and uniform input: $\iota_0 = 1 + \log_2(1-p)$ with probability $1-p$, $\iota_1 = 1 + \log_2(p)$ with probability $p$.

$V = (1-p)(\iota_0 - C)^2 + p(\iota_1 - C)^2$. Note $\iota_0 - \iota_1 = \log_2((1-p)/p)$ and $C = (1-p)\iota_0 + p\iota_1$, so $\iota_0 - C = p(\iota_0 - \iota_1) = p\log_2((1-p)/p)$ and $\iota_1 - C = -(1-p)(\iota_0 - \iota_1) = -(1-p)\log_2((1-p)/p)$.

$V = (1-p) p^2 (\log_2((1-p)/p))^2 + p(1-p)^2(\log_2((1-p)/p))^2 = p(1-p)[p + (1-p)](\log_2((1-p)/p))^2 = p(1-p)(\log_2((1-p)/p))^2$.

For Gaussian codebook and ML decoding, the probability that a random codeword $\bar{X}^n$ has higher likelihood than the true codeword $X^n$ given output $Y^n$ is: $P_{\text{conf}} = \Pr[\|\bar{X}^n - Y^n\|^2 \le \|X^n - Y^n\|^2]$.

Since $X^n - Y^n = -Z^n$ and $\bar{X}^n - Y^n = \bar{X}^n - X^n - Z^n$, this involves the distribution of $\|\bar{X}^n - X^n - Z^n\|^2$ vs $\|Z^n\|^2$.

For large $n$, by the law of large numbers and Cramer's theorem: $P_{\text{conf}} \doteq e^{-nE_{\text{sp}}(R)}$ where $E_{\text{sp}}$ is the sphere-packing exponent. The RCU bound becomes: $(M-1)P_{\text{conf}} \doteq e^{n(R - E_{\text{sp}}(R))}$ which gives $\epsilon \doteq e^{-nE_r(R)}$ where $E_r(R) = E_{\text{sp}}(R) - R + C$ is the random coding exponent.

$C = 1$ bit/use, $V = 0.780$ bits$^2$. $R^* = 1 - \sqrt{0.780/128} \times 4.26 = 1 - 0.332 = 0.668$ bits/use. SNR for $R^* = 0.668$: $\text{SNR}' = 2^{2 \times 0.668} - 1 = 2^{1.336} - 1 = 1.525$. $\Delta = 10\log_{10}(1.525) - 0 = 1.83$ dB.

$C = 3.46$ bits/use, $V = 1.033$ bits$^2$. $R^* = 3.46 - \sqrt{1.033/128} \times 4.26 = 3.46 - 0.383 = 3.08$ bits/use. SNR for $R^* = 3.08$: $\text{SNR}' = 2^{6.16} - 1 = 70.8$ (18.5 dB). $\Delta = 18.5 - 10 = 8.5$ dB. Note: this is large because $C'(\text{SNR})$ is small at high SNR.

The penalty increases with SNR because $C'(\text{SNR})$ flattens out.

The Neyman-Pearson test compares $\sum_{i=1}^n \log(P(x_i)/Q(x_i))$ to a threshold $\tau_n$. Under $P^n$: $\frac{1}{n}\sum_i \log(P(x_i)/Q(x_i)) \to D(P\|Q)$ a.s. by SLLN.

Under $Q^n$: $\frac{1}{n}\sum_i \log(P(x_i)/Q(x_i)) \to -D(Q\|P)$ a.s. The threshold $\tau_n$ must satisfy $\Pr_{P^n}[\sum_i \log(P/Q) > \tau_n] \ge 1 - \epsilon$, so $\tau_n \approx nD(P\|Q) - O(\sqrt{n})$ (CLT correction).

Under $Q^n$: $\beta_{1-\epsilon} = \Pr_{Q^n}[\sum_i \log(P/Q) > \tau_n] \doteq e^{-nD(P\|Q)}$ by Cramer's theorem. Therefore $-\frac{1}{n}\log\beta_{1-\epsilon} \to D(P\|Q)$.

$C = \mathbb{E}_H[\log(1 + P|H|^2)] = \int_0^{\infty} \log(1 + Pt) e^{-t} dt = e^{1/P} E_1(1/P)$ (in nats), where $E_1$ is the exponential integral. For $P = 10$: $C \approx 2.51$ nats $= 3.62$ bits/use.

By the law of total variance: $V = \mathbb{E}_H[\text{Var}[\iota | H]] + \text{Var}_H[\mathbb{E}[\iota | H]] = \mathbb{E}_H[V_{\text{AWGN}}(P|H|^2)] + \text{Var}_H[\log(1 + P|H|^2)]$.

The first term is the average AWGN dispersion across fading realizations. The second term is the fading dispersion — the randomness of capacity across fading states. For Rayleigh fading, this second term dominates at low SNR.

The capacity is $C = \max_q [(1-q)\log(1/(1-q(1-p))) + q(1-p)\log((1-p)/(1-q(1-p)))]$. For $p = 0.2$, the optimal $q^* \approx 0.382$ and $C \approx 0.616$ bits/use.

The information density takes values depending on $(X, Y)$: $(0, 0)$: $\iota_1 = \log(1/(1-q^*(1-p)))$ with prob $(1-q^*)$ $(1, 1)$: $\iota_2 = \log((1-p)/(1-q^*(1-p)))$ with prob $q^*(1-p)$ $(1, 0)$: $\iota_3 = \log(p/(1-q^*(1-p)))$ with prob $q^*p$

$V = \sum_j p_j (\iota_j - C)^2$. For $p = 0.2$: $V \approx 0.51$ bits$^2$.

Given $H = h$, the channel is AWGN with capacity $C(h) = \log(1 + \text{SNR}|h|^2)$. If $R > C(h)$, then no code can achieve error probability $< 1/2$ on this realization (by the converse of the channel coding theorem for the AWGN channel).

$\epsilon = \mathbb{E}_H[\epsilon(H)] \ge \mathbb{E}_H[\epsilon(H) \cdot \mathbf{1}[C(H) < R]] \ge \frac{1}{2}\Pr[C(H) < R] = \frac{1}{2}P_{\text{out}}(R)$.

A tighter argument using the meta-converse shows $\epsilon \ge P_{\text{out}}(R)(1 - o(1))$, confirming that outage dominates at all finite blocklengths.

In quasi-static fading, diversity is essential: without it, the error probability is fundamentally limited by the outage probability, regardless of code length. The normal approximation is not useful here because the fading "dispersion" is infinite (the variance of $\log(1 + \text{SNR}|H|^2)$ does not shrink with $n$ when $H$ is constant over the block).

From the RCU bound: there exists a code with error $\epsilon$ if $(M-1)\Pr[\iota(\bar{X}^n; Y^n) \ge \iota(X^n; Y^n)] \le \epsilon$. This is equivalent to $M - 1 \le \epsilon / \Pr[\iota(\bar{X}^n; Y^n) \ge \gamma]$ where $\gamma$ is chosen to control the error.

Set $\gamma = nC - \sqrt{nV}\,Q^{-1}(\epsilon) + \delta_n$ where $\delta_n = O(1)$. By Berry-Esseen: $\Pr[\iota(X^n; Y^n) < \gamma] \le \epsilon + c_0 T/(V^{3/2}\sqrt{n})$. The confusion probability $\Pr[\iota(\bar{X}^n; Y^n) \ge \gamma] \le e^{-\gamma + nC} = e^{\sqrt{nV}Q^{-1}(\epsilon)}$.

$\log M \ge \gamma - \log(1/\epsilon) = nC - \sqrt{nV}\,Q^{-1}(\epsilon) + O(1)$. Dividing by $n$: $R \ge C - \sqrt{V/n}\,Q^{-1}(\epsilon) - O(1/n)$. The precise third-order term involves $c_0 T / V^{3/2}$.

For BSC($p$) with transmitted $x^n$ and received $y^n$: $\frac{P_{Y|X}^n(y^n|x^n)}{Q_Y^n(y^n)} = \frac{p^d (1-p)^{n-d}}{(1/2)^n} = 2^n p^d(1-p)^{n-d}$ where $d = d_H(x^n, y^n)$ is the Hamming distance.

Under $P^n$: $d \sim \text{Binom}(n, p)$. Under $Q^n$: $d \sim \text{Binom}(n, 1/2)$. The optimal test accepts $H_0$ when $d \le t$ for some threshold $t$. Set $t$ so that $\sum_{d=0}^t \binom{n}{d}p^d(1-p)^{n-d} \ge 1-\epsilon$.

$M \le 1/\beta_{1-\epsilon} = 1/\sum_{d=0}^t \binom{n}{d}(1/2)^n$.

For $n = 64$, $p = 0.11$, $\epsilon = 0.01$: find $t$ such that $\Pr[\text{Binom}(64, 0.11) \le t] \ge 0.99$, then evaluate $\beta = \Pr[\text{Binom}(64, 0.5) \le t]$.

Numerically: $t = 12$ gives $\Pr[d \le 12|P] \ge 0.99$. $\beta = \Pr[\text{Binom}(64, 0.5) \le 12] \approx 6.9 \times 10^{-7}$. $M \le 1/(6.9 \times 10^{-7}) \approx 1.45 \times 10^6$. $\log_2 M \le 20.4$ bits.

If $V = 0$, then $\iota(X_i; Y_i) = C$ with probability 1 for each $i$. The cumulative information density $\sum_i \iota(X_i; Y_i) = nC$ deterministically. There is no CLT correction; the convergence to capacity is determined by the $O(\log n/n)$ term in the finite-blocklength expansion.

The noiseless binary channel ($Y = X$) has $C = 1$ bit/use and $\iota(X; Y) = \log(p_{Y|X}(Y|X)/p_Y(Y)) = \log(1/p_Y(Y)) = \log 2 = 1$ bit deterministically under uniform input. So $V = 0$. At any finite $n$: $R^*(n, \epsilon) = 1 - O(\log n / n)$ for any $\epsilon > 0$.

The BEC has $V > 0$ (the erasure creates randomness in $\iota$), but some channels approach $V = 0$ behavior. Geometrically, $V = 0$ means the typical set has extremely sharp boundaries, so random coding works almost immediately.

$\iota_k = \iota(X_k; Y|X_{\bar{k}})$ is the AWGN information density at SNR $P/\sigma^2 = 10$. $\text{Var}[\iota_k] = V(10) = 10 \times 12 / (2 \times 121) = 0.496$ nats$^2$.

$\iota_{12} = \iota(X_1, X_2; Y)$ is the AWGN information density at SNR $2P = 20$. $\text{Var}[\iota_{12}] = V(20) = 20 \times 22 / (2 \times 441) = 0.499$ nats$^2$.

$\text{Cov}[\iota_1, \iota_2]$ and $\text{Cov}[\iota_k, \iota_{12}]$ are computed from the joint distribution of $(X_1, X_2, Y)$. Since $\iota_{12} = \iota_1 + \iota(X_2; Y)$ (chain rule), the correlations are non-zero.

The full $3 \times 3$ matrix $\mathbf{V}$ has entries computable from the moments of $(X_1^2, X_2^2, Z^2)$. The (3,3) entry is $0.499$ nats$^2$, confirming it equals $V(2P)$.

The information density for AWGN with Gaussian input is a quadratic form in Gaussian variables. Its CGF is: $\Lambda(s) = -\frac{1}{2}\log(1 - s^2 V_1) + \frac{s^2 V_2}{2(1 - s^2 V_1)}$ (up to constants depending on the SNR parametrization).

The saddlepoint $s^*$ satisfies $\Lambda'(s^*) = \gamma/n$ where $\gamma$ is the threshold in the hypothesis test. This gives a more accurate approximation than the CLT because it accounts for the skewness of the information density.

The saddlepoint approximation matches the exact RCU/MC bounds to within 0.01 bits/use for $n \ge 50$, compared to 0.05-0.1 bits/use for the normal approximation. This makes it the tool of choice for precise finite-blocklength analysis in system design.

Write $\mathbf{H} = \mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^H$ and transform to parallel channels: $\tilde{Y}_i = \sigma_i \tilde{X}_i + \tilde{Z}_i$ for $i = 1, \ldots, \min(N_t, N_r)$, with water-filling power $P_i$.

Each parallel channel has AWGN dispersion $V_i = \text{SNR}_{i}(\text{SNR}_{i} + 2)/(2(1+\text{SNR}_{i})^2)$ in nats$^2$.

Since the streams are independent (after unitary transformation): $V = \sum_i V_i$. The normal approximation gives: $R^*(n, \epsilon) = C_{\text{MIMO}} - \sqrt{V/n}\,Q^{-1}(\epsilon) + O(\log n/n)$.

$K_a$ active users, each with $B$ bits, blocklength $n$, over AWGN MAC. Each user transmits $\mathbf{x}_k = \sqrt{nP}\mathbf{c}_k(w_k)$ where $\mathbf{c}_k$ is drawn from a Gaussian codebook of size $2^B$.

Using the RCU bound for the Gaussian MAC: the PUPE satisfies $\epsilon \le K_a \cdot 2^B \cdot \Pr[\iota(\bar{X}; Y) \ge \iota(X; Y)] \approx K_a 2^B \exp(-nE_b/(2N_0))$ where $E_b = nP/B$.

Setting $\epsilon = 0.01$: $nE_b/(2N_0) \ge \log(100 K_a 2^B) = \log(100) + \log K_a + B\log 2$. For $K_a = n/\log n$ and $B = \log n$: $E_b/N_0 \ge \frac{2B}{n}(\log(100) + \log(n/\log n) + \log n \cdot \log 2) \approx \frac{4\log^2 n}{n}$ which goes to 0.

However, the per-user energy $nP$ must satisfy $K_a \cdot nP \le n P_{\text{total}}$, giving $P \le P_{\text{total}}/K_a$ and $E_b = nP_{\text{total}}/(K_a B)$.

For BSC with uniform codebook: $\epsilon_{\text{RCU}} = \sum_{d=0}^n \binom{n}{d}p^d(1-p)^{n-d} \min(1, (M-1)I_d)$ where $I_d = \sum_{d'=0}^d \binom{n}{d'}2^{-n}$ is the confusion probability at Hamming distance $d$.

$M_{\text{MC}} = 1/\beta_{1-\epsilon}(P_{Y|X=0}^n, Q_Y^n)$ with $Q_Y = \text{Uniform}$: find threshold $t$ such that $\Pr[\text{Binom}(n,p) \le t] \ge 1-\epsilon$, then $\beta = \Pr[\text{Binom}(n, 1/2) \le t]$.

The normal approximation is within 0.5 bits of the exact bounds for $n \ge 128$. For $n = 32$, the gap can be 1-2 bits. Best known codes (BCH for small $n$, polar for large $n$) are typically within 1-2 dB of the meta-converse.