Exercises

$\mathcal{H}_2(0.01) = -0.01 \cdot (-6.644) - 0.99 \cdot (-0.0145) = 0.06644 + 0.01436 = 0.0808$ bits

$C = 1 - 0.0808 = 0.919$ bits per channel use.

So with a well-designed code, about 92% of the channel's potential is usable despite the 1% error rate. This illustrates why modern codes (LDPC, polar) that approach capacity are so valuable.

$C_{\text{BEC}} = 1 - 0.3 = 0.7$ bits per channel use.

$\mathcal{H}_2(0.3) = -0.3\log_2 0.3 - 0.7\log_2 0.7 \approx 0.521 + 0.360 = 0.881$. $C_{\text{BSC}} = 1 - 0.881 = 0.119$ bits per channel use.

$C_{\text{BEC}} = 0.7 \gg C_{\text{BSC}} = 0.119$. The BEC has nearly 6 times the capacity of the BSC at the same parameter value! This is because erasures are much less harmful than errors: the decoder knows which bits were lost and can focus its effort there.

If all rows of $\mathbf{P}$ are identical (say, equal to $\mathbf{q}$), then $P_Y(y) = \sum_x P_X(x) P_{Y|X}(y|x) = q(y)$ for any $P_X$. So $Y$ is independent of $X$ and $I(X;Y) = 0$ for all $P_X$. Therefore $C = 0$.

If $C = 0$, then $I(X;Y) = 0$ for all $P_X$. In particular, for $P_X$ that puts positive mass on every $x \in \mathcal{X}$, we need $D(P_{XY} \| P_X P_Y) = 0$, which means $P_{Y|X}(y|x) = P_Y(y)$ for all $(x, y)$ with $P_X(x) > 0$. Since this holds for all $x$, all rows of $\mathbf{P}$ equal $P_Y = \mathbf{q}$.

Each row is a permutation of $(1/2, 1/4, 1/4)$ — verified by inspection. Each column is also a permutation of $(1/2, 1/4, 1/4)$ — verified. So the channel is strongly symmetric.

$C = \log 3 - \mathcal{H}(1/2, 1/4, 1/4)KATEXPLACEHOLDER0END= \log_2 3 - (-\frac{1}{2}\log_2\frac{1}{2} - \frac{1}{4}\log_2\frac{1}{4} - \frac{1}{4}\log_2\frac{1}{4})KATEXPLACEHOLDER1END= 1.585 - (0.5 + 0.5 + 0.5) = 1.585 - 1.5 = 0.085 \text{ bits}$$

The uniform input distribution is optimal.

$H(Y|X) = \sum_x P_X(x) H(Y|X=x)$ is a linear function of $P_X$ (it is a weighted sum with fixed coefficients $H(Y|X=x)$).

The output distribution is $P_Y(y) = \sum_x P_X(x) P_{Y|X}(y|x)$, which is linear in $P_X$. The entropy $H(Y)$ is a concave function of $P_Y$ (a standard property). The composition of a concave function with a linear (affine) map is concave. So $H(Y)$ is concave in $P_X$.

$I(X;Y) = H(Y) - H(Y|X)$ is concave minus linear, which is concave. Therefore $\max_{P_X} I(X;Y)$ is a concave maximization problem with a unique global optimum.

Use a random linear code with $k \times n$ generator matrix $\mathbf{G}$ drawn uniformly at random over $\mathbb{F}_2$. The encoder computes $x^n = m^k \mathbf{G}$ for message $m^k \in \mathbb{F}_2^k$.

After transmission through BEC($\epsilon$), approximately $n(1-\epsilon)$ positions are received correctly. This gives a system of $n(1-\epsilon)$ linear equations in $k$ unknowns (the message bits).

The decoder can recover $m^k$ if and only if the $n(1-\epsilon)$ unerased columns of $\mathbf{G}$ span $\mathbb{F}_2^k$ (the system has full rank $k$).

For a random $\mathbf{G}$, the probability that $n(1-\epsilon)$ random columns span $\mathbb{F}_2^k$ approaches 1 as $n \to \infty$, provided $k < n(1-\epsilon)$, i.e., $R = k/n < 1 - \epsilon = C$.

The probability of failure (rank deficiency) is bounded by: $$P_e \leq 2^{k - n(1-\epsilon)} = 2^{n(R - 1 + \epsilon)}$$

which vanishes exponentially for $R < 1 - \epsilon = C$. (A more careful analysis using concentration of the number of erasures around $n\epsilon$ is needed for the precise statement, but the intuition is clear: with enough unerased observations, the linear system is solvable.)

For message $m$, the decoder declares $\hat{m} = m$ only if $y^n$ is "closer" to $x^n(m)$ than to any other codeword. The probability of correct decoding for message $m$ is:

