Entropy III: Shannon’s Theorem

Mid-length lecture · Lecture 23

Sariel Har-Peled

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

The binary symmetric channel

For input \(x=(x_1,\ldots,x_n)\), the output is

\[R=x\oplus Z,\qquad Z_j\sim\operatorname{Bernoulli}(p),\]

where the \(Z_j\) are independent and \(\oplus\) is bitwise XOR.

Thus \(\Pr[R_j\ne x_j]=p\), independently for every position.

We work with a fixed \(0<p<1/2\).

Encoding and decoding

\[\{0,1\}^k\ \xrightarrow{\ E\ }\ \{0,1\}^n \ \xrightarrow{\ \text{channel}\ }\ \{0,1\}^n \ \xrightarrow{\ D\ }\ \{0,1\}^k.\]

The sender transmits \(E(m)\); the receiver computes \(D(R)\).

For message \(m\), an error is the event \(D(R)\ne m\).

Our decoder may declare failure; a declared failure counts as an error.

The entropy of one noise bit

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

Here \(\lg\) means logarithm to base \(2\), and \(0\lg0=0\).

For \(0<p<1/2\), \(H(p)\) is continuous and increasing.

About \(2^{nH(p)}\) noise patterns matter on the exponential scale.

Shannon’s theorem: achievable rates

Fix \(0<p<1/2\), a rate gap \(\delta>0\), and an error target \(0<\gamma<1\).

For sufficiently large \(n\), if

\[k\leq n\bigl(1-H(p)-\delta\bigr),\]

there are encoding and decoding functions with

\[\Pr[D(R)\ne m\mid m\text{ sent}]\leq\gamma \qquad\text{for every }m.\]

Shannon’s theorem: the converse

Fix \(0<p<1/2\), \(\delta>0\), and \(0<\gamma<1\).

For sufficiently large \(n\), if

\[k\geq n\bigl(1-H(p)+\delta\bigr),\]

then every encoder and decoder satisfy

\[\Pr[D(R)=M]<\gamma, \qquad M\text{ uniform on }\{0,1\}^k.\]

We state this direction without proof, as in the notes.

Sample a larger codebook

Set \(N=2^{k+1}\), where \(k\leq n(1-H(p)-\delta)\).

Sample \(Y_0,\ldots,Y_{N-1}\) independently and uniformly from \(\{0,1\}^n\).

Analyze the ring decoder using all \(N\) codewords.

Eventually retain only \(2^k\) of them.

The randomness is used to prove that a good fixed codebook exists.

A typical Hamming ring

Choose a small constant \(0<\varepsilon<1\).

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

The ring consists of the plausible received words for \(x\).

Also require \((1+\varepsilon)p<1/2\).

The rings of error

The source’s planar schematic: orange overlaps are ambiguous. Hamming rings are discrete sets, not planar annuli.

The red curve marks distance \(np\); the ring has width \(2\varepsilon np\).

The typical-ring decoder

Given the received word \(r\), inspect every codeword.

If exactly one codeword \(Y_i\) satisfies \(r\in\mathcal R(Y_i)\), output its index.

If none or more than one qualify, declare failure.

Being too close to a codeword can also put \(r\) outside its ring.

Error for one indexed codeword

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

\[W_i=\Pr[R\notin S_i\mid Y_i\text{ sent}] =\sum_r w(Y_i,r)\,\mathbf1_{\{r\notin S_i\}}.\]

For a fixed codebook, \(W_i\) is a number in \([0,1]\).

For a random codebook, \(W_i\) is a random variable.

Our goal is \(\mathbb E_{\mathcal C}[W_i]\leq\gamma/4\) for every index \(i\).

Concentration puts the output in the ring

The two-sided Chernoff bound gives, for \(0<\varepsilon<1\),

\[\Pr[R\notin\mathcal R(x)] \leq 2\exp\!\left(-\frac{\varepsilon^2pn}{4}\right).\]

For fixed \(p,\varepsilon>0\), this decays exponentially with \(n\).

Write the bound as \(a_n\) and take \(n\) large enough that \(a_n\leq\gamma/8\).

The size of one ring

Combining the layer count and the entropy bound,

\[|\mathcal R(r)| \leq(n+1)\binom n{\lfloor nq\rfloor} \leq(n+1)2^{nH(q)},\]

where \(q=(1+\varepsilon)p<1/2\).

The polynomial factor \(n+1\) will be dominated by an exponential rate gap.

Freeze the transmitted and received words

Condition on \(Y_i=x\) and \(R=r\) when index \(i\) is sent.

Each other codeword \(Y_j\) is still uniform on \(\{0,1\}^n\).

The other codewords are independent of \(Y_i\) and its channel noise.

This leaves a simple counting problem for every competitor.

One uniform competitor

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

All strings are equally likely as a sampled codeword.

The number of strings in a Hamming ring is independent of its center.

Union bound over competing codewords

For fixed \(x\) and \(r\in\mathcal R(x)\), let \(b_{i,r}\) be the conditional ambiguity probability.

\[\begin{aligned} b_{i,r} &\leq\sum_{j\ne i}\Pr[Y_j\in\mathcal R(r)]\\ &\leq2^{k+1}(n+1)2^{n(H(q)-1)}. \end{aligned}\]

No independence between the ambiguity events is needed for this union bound.

Insert the rate bound

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

\[\begin{aligned} b_{i,r} &\leq2^{k+1}(n+1)2^{n(H(q)-1)}\\ &\leq2(n+1)2^{n(H(q)-H(p)-\delta)}. \end{aligned}\]

We want the exponent to be a negative constant times \(n\).

Spend half the rate gap on the ring width

By continuity of \(H\), choose \(\varepsilon>0\) small enough that

