Information theory

The logarithm is concave, so "on average" it lies below its tangent line. Gibbs' inequality is exactly Jensen's inequality applied to the concave function $\log_2$, weighted by $p$: it says that replacing each ratio $q_i/p_i$ by its $p$-weighted average (which equals $1$) inside the logarithm can only increase the sum, forcing the divergence to be nonnegative.

Start from the elementary inequality $\ln x \le x - 1$ for all $x > 0$, with equality only at $x=1$ (this follows since $f(x) = \ln x - (x-1)$ has $f(1)=0$, $f'(x) = 1/x - 1$, which is positive for $x<1$ and negative for $x>1$, so $f$ has a unique maximum at $x=1$). Dividing by $\ln 2$ gives $\log_2 x \le (x-1)/\ln 2$.

Apply this with $x = q_i/p_i$ for each $i$: $\log_2(q_i/p_i) \le (q_i/p_i - 1)/\ln 2$. Multiply both sides by $p_i > 0$ (which does not flip the inequality) and sum over $i$: $\sum_i p_i \log_2(q_i/p_i) \le \frac{1}{\ln 2}\sum_i (q_i - p_i) = \frac{1}{\ln 2}\left(\sum_i q_i - \sum_i p_i\right) = \frac{1}{\ln 2}(1 - 1) = 0$, since both $p$ and $q$ are probability distributions summing to $1$.

The left side is exactly $-D(p\|q)$ (note the sign flip from $q_i/p_i$ versus $p_i/q_i$ inside the log), so this proves $D(p\|q) \ge 0$.

Equality throughout requires equality in $\ln x \le x-1$ for every $i$ with $p_i > 0$, which happens only when $q_i/p_i = 1$ for every such $i$, i.e. $p = q$.

The lower bound says entropy is a hard floor: no lossless prefix code can, on average, beat $H(X)$ bits per symbol, because doing better would require the code-induced distribution to differ from $X$'s true distribution in a way Gibbs' inequality forbids. The upper bound says this floor is nearly achievable: rounding each ideal length $-\log_2 p_i$ up to an integer wastes less than one bit on average.

For the lower bound, let $l_i$ be the lengths of any prefix code, so $\sum_{i=1}^n 2^{-l_i} \le 1$. Define $q_i = 2^{-l_i}/Z$ where $Z=\sum_j 2^{-l_j} \le 1$, so $q$ is a probability distribution. By Gibbs' inequality, $0 \le D(p\|q) = \sum_i p_i \log_2(p_i/q_i) = \sum_i p_i\log_2 p_i - \sum_i p_i \log_2(2^{-l_i}/Z) = -H(X) + \sum_i p_i l_i + \log_2 Z$. Since $Z \le 1$, $\log_2 Z \le 0$, so $0 \le -H(X) + L + \log_2 Z \le -H(X) + L$, which rearranges to $L \ge H(X)$.

For the upper bound (achievability), choose $l_i = \lceil -\log_2 p_i \rceil$ for each $i$ (round the ideal length up to the nearest integer). These lengths satisfy Kraft's inequality since $2^{-l_i} \le 2^{-(-\log_2 p_i)} = p_i$, so $\sum_i 2^{-l_i} \le \sum_i p_i = 1$; by the Kraft–McMillan construction such lengths can always be realized as an actual prefix code (build the code by assigning binary strings level by level in a binary tree).

By definition of ceiling, $l_i < -\log_2 p_i + 1$. Multiplying by $p_i \ge 0$ and summing over $i$ gives $L = \sum_i p_i l_i < \sum_i p_i(-\log_2 p_i + 1) = H(X) + 1$.

Combining both parts, this construction achieves $H(X) \le L < H(X) + 1$.

Capacity is not merely a convenient formula — it is a genuine wall. Below it, spreading each message over a long enough block lets random-looking codewords stay distinguishable despite noise, so errors can be driven to zero; above it, the channel destroys information faster than any code can protect it, no matter how clever the code.

**Converse ($R > C \Rightarrow P_e \not\to 0$).** Fano's inequality bounds the receiver's remaining uncertainty about the message given the noisy output: $H(X\mid Y) \le 1 + P_e \log_2(n-1)$, where $n$ is the number of possible messages. Meanwhile, the data-processing structure of the channel forces $I(X;Y) \le C$ for every use, so over a block of $N$ channel uses the total information the receiver can extract is at most $NC$ bits. If the true rate is $R > C$ bits per use, the message carries $NR$ bits of entropy but the channel supplies only about $NC < NR$ bits about it; Fano's inequality then forces $P_e$ to stay bounded away from $0$ as $N$ grows, since the leftover uncertainty $H(X\mid Y)$ cannot be made to vanish.

**Achievability sketch ($R < C \Rightarrow P_e \to 0$).** Fix an input distribution $p(x)$ achieving the capacity and generate a codebook of $2^{NR}$ codewords of length $N$ independently at random from $p(x)^N$. To decode, the receiver looks for the unique codeword that is jointly typical with the received sequence (i.e. behaves, in its statistical patterns, like a genuine input–output pair). Because $R < C$, the number of candidate codewords ($2^{NR}$) is far smaller than the number of statistically distinguishable channel outputs ($\approx 2^{NC}$), so as $N \to \infty$ the chance that some other, unsent codeword accidentally looks jointly typical with the received sequence shrinks to $0$, and so does the decoding error probability, averaged over the random choice of codebook — hence at least one codebook must achieve arbitrarily small $P_e$.