$$P_{c,m} = \sum_{y^n} P_{Y^n|X^n}(y^n | x^n(m)) \cdot \mathbf{1}\{g(y^n) = m\}$$

The output distribution given input $x^n(m)$ concentrates on sequences $y^n$ with joint type close to $P_{XY}$. The number of "distinguishable" output sequences (those in the typical set around $x^n(m)$) is approximately $2^{nH(Y|X)}$.

For correct decoding, the decoder's decision region for message $m$ must include most of these $2^{nH(Y|X)}$ sequences. But the total number of output sequences is $2^{nH(Y)}$, and there are $2^{nR}$ codewords.

If $R > C = H(Y) - H(Y|X)$, then $2^{nR} \cdot 2^{nH(Y|X)} > 2^{nH(Y)}$, so the decision regions must overlap significantly, forcing $P_{c,m} \to 0$ for most messages. More precisely, $P_e^{(n)} \to 1$.

With $\mathbf{p}^{(0)} = (0.5, 0.5)$:

$P_Y(0) = 0.5 \cdot 0.9 + 0.5 \cdot 0.1 = 0.5$ $P_Y(1) = 0.5 \cdot 0.1 + 0.5 \cdot 0.9 = 0.5$

$Q_{0,0} = \frac{0.5 \cdot 0.9}{0.5} = 0.9$, $Q_{0,1} = \frac{0.5 \cdot 0.1}{0.5} = 0.1$ $Q_{1,0} = \frac{0.5 \cdot 0.1}{0.5} = 0.1$, $Q_{1,1} = \frac{0.5 \cdot 0.9}{0.5} = 0.9$

$p_0^{(1)} \propto \exp(0.9\log 0.9 + 0.1\log 0.1) = \exp(-0.469\ln 2) = 2^{-0.469}$ $p_1^{(1)} \propto \exp(0.1\log 0.9 + 0.9\log 0.1) = \exp(-0.469\ln 2) = 2^{-0.469}$

By symmetry: $\mathbf{p}^{(1)} = (0.5, 0.5)$.

$I(X;Y) = 1 - \mathcal{H}_2(0.1) = 1 - 0.469 = 0.531$ bits.

The BSC is symmetric, so the algorithm converges in one iteration to the uniform distribution. For asymmetric channels, multiple iterations are needed.

$C = 1 - 0.4 = 0.6$ bits per channel use. $\tauC = 3 \times 0.6 = 1.8$ bits per source symbol.

Since $H(V) = 1.5 < 1.8 = \tauC$, the source is transmissible. Separate source coding at rate $> 1.5$ bits/symbol followed by channel coding at rate $< 0.6$ bits/use achieves reliable transmission.

Let $\alpha = P_X(1)$. Then $P_Y(1) = \alpha(1-p) + (1-\alpha)p = p + \alpha(1-2p)$.

$I = \mathcal{H}_2(p + \alpha(1-2p)) - \mathcal{H}_2(p)$.

$\frac{dI}{d\alpha} = (1-2p) \cdot \mathcal{H}_2'(p + \alpha(1-2p))$$where$\mathcal{H}_2'(q) = -\log q + \log(1-q) = \log\frac{1-q}{q}$. Setting$\frac{dI}{d\alpha} = 0$: either$p = 1/2$(trivial channel) or$\mathcal{H}_2'(P_Y(1)) = 0$, i.e.,$P_Y(1) = 1/2$.$P_Y(1) = 1/2 \implies p + \alpha(1-2p) = 1/2 \implies \alpha = 1/2$.

Let $\alpha_0 = \alpha_2 = \alpha$ and $\alpha_1 = 1 - 2\alpha$.

$P_Y(0) = \alpha \cdot 1 + (1-2\alpha) \cdot 1/2 + \alpha \cdot 0 = \alpha + (1-2\alpha)/2 = 1/2$.

Interesting: $P_Y$ is always $(1/2, 1/2)$ for this symmetric parameterization! So $H(Y) = 1$ bit.

$H(Y|X) = \alpha \cdot 0 + (1-2\alpha) \cdot 1 + \alpha \cdot 0 = 1 - 2\alpha$.

$I(X;Y) = 1 - (1 - 2\alpha) = 2\alpha$.

Maximized at $\alpha = 1/2$... but $\alpha_1 = 1 - 2\alpha \geq 0$ requires $\alpha \leq 1/2$.

At $\alpha = 1/2$: $P_X = (1/2, 0, 1/2)$ and $C = 1$ bit.

The optimal strategy never uses input 1 (the noisy input). By using only inputs 0 and 2, the channel becomes noiseless (0 maps deterministically to output 0, 2 maps deterministically to output 1).

Let $P_X^{(1)}$ achieve $C(B_1)$ and $P_X^{(2)}$ achieve $C(B_2)$. Consider $P_X^{(\lambda)} = \lambda P_X^{(1)} + (1-\lambda) P_X^{(2)}$.

