Exercises

$H(X) = 1/2 + 1/2 + 1/2 = 3/2$ bits.

Typical set size $\approx 2^{100 \times 3/2} = 2^{150}$. Total sequences: $3^{100} = 2^{100 \log_2 3} \approx 2^{158.5}$. Fraction: $2^{150}/2^{158.5} = 2^{-8.5} \approx 0.003$.

False for the weak typical set (probabilities lie in a range $[2^{-n(H+\epsilon)}, 2^{-n(H-\epsilon)}]$, not at a single value).

For the type class $T_Q$ (a subset of the strongly typical set for a specific type $Q$), all sequences have exactly the same probability $\prod_a P(a)^{nQ(a)}$. But the typical set contains sequences from multiple types.

(a) $2^{1000}$.

(b) $H(X) = h_b(0.1) \approx 0.469$ bits. Typical set: $\approx 2^{1000 \times 0.469} = 2^{469}$.

(c) Fraction: $2^{469}/2^{1000} = 2^{-531} \approx 10^{-160}$.

A vanishingly small fraction of all binary sequences are typical for this highly biased source. The typical sequences have about 100 ones and 900 zeros (with fluctuations).

$H(X) = 1$ bit $= \log_2 2$. Typical set size $\approx 2^n$, which equals the total number of sequences. So the fraction approaches $1$. For a uniform source, all sequences are typical. This makes sense: every sequence is equally likely, so the AEP condition is trivially satisfied.

$\hat{P}(b|a) = \frac{\hat{P}(a,b)}{\hat{P}(a)}$.

By strong typicality: $\hat{P}(a,b) \in [(1-\epsilon)P(a,b), (1+\epsilon)P(a,b)]$ and $\hat{P}(a) \in [(1-\epsilon)P(a), (1+\epsilon)P(a)]$.

$\hat{P}(b|a) \in \left[\frac{(1-\epsilon)P(a,b)}{(1+\epsilon)P(a)}, \frac{(1+\epsilon)P(a,b)}{(1-\epsilon)P(a)}\right] = \left[\frac{1-\epsilon}{1+\epsilon}P(b|a), \frac{1+\epsilon}{1-\epsilon}P(b|a)\right]$.

As $\epsilon \to 0$: $\hat{P}(b|a) \to P(b|a)$. Specifically, $|\hat{P}(b|a) - P(b|a)| \leq \frac{2\epsilon}{1-\epsilon}P(b|a) \to 0$.

For $\mathbf{x} \in \mathcal{T}_\epsilon^{(n)}(X)$:

$\sum_{\mathbf{y} \in \mathcal{T}_\epsilon^{(n)}(Y|\mathbf{x})} P^n_{Y|X}(\mathbf{y}|\mathbf{x}) \to 1$.

Each $\mathbf{y} \in \mathcal{T}_\epsilon^{(n)}(Y|\mathbf{x})$ has $P^n_{Y|X}(\mathbf{y}|\mathbf{x}) \doteq 2^{-nH(Y|X)}$.

Upper bound: $1 \geq |\mathcal{T}_\epsilon^{(n)}(Y|\mathbf{x})| \cdot 2^{-n(H(Y|X)+\delta)}$.

Lower bound: $1 - \epsilon \leq |\mathcal{T}_\epsilon^{(n)}(Y|\mathbf{x})| \cdot 2^{-n(H(Y|X)-\delta)}$.

Therefore $|\mathcal{T}_\epsilon^{(n)}(Y|\mathbf{x})| \doteq 2^{nH(Y|X)}$.

1. If $\mathbf{x} \in A_\epsilon^{(n)}$: send a $0$ bit followed by the index of $\mathbf{x}$ in the typical set, using $\lceil\log|A_\epsilon^{(n)}|\rceil \leq n(H(X) + \epsilon)$ bits.

2. If $\mathbf{x} \notin A_\epsilon^{(n)}$: send a $1$ bit followed by the raw description of $\mathbf{x}$ using $n\log|\mathcal{X}|$ bits.

Average bits: $\leq (1)(1 + n(H+\epsilon)) + \epsilon(1 + n\log|\mathcal{X}|)$.

Per symbol: $\leq H(X) + \epsilon + \frac{1}{n} + \epsilon\log|\mathcal{X}| + \frac{\epsilon}{n}$.

For small $\epsilon$ and large $n$, this approaches $H(X)$.

$\log\binom{n}{pn} = \log n! - \log(pn)! - \log((1-p)n)!$

$\approx n\log n - pn\log(pn) - (1-p)n\log((1-p)n) + O(\log n)$

$= n[-p\log p - (1-p)\log(1-p)] + O(\log n)$

$= nh_b(p) + O(\log n)$.

Therefore $\binom{n}{pn} \doteq 2^{nh_b(p)}$. This shows that the type class of a binary type $Q = (p, 1-p)$ has size $\doteq 2^{nH(Q)}$, consistent with the general formula.

$\Pr(\hat{P}(1) \geq q) = \sum_{k \geq qn} \binom{n}{k} p^k (1-p)^{n-k}$

$= \sum_{Q: Q(1) \geq q} P^n(T_Q) \leq (n+1) \cdot \max_{Q: Q(1) \geq q} 2^{-nD(Q\|P)}$.