\[q=(1+\varepsilon)p<\frac12, \qquad H(q)-H(p)\leq\frac\delta2.\]

Also keep \(\varepsilon<1\). Then

\[H(q)-H(p)-\delta\leq-\frac\delta2.\]

Exponential decay beats the layer count

\[b_{i,r}\leq b_n:=2(n+1)2^{-n\delta/2}.\]

For fixed \(\delta>0\), \(b_n\to0\).

Increase \(n\) until \(b_n\leq\gamma/8\).

This bound holds for every \(i\), every \(x\), and every \(r\in\mathcal R(x)\).

Average with the channel weights

For \(Y_i=x\), the inside-ring contribution is

\[g(x)=\sum_{r\in\mathcal R(x)} w(x,r)\Pr_{\mathcal C\setminus Y_i}[r\notin S_i\mid Y_i=x].\]

Each term keeps its weight \(w(x,r)\).

These weights turn a sum over received strings into a probability.

Inside the ring: total error mass

Apply the pointwise collision bound to every summand:

\[\begin{aligned} g(x) &\leq\sum_{r\in\mathcal R(x)}w(x,r)\frac\gamma8\\ &\leq\frac\gamma8, \end{aligned}\]

because \(\sum_{r\in\mathcal R(x)}w(x,r)\leq1\).

Combine the two error contributions

Let \(f(x)=\sum_{r\notin\mathcal R(x)}w(x,r)\leq a_n\leq\gamma/8\).

\[\begin{aligned} \mathbb E_{\mathcal C}[W_i\mid Y_i=x] &=f(x)+g(x)\\ &\leq\frac\gamma8+\frac\gamma8 =\frac\gamma4. \end{aligned}\]

The estimate holds for every transmitted word \(x\).

Remove the conditioning

Average over the uniform choice of \(Y_i\):

\[\mathbb E_{\mathcal C}[W_i] =\mathbb E_{Y_i}\!\left[ \mathbb E_{\mathcal C}[W_i\mid Y_i]\right] \leq\frac\gamma4.\]

Every index has small expected error over random codebooks.

We still need one fixed codebook protecting every retained index.

Fix one good codebook

Linearity gives \(\mathbb E[\overline W]\leq\gamma/4\) for \(\overline W=N^{-1}\sum_iW_i\).

Some sampled codebook satisfies

\[\overline W\leq\frac\gamma4, \qquad\text{so}\qquad \sum_{i=0}^{N-1}W_i\leq\frac{N\gamma}{4}.\]

Otherwise every codebook would have average error greater than its expectation bound.

From now on, the codebook is fixed.

How many codewords can be bad?

Let \(B=\{i:W_i>\gamma\}\).

\[\gamma|B|\leq\sum_{i\in B}W_i \leq\sum_{i=0}^{N-1}W_i \leq\frac{N\gamma}{4}.\]

Thus \(|B|\leq N/4\); at least \(3N/4\) indices have \(W_i\leq\gamma\).

We need only \(N/2=2^k\) good indices.

Keep the best half

Retain the \(2^k\) indices with the smallest \(W_i\).

Call their codewords \(X_0,\ldots,X_{2^k-1}\).

Every retained index had error at most \(\gamma\) in the larger codebook.

Discarding codewords with large error is called expurgation.

Recompute the decoder on the retained set

The new decoder searches only \(X_0,\ldots,X_{2^k-1}\).

For each retained index,

\[S_i^{\mathrm{old}}\subseteq S_i^{\mathrm{new}}, \qquad W_i^{\mathrm{new}}\leq W_i^{\mathrm{old}}\leq\gamma.\]

Removing competitors can turn ambiguous outputs into uniquely decodable outputs.

Why the retained words are distinct

Suppose two sampled indices had the same word: \(Y_i=Y_j\).

Their rings coincide, so neither index ever decodes uniquely.

Thus \(W_i=W_j=1\) in the original codebook.

Since \(\gamma<1\), no such index belongs to the selected good half.

Achievability is proved

For \(k\leq n(1-H(p)-\delta)\) and sufficiently large \(n\),

\[\boxed{\max_m\Pr[D(R)\ne m\mid m\text{ sent}]\leq\gamma.}\]

Random coding controls average error.

Expurgation makes the guarantee hold for every message.

A quantitative view of the proof

Before choosing the final block length,

\[\mathbb E_{\mathcal C}[W_i] \leq\underbrace{2e^{-\varepsilon^2pn/4}}_{\text{atypical noise}} +\underbrace{2(n+1)2^{-n\delta/2}}_{\text{ambiguity}}.\]

A smaller rate gap leaves less room for noise fluctuations.

A longer block makes both sources of error small.

Where the capacity expression comes from

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

The threshold on the exponential scale is \(k/n=1-H(p)\).

The proof makes this intuition precise using a slightly wider ring and a fixed rate gap.

Why there is also a converse

Each message needs a decoding region carrying substantial channel probability.

Different messages have disjoint decoding regions inside a space of \(2^n\) received words.

Typical noise spreads probability over roughly \(2^{nH(p)}\) possible outputs per message.

This motivates the threshold \(1-H(p)\); it is packing intuition, not a proof of the strong converse.

Three ideas to remember

Concentration: the received word lies in a typical ring.

Entropy counting: a random competing codeword rarely explains it.

Expurgation: average reliability yields reliability for every retained message.

Together they achieve every fixed rate below \(1-H(p)\).

Reading

Notes 45: Entropy III — Shannon’s Theorem.

The notes follow Michael Mitzenmacher and Eli Upfal, Probability and Computing (2005), §§9.1–9.3.

Prerequisites: entropy, binomial coefficient estimates, Chernoff bounds, and the probabilistic method.