Cost: $\mathbb{E}_{P_X^{(\lambda)}}[b(X)] = \lambda B_1 + (1-\lambda) B_2$.

By concavity of $I(X;Y)$ in $P_X$: $$I_{P_X^{(\lambda)}}(X;Y) \geq \lambda I_{P_X^{(1)}}(X;Y) + (1-\lambda)I_{P_X^{(2)}}(X;Y)$$ $$= \lambda C(B_1) + (1-\lambda)C(B_2)$$

Since $P_X^{(\lambda)}$ is feasible for cost $\lambda B_1 + (1-\lambda)B_2$: $$C(\lambda B_1 + (1-\lambda)B_2) \geq \lambdaC(B_1) + (1-\lambda)C(B_2)$$

This is exactly the definition of concavity.

Row 0: $(0.8, 0.1, 0.1)$. Row 1: $(0.1, 0.1, 0.8)$. Row 1 is a permutation of Row 0 (swap first and third elements). So the channel is weakly symmetric.

Check columns: Column 0 is $(0.8, 0.1)$, Column 1 is $(0.1, 0.1)$, Column 2 is $(0.1, 0.8)$. Column 0 and Column 2 are permutations; Column 1 is constant. Not all columns are permutations of each other, so not strongly symmetric.

For weakly symmetric channels: $H(Y|X)$ is the same for all $x$: $H(Y|X=x) = \mathcal{H}(0.8, 0.1, 0.1) = -0.8\log 0.8 - 2(0.1\log 0.1) \approx 0.922$.

$C = \max_{P_X} H(Y) - 0.922$.

With $P_X(0) = P_X(1) = 1/2$: $P_Y = (0.45, 0.1, 0.45)$. $H(Y) = -2(0.45\log 0.45) - 0.1\log 0.1 = 1.477$ bits. $I = 1.477 - 0.922 = 0.555$ bits.

Since the channel is weakly symmetric with a "balanced" structure, $P_X = (1/2, 1/2)$ is likely optimal, giving $C \approx 0.555$ bits.

For fixed $\mathbf{p}^{(\ell)}$, the E-step sets $\mathbf{Q}^{(\ell+1)}$ to the Bayes-optimal backward channel, which maximizes $J$ over $\mathbf{Q}$. So $J(\mathbf{p}^{(\ell)}, \mathbf{P}, \mathbf{Q}^{(\ell+1)}) \geq J(\mathbf{p}^{(\ell)}, \mathbf{P}, \mathbf{Q}^{(\ell)})$.

Moreover, $J(\mathbf{p}^{(\ell)}, \mathbf{P}, \mathbf{Q}^{(\ell+1)}) = I_{P_X = \mathbf{p}^{(\ell)}}(X;Y)$.

For fixed $\mathbf{Q}^{(\ell+1)}$, the M-step maximizes $J$ over $\mathbf{p} \in \mathcal{B}$ (the cost-constrained simplex). Since $J$ is concave in $\mathbf{p}$ for fixed $\mathbf{Q}$, the M-step finds the global max: $J(\mathbf{p}^{(\ell+1)}, \mathbf{P}, \mathbf{Q}^{(\ell+1)}) \geq J(\mathbf{p}^{(\ell)}, \mathbf{P}, \mathbf{Q}^{(\ell+1)})$.

Combining: $J^{(\ell+1)} \geq J^{(\ell)}$ (non-decreasing). Since $J \leq C(B)$ (bounded above), the sequence converges. At convergence, both the E-step and M-step are fixed points, which means $\mathbf{p}^{(\infty)}$ satisfies the KKT conditions for $\max_{\mathbf{p} \in \mathcal{B}} I(X;Y)$. By concavity, the KKT point is the global maximum, so $J^{(\infty)} = C(B)$.

$P_Y(0) = (1-\alpha)(1-p_0) + \alpha p_1$, $P_Y(1) = (1-\alpha)p_0 + \alpha(1-p_1)$.

$H(Y|X) = (1-\alpha)\mathcal{H}_2(p_0) + \alpha\mathcal{H}_2(p_1)$.

$I(X;Y) = \mathcal{H}_2(P_Y(1)) - (1-\alpha)\mathcal{H}_2(p_0) - \alpha\mathcal{H}_2(p_1)$.

$\frac{dI}{d\alpha} = (1-p_1-p_0)\log\frac{1-P_Y(1)}{P_Y(1)} - \mathcal{H}_2(p_1) + \mathcal{H}_2(p_0) = 0$$When$p_0 = p_1$:$\mathcal{H}_2(p_0) = \mathcal{H}_2(p_1)$and we get$P_Y(1) = 1/2$, giving$\alpha = 1/2$(uniform input). When$p_0 \neq p_1$: the optimal$\alpha^*$must satisfy a transcendental equation — it is generally not$1/2$. The channel asymmetry pushes the optimal input towards the "better" direction.