The minimum of $D(Q\|P)$ over $Q(1) \geq q$ is achieved at $Q^* = (1-q, q)$ (the boundary), giving $D((1-q,q)\|(1-p,p))$.

$\Pr(\hat{P}(1) \geq q) \geq P^n(T_{Q^*}) \geq \frac{1}{(n+1)^2} 2^{-nD(Q^*\|P)}$.

Together: $\Pr(\hat{P}(1) \geq q) \doteq 2^{-nD(q\|p)}$.

Fix $P_X^*$ achieving $C$. Generate $2^{nR}$ codewords $\mathbf{x}(m) \sim P_X^{*n}$ independently.

To send message $m$: transmit $\mathbf{x}(m)$. Decoder: find the unique $\hat{m}$ such that $(\mathbf{x}(\hat{m}), \mathbf{y}) \in \mathcal{T}_\epsilon^{(n)}(X,Y)$.

By symmetry, assume $m = 1$ was sent. Error event: $\{(\mathbf{x}(1), \mathbf{y}) \notin \mathcal{T}_\epsilon^{(n)}\} \cup \{\exists m \neq 1: (\mathbf{x}(m), \mathbf{y}) \in \mathcal{T}_\epsilon^{(n)}\}$.

First event: $\to 0$ by the AEP. Second event: $\to 0$ by the packing lemma, since $R < I(X^*;Y) = C$.

Therefore $P_e^{(n)} \to 0$, proving achievability.

Assign each $\mathbf{x} \in \mathcal{X}^n$ to a random bin $b(\mathbf{x})$ uniformly from $\{1, \ldots, 2^{nR_X}\}$.

Encoder for $X$: send $b(\mathbf{x})$. Encoder for $Y$: send $\mathbf{y}$ losslessly at rate $R_Y \geq H(Y)$.

The decoder knows $b(\mathbf{x})$ and $\mathbf{y}$. It finds the unique $\hat{\mathbf{x}}$ in bin $b$ that is jointly typical with $\mathbf{y}$.

Error occurs if: (a) $(\mathbf{x}, \mathbf{y}) \notin \mathcal{T}_\epsilon^{(n)}$ (probability $\to 0$), or (b) another $\tilde{\mathbf{x}} \neq \mathbf{x}$ in the same bin is jointly typical with $\mathbf{y}$.

Expected number of $\tilde{\mathbf{x}}$ in the same bin that are jointly typical: $\frac{|\mathcal{T}_\epsilon^{(n)}(X)| - 1}{2^{nR_X}} \cdot 2^{-nI(X;Y)}$ $\doteq 2^{nH(X)} \cdot 2^{-nR_X} \cdot 2^{-nI(X;Y)}$ $= 2^{n(H(X) - R_X - I(X;Y))}$ $= 2^{-n(R_X - H(X|Y))} \to 0$ if $R_X > H(X|Y)$.

A joint type $Q_{XY}$ assigns a non-negative integer count to each $(a,b) \in \mathcal{X} \times \mathcal{Y}$, with total $n$. The number of ways: $\binom{n + |\mathcal{X}||\mathcal{Y}| - 1}{|\mathcal{X}||\mathcal{Y}| - 1} \leq (n+1)^{|\mathcal{X}||\mathcal{Y}|}$.

For a fixed $\mathbf{x}$ with type $Q_X$: at each position where $x_i = a$, the value $y_i$ is drawn from the conditional type $Q_{Y|X=a}$. The number of such $\mathbf{y}$ is:

$|T_{Q_{Y|X}}(\mathbf{x})| = \prod_a \binom{nQ_X(a)}{nQ_{Y|X}(b|a): b \in \mathcal{Y}}$

$\doteq \prod_a 2^{nQ_X(a)H(Y|X=a)_Q} = 2^{nH(Y|X)_Q}$.

The proof uses the isoperimetric inequality on the Hamming cube. For i.i.d. sequences, the probability of being at Hamming distance $> n\delta$ from a set $S$ with $P^n(S) \geq 1/2$ decays exponentially in $n\delta^2$. This is the "blowing-up lemma" of Marton (1986), which is a key tool in the strong converse of the channel coding theorem.

The method of types approach: partition by type, use the type class concentration, and note that Hamming neighbors within the same type class are close in probability.

$C = 1 - h_b(0.11) \approx 1 - 0.500 = 0.500$ bits.

At uniform input: $I(X;Y) = 1 - h_b(0.11) \approx 0.500$.

The packing lemma gives error probability $\leq 2^{-n(I - R)} = 2^{-n(0.500 - 0.500)} = 2^0 = 1$.

This bound is useless because $R = C$! At capacity, the packing lemma bound does not decay. We need $R < C$ for a positive exponent. For $R = 0.4$: exponent $\approx 0.1$, and $P_e \leq 2^{-0.1n}$, which decays nicely.

A binary type is $(k/n, 1 - k/n)$ for $k = 0, 1, \ldots, n$. There are $n + 1 = 101$ possible types.

This matches the bound $(n+1)^{|\mathcal{X}|} = 101^2 = 10201$, which is loose. The exact count is $n + 1$ for binary alphabets.