Entropy III: Shannon’s Theorem

15-minute mathematical summary · Lecture 23

Sariel Har-Peled

CS 574 · University of Illinois, Urbana-Champaign · Fall 2026

The channel and the rate

The binary symmetric channel flips each bit independently with probability \(p\).

\[E:\{0,1\}^k\to\{0,1\}^n,\qquad D:\{0,1\}^n\to\{0,1\}^k,\qquad\text{rate}=k/n.\]

Fix \(0<p<1/2\). Write \(\Delta(x,r)\) for Hamming distance and

\[H(p)=-p\lg p-(1-p)\lg(1-p),\qquad C=1-H(p).\]

All logarithms \(\lg\) are base \(2\).

Shannon’s theorem

Fix \(\delta>0\) and \(0<\gamma<1\). For sufficiently large \(n\):

If \(k\leq n(C-\delta)\), some encoder and decoder have error at most \(\gamma\) for every message.

If \(k\geq n(C+\delta)\), every encoder and decoder have success probability less than \(\gamma\) for a uniform random message.

We prove achievability. The converse is stated without proof in the notes.

The random coding scheme

  1. Sample \(N=2^{k+1}\) independent uniform codewords \(Y_i\in\{0,1\}^n\).
  2. Decode by unique membership in a typical Hamming ring.
  3. Retain the \(2^k\) indices with smallest decoding error and relabel them by messages.

This proves existence; the unstructured codebook and exhaustive decoder are not computationally efficient.

Typical rings and the decoder

For \(0<\varepsilon<1\), define

\[\mathcal R(x)=\{r:(1-\varepsilon)np\leq\Delta(x,r)\leq(1+\varepsilon)np\}.\]

Given \(r\), return index \(i\) if \(r\in\mathcal R(Y_i)\) for exactly one index.

Otherwise declare failure. A declared failure counts as an error.

Two error events

Planar schematic of discrete Hamming rings; overlaps cause ambiguity.

Either the output misses the transmitted word’s ring, or it lies in that ring and a competing ring.

Atypical noise is rare

For fixed \(Y_i=x\), \(\Delta(x,R)\sim\operatorname{Binomial}(n,p)\).

\[\Pr[R\notin\mathcal R(x)] \leq a_n:=2e^{-\varepsilon^2pn/4}.\]

Choose \(n\) large enough that \(a_n\leq\gamma/8\).

The bound is uniform in \(x\) and independent of the other codewords.

Entropy bounds the ring size

Put \(q=(1+\varepsilon)p<1/2\). Binomial coefficients increase up to \(n/2\):

\[\begin{aligned} |\mathcal R(r)| &=\sum_{m=\lceil(1-\varepsilon)np\rceil}^{\lfloor(1+\varepsilon)np\rfloor}\binom nm\\ &\leq(n+1)\binom n{\lfloor nq\rfloor} \leq(n+1)2^{nH(q)}. \end{aligned}\]

The last inequality is the entropy counting bound from the preceding lecture.

Bound competing explanations

Condition on \(Y_i=x\) and a received word \(r\in\mathcal R(x)\). Every \(Y_j\), \(j\ne i\), remains uniform and independent of this conditioning.

\[\Pr[r\in\mathcal R(Y_j)] =\Pr[Y_j\in\mathcal R(r)] =\frac{|\mathcal R(r)|}{2^n}.\]

\[\Pr[\text{ambiguity}\mid x,r] \leq2^{k+1}(n+1)2^{n(H(q)-1)}.\]

Symmetry of Hamming distance gives the first equality; a union bound gives the second display.

Use the gap below capacity

Since \(k\leq n(1-H(p)-\delta)\),

\[\Pr[\text{ambiguity}\mid x,r] \leq2(n+1)2^{n(H(q)-H(p)-\delta)}.\]

Choose \(\varepsilon\) by continuity so that \(q<1/2\) and \(H(q)-H(p)\leq\delta/2\).

Then ambiguity is at most \(b_n:=2(n+1)2^{-n\delta/2}\leq\gamma/8\) for large \(n\).

Choose \(p,\delta,\gamma\), then \(\varepsilon\), then \(n\).

Error is a weighted sum

Let \(S_i\) be the received words that uniquely decode to index \(i\).

\[w(x,r)=p^{\Delta(x,r)}(1-p)^{n-\Delta(x,r)},\qquad\sum_rw(x,r)=1.\]

\[W_i=\sum_rw(Y_i,r)\mathbf1_{\{r\notin S_i\}}.\]

\(W_i\) is the channel error of index \(i\) for a fixed codebook. It becomes a random variable when we sample the codebook.

Expected error of one codeword

Fix \(Y_i=x\) and average over the competing codewords:

\[\begin{aligned} \mathbb E[W_i\mid Y_i=x] &\leq\sum_{r\notin\mathcal R(x)}w(x,r) +\sum_{r\in\mathcal R(x)}w(x,r)b_n\\ &\leq a_n+b_n\leq\gamma/4. \end{aligned}\]

Hence \(\mathbb E[W_i]\leq\gamma/4\) for every index \(i\).

Fix a codebook with small total error

\[\mathbb E\!\left[\sum_{i=0}^{N-1}W_i\right] \leq\frac{N\gamma}{4}.\]

Therefore some fixed codebook satisfies \(\sum_iW_i\leq N\gamma/4\).

No independence among the \(W_i\) is needed.

Expurgate the bad indices

Let \(B=\{i:W_i>\gamma\}\) for this fixed codebook.

\[\gamma|B|\leq\sum_iW_i\leq\frac{N\gamma}{4} \quad\Longrightarrow\quad |B|\leq N/4.\]

At least \(3N/4\) indices have error at most \(\gamma\).

Keep the best \(N/2=2^k\) indices.

Restrict the decoder and relabel

Deleting competing codewords enlarges each retained success region.

Thus every retained codeword has error at most \(\gamma\) under the new decoder.

Assign the \(2^k\) messages bijectively to these words.

Duplicates cannot survive: two identical indexed words each have error \(1\) under the original unique-ring decoder, while \(\gamma<1\).

The achieved guarantee

\[\boxed{k\leq n(1-H(p)-\delta) \quad\Longrightarrow\quad \max_m\Pr[D(R)\ne m\mid m]\leq\gamma}\]

for all sufficiently large block lengths.

Random coding controls expected error; expurgation protects every message.

The guarantee concerns independent random noise, not every pattern of \(np\) flips.

Capacity: the counting intuition

\[\underbrace{2^k}_{\text{messages}} \cdot\underbrace{2^{nH(p)}}_{\text{typical noise scale}} \quad\text{versus}\quad \underbrace{2^n}_{\text{outputs}}.\]

Disjoint decoding regions motivate the threshold \(k/n=1-H(p)\).

This picture explains the converse intuition; it does not prove the strong converse stated earlier.

Reading and proof ingredients

Notes 45: Entropy III — Shannon’s Theorem.

Mitzenmacher and Upfal, Probability and Computing (2005), §§9.1–9.3, as cited in the notes.

Concentration + entropy counting + the probabilistic method + expurgation.